Research map / Bandits and online learning / RL theory and MDPs
Prospective Side Information for Latent MDPs
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.
Studies latent MDPs where a weakly revealing side signal about the latent context is given at the start of each episode (LMDP-Ψ), proving an Ω(K^{2/3}) regret lower bound and an matching poly(M)K^{2/3} upper bound via pure exploration over blind policies.
Problem
Learning near-optimal policies in latent MDPs when prospective side information on the latent context is available at the start of each episode; standard sqrt(K) regret is not achievable in the stronger sense of regret against the side-information-aware optimal policy.
Approach
Shows that prospective side information breaks the standard weakly-revealing POMDP assumptions (observations correlated across time given latent state), proves a K^{2/3} lower bound against the side-info-aware optimal policy, and gives an explore-then-exploit algorithm that explores with blind policies using a PSR-based termination/bonus criterion, achieving K^{2/3} regret without exponential depe
Key results
- Lower bound: any algorithm suffers min(A^{Omega(M)} sqrt(K), poly(A, 1/alpha) K^{2/3}) regret for LMDP-Psi, showing sqrt(K) is not achievable in general.
- Upper bound: explore-then-exploit with pure exploration over blind policies achieves regret roughly (M^8 H^4 SA log(|Theta|/delta)/alpha^6)^{1/3} K^{2/3}.
- Warm-up: O-MLE over blind policies achieves O(sqrt(K)) regret against the best blind policy, but not against the side-information-aware optimal policy.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Allow policies to use weakly revealing prospective side information instead of restricting them to blind policies | LMDP learning · LMDP with α-prospective SI | regret rate: \sqrt{K} -> K^{2/3} | Hurt |
| Use pure exploration over blind policies, then exploit the learned model | LMDP-$\Psi$ · LMDP with α-prospective SI | regret upper bound: O(K^{2/3}) | Helped |
| Restrict the policy class to policies that ignore prospective side information | LMDP-$\Psi$ · LMDP with α-prospective SI, blind policy class | regret rate: \sqrt{K} | Helped |
Surprising findings
- Achieving sqrt(K) regret against the side-information-aware optimal policy is impossible in general unless K exceeds A^{Omega(M)}, despite sqrt(K) being achievable against blind policies.
- LMDP-Psi falls outside the weakly revealing POMDP class because observations are correlated across time steps given the latent state.
Limitations
- Upper bound has large polynomial dependence (M^8 H^4 / alpha^6) and is not tight in these factors.
- Assumes finite (possibly exponentially large) model class and discrete observations; continuous case only sketched.
- Results are theoretical with no empirical evaluation.
Experimental setup
Metrics: regret sample complexity
Baselines: O-MLE weakly revealing POMDP algorithms
Builds on: Optimistic-MLE well-conditioned PSR weakly revealing POMDP latent MDP sample complexity lower bounds
Closest papers by meaning
- RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation (NeurIPS 2024 · similarity 0.91)
- Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsight (ICLR 2024 · similarity 0.85)
- Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs (NeurIPS 2024 · similarity 0.85)
- Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs (NeurIPS 2025 · similarity 0.84)
- Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability (NeurIPS 2024 · similarity 0.84)
- Logarithmic Smoothing for Pessimistic Off-Policy Evaluation, Selection and Learning (NeurIPS 2024 · similarity 0.84)
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.