mlsanityData to 14 Oct 2026

Near-Optimal Partially Observable Reinforcement Learning with Partial Online State Information

arXiv 2306.08762 ↗First posted 14 Jun 2023cs.LG cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

Partially observable Markov decision processes (POMDPs) are a general framework for sequential decision-making under latent state uncertainty, yet learning in POMDPs is intractable in the worst case. Motivated by sensing and probing constraints in practice, we study how much online state information (OSI) is sufficient to enable efficient learning guarantees. We formalize a model in which the learner can query only partial OSI (POSI) during interaction. We first prove an information-theoretic hardness result showing that, for general POMDPs, achieving an ε-optimal policy can require sample complexity that is exponential unless full OSI is available. We then identify two structured subclasses that remain learnable under POSI and propose corresponding algorithms with provably efficient performance guarantees. In particular, we establish regret upper bounds with tildeO(√K) dependence on the number of episodes K, together with complementary lower bounds, thereby delineating when POSI suffices for efficient reinforcement learning. Our results highlight a principled separation between intractable and tractable regimes under incomplete online state access and provide new tools for jointly optimizing POSI queries and learning control actions.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 27 of its 49 references that are in the map. First posted on arXiv 14 Jun 2023.

Builds on

27 of 49 references.

References · 27

  1. 2019Dota 2 with Large Scale Deep Reinforcement Learningcited by 1,103
  2. 2019Solving Rubik's Cube with a Robot Handcited by 734
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  4. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  5. 2018Is Q-learning Provably Efficient?cited by 487
  6. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  7. 2017Asymmetric Actor Critic for Image-Based Robot Learningcited by 238
  8. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  9. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  10. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 114
  11. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  12. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
15 more
  1. 2019Provably Efficient Q-Learning with Low Switching Costcited by 78
  2. 2020The AI Economist: Improving Equality and Productivity with AI-Driven Tax Policiescited by 75
  3. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 70
  4. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  5. 2016On Lower Bounds for Regret in Reinforcement Learningcited by 40
  6. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  7. 2022Hindsight Learning for MDPs with Exogenous Inputscited by 26
  8. 2022Planning in Observable POMDPs in Quasipolynomial Timecited by 25
  9. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  10. 2021Sublinear Regret for Learning POMDPscited by 19
  11. 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 18
  12. 2023A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraintscited by 17
  13. 2022Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiencycited by 16
  14. 2023Lower Bounds for Learning in Revealing POMDPscited by 15
  15. 2023Near-Optimal Adversarial Reinforcement Learning with Switching Costscited by 4

Built on by

Not cited yet.