{"id":"8c907d21-bd2d-4445-8d37-b94fcd92d6e4","arxiv_id":"2412.00985","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper gives the first provable polynomial-sample and quasi-polynomial-time guarantees for expert distillation and belief-weighted asymmetric actor-critic in POMDPs with privileged state information.","lead":"This theory paper studies two widely used reinforcement learning tricks that use hidden state information during training: teacher-student distillation and asymmetric actor-critic. It proves that under natural structural conditions these tricks can be made sample-efficient without computationally intractable planning oracles.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central theorem appears sound, but its polynomial-sample guarantee depends on applying the imported filter-stability bound to the truncated learned model bP_sub, whose time-varying state spaces and uniform prior are not explicitly covered by [22, Theorem 4.1].","rationale":"The paper's central positive result is Theorem 5.3: a polynomial-sample, quasi-polynomial-time guarantee for gamma-observable POMDPs with privileged information. The proof chain is Algorithm 4 learns a truncated model bP_sub; Theorem F.6 shows the approximate belief is epsilon-close for all pi in Pi_L; Theorem 5.1 converts that into a near-optimal policy. I checked the internal steps of the proof: the optimism argument for the Q-estimates, the MWU regret with belief weighting, and the total-variation decompositions connecting P to P_trunc to bP_trunc. Those steps are largely standard, and minor issues such as an off-by-one indexing in the policy-update proof and the Proposition 3.1 overclaim about non-strict f-divergences are real but do not break the main theorems. The least secure point is the unverified application of the imported filter-stability theorem to bP_sub, which has layer-dependent state spaces and starts its finite-memory filter from a uniform prior. This is a verification gap rather than a demonstrated inconsistency: if [22, Theorem 4.1] extends to the time-inhomogeneous truncated model as the paper implicitly assumes, the central claim holds; if not, the polynomial sample complexity does not follow from the provided proof. An independent check of this single step would settle the matter, so I recommend CONDITIONAL rather than ACCEPT or REJECT.","tokens_in":69460,"tokens_out":38802,"duration_ms":368360,"concrete_test":"Independently verify the filter-stability inequality for the time-inhomogeneous, truncated model bP_sub: instantiate a gamma-observable POMDP with time-varying state spaces S_high^h (e.g., S=3, H=4, gamma=0.5), compute the exact finite-memory filter b'_h(z_h) with uniform prior and window length L = c * gamma^{-4} log(SH/epsilon) for a range of c, and compare E_pi ||b_h(tau_h) - b'_h(z_h)|| to the true filter under several policies pi in Pi_L. If the error does not decay to epsilon at the claimed L, the proof of Theorem F.6 has a gap and Theorem 5.3 needs revision.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 5.3's polynomial sample complexity rests on Theorem F.6, which bounds E_pi ||b_h(tau_h) - bapx_h(z_h)|| for every pi in Pi_L by decomposing into truncation error, model error, and the finite-memory filtering error of the truncated learned model bP_sub. The third term is bounded by invoking [22, Theorem 4.1] on bP_sub, which is shown to be gamma/2-observable. Two hypotheses of that imported theorem are not checked in the paper. First, [22, Theorem 4.1] is stated for a POMDP with a fixed state space S; the constructed bP_sub has state spaces S_high^h that vary with h and are only implicitly time-indexed. Second, the approximate filter is initialized with a uniform prior over S_high^h at the start of the length-L window, whereas the imported theorem's constants and burn-in may require a particular prior or a minimum number of observations to contract. If either hypothesis fails, the bound L = eOmega(gamma^{-4} log(SH/epsilon)) may not suffice for the third term, and the polynomial sample complexity in Theorem 5.3 does not follow. This is the least secure link in the chain: the other components (Q estimation, MWU, truncation TV bounds) are standard and checkable, while this external filter-stability application is load-bearing and not re-derived in the paper.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies partially observable RL in the setting where privileged state information is available during training, and it provides provable guarantees for two practically used paradigms. It first formalizes the expert-distillation (teacher-student) objective in Equation (3.1) and shows, in Proposition 3.1, that even for a gamma-observable POMDP and with infinite distillation data, the distilled policy can be strictly suboptimal. It then introduces the deterministic filter condition (Definition 3.2), which subsumes deterministic POMDPs, block MDPs, and k-step decodable POMDPs with unknown k, and proves that under this condition expert distillation achieves polynomial sample and computational complexity (Theorem 4.6). For the asymmetric actor-critic paradigm, the paper argues that the vanilla variant has super-polynomial sample complexity (Proposition 3.7) and develops a belief-weighted optimistic asymmetric actor-critic (Algorithm 2) together with a belief-learning oracle based on model truncation (Algorithms 3-4). The main guarantee, Theorem 5.3, states that for a gamma-observable POMDP, a policy pi in Π_L can be learned with v_P(pi) >= max_{pi'} v_P(pi') - epsilon using poly(S,H,1/epsilon,1/gamma,log(1/delta),O,A) episodes and quasi-polynomial time, provided L >= Omega-tilde(gamma^{-4} log(SH/epsilon)). The framework is extended to partially observable stochastic games under centralized-training-with-decentralized-execution in Theorems 7.4, 7.6, and 7.7.","tokens_in":69760,"tokens_out":22633,"duration_ms":209158,"significance":"The paper's central claim, that privileged state information reduces the sample complexity of observable POMDPs from quasi-polynomial to polynomial while avoiding computationally intractable planning oracles, is significant if it holds. The algorithmic framework is genuinely modular: the belief-learning oracle of Section 5.2, which truncates rarely visited states while preserving observability and filter stability, is a substantive technical contribution that may be of independent interest, and the deterministic filter condition correctly unifies several known tractable POMDP classes. The presentation is careful about what is imported and what is proved in the paper: the algorithms are explicit, the proofs are detailed and modular, the comparisons with prior work are fair, and the limitation of assuming exact state information is acknowledged in Section 8. The numerical study is honest and small-scale.","major_comments":[{"comment":"Proposition 3.1 is stated for any choice of D_f (any f-divergence) in Equation (3.1), but the proof establishes the claim only for strictly convex generators f. The step identifying the minimizer of E_{s~b1(o1)}[D_f(pi*(.|s)||q)] with Unif(A) uses a uniqueness assertion from Jensen's inequality that holds only when f is strictly convex, which the proof itself concedes in the parenthetical 'for the common choice of D_f ... where f is strictly convex.' For a non-strictly-convex generator such as f(t)=|t-1| (total variation), the objective (TV(delta_{a1},q)+TV(delta_{a2},q))/2 equals 1/2 for every q in Delta(A) in the constructed counterexample, so every q is a minimizer; choosing q = delta_{a1} yields a distilled policy whose value gap to the optimal policy is gamma*epsilon/(2-gamma), which is strictly smaller than the claimed (1-gamma)(1-epsilon)/4 for, e.g., gamma = epsilon = 0.1. The proposition should be restricted to strictly convex f (or to a fixed tie-breaking rule that the proof controls), and the statement should be corrected accordingly.","section":"Section 3.1, Proposition 3.1 (proof in Appendix C)"},{"comment":"The load-bearing step of the proof of Theorem F.6 is the assertion that, for the truncated learned model bP_sub, E_{bP_sub,pi}||b_{b,sub,h}(tau_h) - b'_{b,sub,h}(z_h)||_1 <= epsilon follows from [22, Theorem 4.1] with L >= Omega-tilde(gamma^{-4} log(SH/epsilon)). Two hypotheses of that imported theorem are not verified for the constructed bP_sub. First, [22, Theorem 4.1] is stated for a POMDP with a fixed state space S, whereas bP_sub has state spaces S_high^h that vary with h; this is not a purely notational issue, because the gamma-observability assumption in the imported theorem is a global condition over all pairs of beliefs on a single state space, and the natural time-augmented model union_h {h} x S_high^h does not automatically inherit it from the slice-wise separation condition shown in the paper. Second, the finite-memory filter b'_{b,sub,h} is re-initialized with the uniform prior over S_high^{h-L} at the start of each length-L window, while the ground-truth belief b_{b,sub,h} is conditioned on the full history under the truncated initial distribution mu_trunc_1; the paper does not check that the imported theorem's constants accommodate this prior mismatch and the burn-in of the contraction. Since this filter-stability bound is essential for Theorem F.6, and hence for the polynomial sample complexity claimed in Theorem 5.3 (and in the multi-agent Theorem 7.7), the authors should provide a self-contained filter-stability lemma for the truncated, time-varying model bP_sub with all constants tracked, or verify the hypotheses of [22, Theorem 4.1] verbatim.","section":"Appendix F, proof of Theorem F.6 (invoked by Theorem 5.3)"}],"minor_comments":[{"comment":"The displayed formulas for NE-gap and CCE-gap are identical; the distinction between Nash equilibrium and coarse correlated equilibrium (product policies versus potentially correlated joint policies, and the admissible deviation sets) should be made explicit in the displayed equations or by naming the policy classes over which the maxima are taken.","section":"Section 2.2, Definitions 2.2 and 2.3"},{"comment":"The argument that the vanilla asymmetric actor-critic has super-polynomial sample complexity is informal: it assumes that convergence of the tabular update to an epsilon-optimal policy would imply a polynomial-time planner whenever the sample complexity is polynomial, but no convergence guarantee for that update rule is stated, and the coupling between per-iteration computation and sample count is not formalized; the proposition should be stated as conditional on that convergence property or proved formally.","section":"Appendix C, proof of Proposition 3.7"},{"comment":"The inequality P_{pi,P}(tau_h) <= P_{pi,P_trunc}(tau_h) for tau_h in T_high_h is asserted without justification; a one-line argument that truncation only transfers probability mass out of S_low into S_high, so the probability of every all-high trajectory weakly increases, would make the step transparent.","section":"Appendix F, proof of Theorem F.6"},{"comment":"The statement of Theorem F.6 contains an unmatched parenthesis in L >= Omega-tilde(gamma^{-4} log(S/epsilon), and the accuracy parameter is denoted epsilon in the theorem statement but ϵ (same symbol as the model-error parameter) at several points in the proof; the two accuracies should be distinguished and the notation made consistent.","section":"Appendix F, Theorem F.6 statement and proof"}],"recommendation":"major_revision","confidential_remarks":"The paper fits the journal's scope and the main claim is defensible, but the unverified application of [22, Theorem 4.1] to the truncated, time-varying model bP_sub in the proof of Theorem F.6 is a genuine load-bearing gap that should be resolved before publication; it appears fixable within the manuscript's scope by adding a self-contained filter-stability lemma, so I do not recommend rejection on that basis. The overclaim in Proposition 3.1 is local but should be corrected because the pitfall result is advertised as a contribution. The conditional verdict in the reader's report is consistent with my own assessment."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. First, it delivers real results: it formalizes expert distillation and asymmetric actor-critic under privileged information, identifies the deterministic filter condition, and proves polynomial sample complexity for both paradigms without intractable planning oracles. The belief-weighted actor-critic and the model-truncation oracle are genuinely new, and the modular proof structure is a strength. Second, the weakest link is not the conceptual framework but a specific imported theorem application in Theorem 5.3.\n\nThe deterministic filter condition section (Section 4) is clean. The pitfall result (Proposition 3.1) is correct in spirit, but the statement overclaims: it says 'any f-divergence,' while the proof only supports strictly convex f. That is a minor blemish, fixable by qualifying the statement; it does not affect the main results. The expert-distillation theorems are convincing and the function-approximation extension is a nice bonus.\n\nThe main concern, and it is a real one, is the step where Theorem 5.3 applies the filter-stability bound from [22, Theorem 4.1] to the truncated learned model bP_sub. Two hypotheses are not explicitly checked. First, [22] assumes a fixed state space, while bP_sub has state spaces S_high^h that vary with h. Second, the approximate filter is initialized with a uniform prior over S_high^h at the start of a length-L window, which may not match the prior or burn-in required by the imported theorem. The paper shows bP_sub is gamma/2-observable, but that alone does not guarantee the constant L = eOmega(gamma^{-4} log(SH/epsilon)) suffices for the finite-memory filtering error. If this step fails, the polynomial sample complexity in Theorem 5.3 does not follow. The rest of the chain—Q-estimation, MWU, truncation TV bounds—is standard and checkable. This is the load-bearing external step, and it is not re-derived.\n\nThat said, the paper is honest about its assumptions, the experiments are small but not overclaimed, and the self-citations are appropriate (they supply background results, not the target conclusions). The MARL extension in Section 7 is plausible and follows the same template.\n\nWho should read this: anyone working on provable POMDP RL or on theory for practical paradigms like teacher-student or CTDE. It deserves a serious referee, but the referee should push on the filter-stability application. If the authors can patch that step—either by re-proving the filtering bound for time-varying state spaces with a uniform prior, or by adding the needed conditions—the paper is a solid contribution. I would accept it for peer review now, conditionally, with the expectation that this gap is addressed.","headline":"A substantial theory paper that gives the first polynomial-sample explanation for teacher-student and asymmetric actor-critic with privileged information, but the load-bearing filter-stability step in Theorem 5.3 deserves scrutiny before you rely on it.","tokens_in":70266,"tokens_out":801,"would_cite":true,"duration_ms":10555,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"On $\\gamma$-observable partially observable Markov decision processes, training with access to the true underlying states reduces the sample complexity of learning a near-optimal policy from quasi-polynomial to polynomial, while…","keywords":["partially observable Markov decision process","privileged information","expert distillation","asymmetric actor-critic","belief state learning","gamma-observability","filter stability","centralized training with decentralized execution"],"falsifier":"A concrete check: instantiate the $H=1$, $S=O=A=2$ instance from the paper's own Proposition 3.1 with small $\\gamma$ (two states whose emission distributions differ by $\\gamma$), run Algorithm 2 with $L=\\widetilde{\\Omega}(\\gamma^{-4}\\log(SH/\\epsilon))$ and about $\\mathrm{poly}(1/\\epsilon,1/\\gamma)$ episodes, and measure both the value gap to the optimal history-dependent policy and the $\\ell^1$ error of the learned belief. The theorem predicts both shrink to $O(\\epsilon)$; any instance where the gap or the belief error stalls as $1/\\gamma$ grows would point at the filter-stability step. A second, sharper test targets the truncation lemma: search over $\\gamma$-observable POMDP instances for one where redirection of probability mass from rarely visited to frequently visited states (Algorithm 4) makes the empirical emission matrix fail $\\gamma/2$-observability — the proof of Theorem 5.2 depends on that separation being preserved.","tokens_in":69265,"feed_emoji":"🤖","tokens_out":15395,"duration_ms":120156,"temperature":0.7,"pith_summary":"This paper tries to establish that two paradigms practitioners actually use — expert distillation (teacher-student learning) and asymmetric actor-critic — can be provably sample- and computationally efficient for partially observable RL when training has privileged access to the true states. The first claim is a caution: distillation can lose a constant fraction of optimal value even on $\\gamma$-observable POMDPs, but becomes both sample- and time-polynomial under a new 'deterministic filter condition' (the belief always collapses to a single state), a condition weaker than known tractable classes and covering decodable POMDPs with unknown decoding length. The second and main claim is positive for the harder $\\gamma$-observable class: a belief-weighted asymmetric actor-critic with a new belief-learning oracle learns an $\\epsilon$-optimal policy with polynomial episodes and quasi-polynomial time — improving the quasi-polynomial sample complexity of prior no-intractable-oracle algorithms to polynomial, and beating vanilla actor-critic, which the paper proves is sample-super-polynomial. If correct, these results say that simulator or sensor access to states during training is not just practically useful but provably converts some of the hardest learnable POMDPs into polynomial-sample problems, without oracle shortcuts.","feed_headline":"State access in training makes hard POMDPs polynomial-sample learnable","feed_subtitle":"Teacher-student and asymmetric critic paradigms get provable efficiency without intractable planning oracles.","key_machinery":"The argument runs on three objects. (1) $\\gamma$-observability (Assumption 2.5): each emission matrix $O_h$ must separate any two belief distributions by at least $\\gamma$ in $\\ell^1$ norm; this is the condition under which $L$-step finite-memory policies approximate history-dependent policies, via the filter-stability bound $L\\ge\\widetilde{\\Omega}(\\gamma^{-4}\\log(SH/\\epsilon))$. (2) The deterministic filter condition (Definition 3.2): every Bayes belief update returns a one-hot state vector, so there is a function $\\psi_h(s_{h-1},a_{h-1},o_h)$ that exactly recovers the current state; this turns distillation into learning a decoding function, a supervised classification task solvable with polynomial samples and time, and it strictly generalizes deterministic transitions, block MDPs, and $k$-step decodable POMDPs. (3) Model truncation for belief learning (Algorithm 4): the learner explores the state space explicitly with a reward-free MDP subroutine (possible only because states are visible in training), estimates transitions and emissions, then redirects probability mass from rarely visited to frequently visited states so the truncated emission stays $(\\gamma/2)$-observable; finite-memory beliefs computed on the truncated model are provably within $\\epsilon$ of true beliefs in $\\ell^1$ under any policy. The belief-weighted policy update $\\pi_t(\\cdot|z)\\propto\\pi_{t-1}(\\cdot|z)\\exp(\\eta\\,\\mathbb{E}_{s\\sim b^{\\mathrm{apx}}(z)}[Q_{t-1}(z,s,\\cdot)])$, a multiplicative-weights step on each memory $z$ with the action-value averaged over the learned belief, is what decouples sample from computational complexity: synchronous updates over all memories cost quasi-polynomial computation per iteration but keep the number of episodes polynomial.","core_discovery":"The central claim, Theorem 5.3, states that for a $\\gamma$-observable POMDP $P$ — every emission matrix separates any two beliefs in $\\ell^1$ distance by at least $\\gamma$ — Algorithm 2 (belief-weighted optimistic asymmetric actor-critic with a truncated-model belief oracle) learns, with probability at least $1-\\delta$, a finite-memory policy $\\pi\\in\\Pi_L$ with $v_P(\\pi)\\ge \\max_{\\pi'\\in\\Pi} v_P(\\pi')-\\epsilon$, using $\\mathrm{poly}(S,H,1/\\epsilon,1/\\gamma,\\log(1/\\delta),O,A)$ episodes and running in time $\\mathrm{poly}(S,H,1/\\epsilon,\\log(1/\\delta),O^L,A^L)$, where $L=\\widetilde{\\Omega}(\\gamma^{-4}\\log(SH/\\epsilon))$. The sample complexity is polynomial where the best prior guarantees without intractable oracles were quasi-polynomial; the time remains quasi-polynomial, which the paper notes cannot be improved even for planning. A second theorem (4.6) claims that under the deterministic filter condition, expert distillation matches the value of any state-based expert policy with both sample and computational complexity polynomial, including for $k$-decodable POMDPs with unknown, arbitrary $k$, where learning without privileged information is exponential in $k$. The paper also claims (Proposition 3.7) that vanilla asymmetric actor-critic is inherently sample-super-polynomial, and extends both frameworks to partially observable Markov games under centralized-training-with-decentralized-execution information sharing, with polynomial sample and (quasi-)polynomial time guarantees for Nash, correlated, and coarse correlated equilibria.","pith_inferences":["A general design principle implicit in the paper: privileged information converts exploration from a POMDP problem into a state-space MDP problem, leaving partial observability to be handled only inside a belief-estimation oracle; the analysis is all-or-nothing about state quality, so how guarantees degrade with noisy, biased, or delayed privileged states is an open extension.","The $\\gamma^{-4}$ exponent in the required memory length $L$ is imported from filter stability and not shown tight; a sharper filter-stability bound would directly shrink the quasi-polynomial time exponent, since runtime is polynomial in $O^L$ and $A^L$.","The explicit counterexample behind Proposition 3.1 doubles as a cheap diagnostic: measuring whether empirical belief updates are near one-hot under random rollouts could tell a practitioner whether the cheap distillation pipeline is safe or whether belief-weighted actor-critic is needed.","The truncated-model belief oracle is a standalone reward-free primitive that any $\\gamma$-observable POMDP algorithm needing an approximate belief could consume; the paper flags possible independent interest but does not explore such reuse."],"forward_implications":["For $\\gamma$-observable POMDPs, privileged state information during training cuts sample complexity from quasi-polynomial to polynomial while keeping runtime quasi-polynomial, without any computationally intractable planning oracle.","Under the deterministic filter condition, expert distillation achieves both polynomial sample and polynomial time, matching a state-based expert's value even when the state-decoding length is unknown and arbitrary; without privileged information, $k$-decodable POMDPs need sample complexity exponential in $k$.","The belief-learning oracle is modular: any approximate belief with $\\ell^1$ error $\\epsilon_{\\mathrm{belief}}$ yields a policy with value gap $O(\\epsilon + H^2\\epsilon_{\\mathrm{belief}})$, giving a provable guarantee for the belief-state learning plus planning paradigm used by many empirical systems.","Vanilla asymmetric actor-critic cannot be fixed by tuning alone: with tabular parameterization it is provably sample-super-polynomial on $\\gamma$-observable POMDPs under standard hardness assumptions.","In multi-agent settings with information sharing (centralized training, decentralized execution), the same two paradigms yield polynomial-sample, (quasi-)polynomial-time guarantees for Nash, correlated, and coarse correlated equilibria in the analogous model classes."],"supporting_citations":[{"why":"supplies the filter-stability theorem ($L\\ge\\widetilde{\\Omega}(\\gamma^{-4}\\log(SH/\\epsilon))$) that lets finite-memory filters approximate true beliefs, and the quasi-polynomial planning baseline","marker":"[38]"},{"why":"gives the prior quasi-polynomial-sample guarantee for learning observable POMDPs without intractable oracles, which Theorem 5.3 improves to polynomial samples","marker":"[22]"},{"why":"defines $k$-step decodable POMDPs, a special case of the deterministic filter condition where the paper removes the exponential-in-$k$ sample dependence","marker":"[27]"},{"why":"defines weakly revealing/undercomplete POMDPs and the deterministic-transition, well-separated-emission model subsumed by the deterministic filter condition","marker":"[9]"},{"why":"defines block MDPs, another subclass covered by the deterministic filter condition","marker":"[8]"},{"why":"introduces the asymmetric actor-critic paradigm whose vanilla form the paper proves sample-super-polynomial","marker":"[19]"},{"why":"shows the state-only critic is biased, motivating the unbiased state-plus-history critic used in the paper's updates","marker":"[47]"},{"why":"establishes polynomial sample complexity under hindsight observability but with computationally intractable planning oracles, the comparison point for the no-intractable-oracle goal","marker":"[20]"},{"why":"provides the reward-free MDP exploration subroutine that Algorithm 4 uses to explore the state space with privileged information","marker":"[89]"}],"fun_headline_variants":["Privileged info makes hard POMDPs learnable in polynomial samples","Teacher-student and asymmetric critic get polynomial sample guarantees","Polynomial-sample RL for partial observability with privileged states","Privileged state access tames POMDPs without intractable oracles"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise for the main result is $\\gamma$-observability: every observation channel must separate any two belief distributions by at least a margin $\\gamma$, together with the inherited filter-stability requirement that the memory length $L$ grow like $\\gamma^{-4}\\log(SH/\\epsilon)$. If some channel fails to separate beliefs or $\\gamma$ is tiny, finite-memory policies no longer approximate history-dependent policies, the learned belief can be far from the true one, and the polynomial-sample, quasi-polynomial-time guarantee collapses.","fun_headline_variants_meta":{"raw":{"variants":["Privileged info makes hard POMDPs learnable in polynomial samples","Teacher-student and asymmetric critic get polynomial sample guarantees","Polynomial-sample RL for partial observability with privileged states","Privileged state access tames POMDPs without intractable oracles"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000614,"raw_usage":{"total_tokens":2986,"prompt_tokens":1209,"completion_tokens":1777,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":825,"completion_tokens_details":{"reasoning_tokens":1700}},"tokens_in":825,"tokens_out":1777,"duration_ms":13322,"temperature":1.0,"reasoning_tokens":1700,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T04:48:05.372627+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete check: instantiate the $H=1$, $S=O=A=2$ instance from the paper's own Proposition 3.1 with small $\\gamma$ (two states whose emission distributions differ by $\\gamma$), run Algorithm 2 with $L=\\widetilde{\\Omega}(\\gamma^{-4}\\log(SH/\\epsilon))$ and about $\\mathrm{poly}(1/\\epsilon,1/\\gamma)$ episodes, and measure both the value gap to the optimal history-dependent policy and the $\\ell^1$ error of the learned belief. The theorem predicts both shrink to $O(\\epsilon)$; any instance where the gap or the belief error stalls as $1/\\gamma$ grows would point at the filter-stability step. A second, sharper test targets the truncation lemma: search over $\\gamma$-observable POMDP instances for one where redirection of probability mass from rarely visited to frequently visited states (Algorithm 4) makes the empirical emission matrix fail $\\gamma/2$-observability — the proof of Theorem 5.2 depends on that separation being preserved.","supporting_citations":[{"cited_title":"Learning in observable POMDPs, without computationally intractable oracles","cited_arxiv_id":null,"evidence_quote":"gives the prior quasi-polynomial-sample guarantee for learning observable POMDPs without intractable oracles, which Theorem 5.3 improves to polynomial samples"},{"cited_title":"Provable reinforce- ment learning with a short-term memory","cited_arxiv_id":null,"evidence_quote":"defines $k$-step decodable POMDPs, a special case of the deterministic filter condition where the paper removes the exponential-in-$k$ sample dependence"},{"cited_title":"Asymmetric actor critic for image-based robot learning","cited_arxiv_id":null,"evidence_quote":"introduces the asymmetric actor-critic paradigm whose vanilla form the paper proves sample-super-polynomial"},{"cited_title":"Unbiased asymmetric reinforcement learning under partial observability","cited_arxiv_id":null,"evidence_quote":"shows the state-only critic is biased, motivating the unbiased state-plus-history critic used in the paper's updates"},{"cited_title":"Learning in pomdps is sample- efficient with hindsight observability","cited_arxiv_id":null,"evidence_quote":"establishes polynomial sample complexity under hindsight observability but with computationally intractable planning oracles, the comparison point for the no-intractable-oracle goal"},{"cited_title":"Reward-free exploration for reinforcement learning","cited_arxiv_id":null,"evidence_quote":"provides the reward-free MDP exploration subroutine that Algorithm 4 uses to explore the state space with privileged information"}],"review_version":1}