Research map / Reinforcement learning / MDPs and planning
RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes LMDP-OMLE, the first sample-efficient online exploration algorithm for general latent MDPs with a constant number of latent contexts and no structural assumptions, built on a new off-policy evaluation lemma and LMDP coverage coefficient.
Problem
Sample-efficient exploration in Latent MDPs (LMDPs) where a fixed latent context is drawn at episode start and hidden from the agent, without separation or full-rank structural assumptions; prior bounds suffer the curse of horizon, A^H.
Approach
Derives an off-policy evaluation lemma for LMDPs using segmented policies (switching between test policies with uniform-action interventions at checkpoints) and a new coverage coefficient over subsequences of up to d=2M-1 state-action tuples; combined with OMLE-style optimistic model elimination and reduction to memoryless policies, coverage doubles each iteration, yielding poly(S,A,H)^M-type samp
Key results
- LMDP-OMLE terminates after K=O(MS^2H) log(MSAH/eps) iterations with sample complexity N ~ (M^4 S^6 A^4 H^7 log(MSAH/eps))^d times M^4 H^2 log(K|Theta|/eta)/eps^2, d=2M-1, the first polynomial-in-(S,A,H) bound for general LMDPs with M=O(1) and no extra assumptions.
- A new OPE lemma bounds TV distance of history-dependent policies by an LMDP coverage coefficient times TV distances of segmented-policy partial trajectories of length at most d, independent of H.
- Sufficiency of memoryless policies: if memoryless policies are epsilon_test-accurate in TV, all history-dependent policies are accurate up to M(2H^2)^d (MSA)^d epsilon_test.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use LMDP-OMLE with segmented-policy exploration and the LMDP coverage coefficient | LMDPs with M latent contexts and H > 2M · LMDPs | sample complexity (episodes): N \gtrsim \left(M^4 S^6 A^4 H^7 \cdot \log(MSAH/\epsilon) \right)^{d} \cdot M^4 H^2 \cdot \log(K|\Theta|/\eta) / \epsilo | Helped |
Surprising findings
- A single latent-state coverage coefficient can be finite while off-policy evaluation guarantees still fail, motivating the multi-step LMDP coverage coefficient.
Limitations
- Sample complexity exponent grows as (...)^{2M-1}, so the bound is not tight relative to the Omega((SA)^M) lower bound.
- OPE lemma is restricted to segmented policies with interventions and does not give general OPE or regret guarantees for history-dependent behavior policies.
- Purely theoretical; no empirical evaluation or practical algorithm.
Experimental setup
Metrics: sample complexity
Baselines: OMLE moment-matching LMDP algorithm Chen et al. separation-based LMDP algorithm
Builds on: OMLE MDP coverage coefficient OPE moment-matching exploration for LMDPs
Closest papers by meaning
- Prospective Side Information for Latent MDPs (ICML 2024 · similarity 0.91)
- Offline-Online Reinforcement Learning for Linear Mixture MDPs (NeurIPS 2026 · similarity 0.90)
- Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL (NeurIPS 2025 · similarity 0.90)
- Model-based Reinforcement Learning for Confounded POMDPs (ICML 2024 · similarity 0.89)
- Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPs (ICLR 2025 · similarity 0.89)
- Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsight (ICLR 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.