Partially Observable RL With B-stability: Unified Structural Condition And Sharp Sample-efficient Algorithms

Abstract

Partial Observability -- where agents can only observe partial information about the true underlying state of the system -- is ubiquitous in real-world applications of Reinforcement Learning (RL). Theoretically, learning a near-optimal policy under partial observability is known to be hard in the worst case due to an exponential sample complexity lower bound. Recent work has identified several tractable subclasses that are learnable with polynomial samples, such as Partially Observable Markov Decision Processes (POMDPs) with certain revealing or decodability conditions. However, this line of research is still in its infancy, where (1) unified structural conditions enabling sample-efficient learning are lacking; (2) existing sample complexities for known tractable subclasses are far from sharp; and (3) fewer sample-efficient algorithms are available than in fully observable RL. This paper advances all three aspects above for Partially Observable RL in the general setting of Predictive

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keychen2022partially

Related papers

• Pessimism In The Face Of Confounders: Provably Efficient Offline Reinforcement Learning In Partially Observable Markov Decision Processes (2022)0.00
• Provably Efficient Reinforcement Learning In Partially Observable Dynamical Systems (2022)0.00
• Provable Partially Observable Reinforcement Learning With Privileged Information (2024)2.26
• Sample-efficient Reinforcement Learning Of Partially Observable Markov Games (2022)0.00
• Reinforcement Learning Under Partial Observability Guided By Learned Environment Models (2022)6.34
• Provable Representation With Efficient Planning For Partial Observable Reinforcement Learning (2023)0.00
• Near-optimal Partially Observable Reinforcement Learning With Partial Online State Information (2023)0.00
• Benchmarking Partial Observability In Reinforcement Learning With A Suite Of Memory-improvable Domains (2025)0.00