Prospective Side Information for Latent MDPs
Not on the map. Why?
Abstract (arXiv)
In many interactive decision-making settings, there is latent and unobserved information that remains fixed. Consider, for example, a dialogue system, where complete information about a user, such as the user's preferences, is not given. In such an environment, the latent information remains fixed throughout each episode, since the identity of the user does not change during an interaction. This type of environment can be modeled as a Latent Markov Decision Process (LMDP), a special instance of Partially Observed Markov Decision Processes (POMDPs). Previous work established exponential lower bounds in the number of latent contexts for the LMDP class. This puts forward a question: under which natural assumptions a near-optimal policy of an LMDP can be efficiently learned? In this work, we study the class of LMDPs with em prospective side information, when an agent receives additional, weakly revealing, information on the latent context at the beginning of each episode. We show that, surprisingly, this problem is not captured by contemporary settings and algorithms designed for partially observed environments. We then establish that any sample efficient algorithm must suffer at least Omega(K2/3)-regret, as opposed to standard Omega(√K) lower bounds, and design an algorithm with a matching upper bound.
Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 21 of its 38 references that are in the map. First posted on arXiv 11 Oct 2023.
Builds on
21 of 38 references.
References · 21
- 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
- 2015Contextual Markov Decision Processescited by 213
- 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
- 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
- 2016Explore First, Exploit Next: The True Shape of Regret in Bandit Problemscited by 78
- 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
- 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
- 2013Sample Complexity of Multi-task Reinforcement Learningcited by 58
- 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
- 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
- 2016On Context-Dependent Clustering of Banditscited by 43
- 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
9 more
- 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
- 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
- 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
- 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 17
- 2023Lower Bounds for Learning in Revealing POMDPscited by 14
- 2023Provably Efficient UCB-type Algorithms For Learning Predictive State Representationscited by 6
- 2022Reward-Mixing MDPs with a Few Latent Contexts are Learnablecited by 5
- 2022Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanismscited by 4
- 2022Tractable Optimality in Episodic Latent MABscited by 3
Built on by
Citing papers per year: 2024: 2; 2025: 2.
4 papers.