mlsanityData to 7 Oct 2026

Reinforcement Learning of POMDPs using Spectral Methods

arXiv 1602.07764 ↗First posted 25 Feb 2016cs.AI cs.LG cs.NAcited by 51

Not on the map. Why?

Abstract (arXiv)

We propose a new reinforcement learning algorithm for partially observable Markov decision processes (POMDP) based on spectral decomposition methods. While spectral methods have been previously employed for consistent learning of (passive) latent variable models such as hidden Markov models, POMDPs are more challenging since the learner interacts with the environment and possibly changes the future observations in the process. We devise a learning algorithm running through episodes, in each episode we employ spectral techniques to learn the POMDP parameters from a trajectory generated by a fixed policy. At the end of the episode, an optimization oracle returns the optimal memoryless planning policy which maximizes the expected reward based on the estimated POMDP model. We prove an order-optimal regret bound with respect to the optimal memoryless policy and efficient scaling with respect to the dimensionality of observation and action spaces.

Key facts. Cited by 51 papers in the map (data through 7 Oct 2026). First posted on arXiv 25 Feb 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 17; 2023: 9; 2024: 7; 2025: 6; 2026: 3.

51 papers.

Sort:

By area:

  1. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  2. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
  3. 2021Exploration in Deep Reinforcement Learning: From Single-Agent to Multiagent Domaincited by 57
  4. 2022PAC Reinforcement Learning for Predictive State Representationscited by 42
  5. 2021Proximal Reinforcement Learning: Efficient Off-Policy Evaluation in Partially Observed Markov Decision Processescited by 40
  6. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  7. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  8. 2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 26
  9. 2022Planning in Observable POMDPs in Quasipolynomial Timecited by 25
  10. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  11. 2022Future-Dependent Value-Based Off-Policy Evaluation in POMDPscited by 20
  12. 2022An Instrumental Variable Approach to Confounded Off-Policy Evaluationcited by 20
38 more
  1. 2021Sublinear Regret for Learning POMDPscited by 19
  2. 2022Policy Optimization with Linear Temporal Logic Constraintscited by 19
  3. 2022Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limitscited by 17
  4. 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 17
  5. 2022Tensor and Matrix Low-Rank Value-Function Approximation in Reinforcement Learningcited by 16
  6. 2022Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiencycited by 16
  7. 2021Reinforcement Learning in Reward-Mixing MDPscited by 15
  8. 2022Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiencycited by 15
  9. 2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
  10. 2023Provable Representation with Efficient Planning for Partial Observable Reinforcement Learningcited by 10
  11. 2024On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluationcited by 9
  12. 2023Faster Robust Tensor Power Method for Arbitrary Ordercited by 8
  13. 2023Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDPcited by 8
  14. 2021Model based Multi-agent Reinforcement Learning with Tensor Decompositionscited by 7
  15. 2023Offline RL with Observation Histories: Analyzing and Improving Sample Complexitycited by 7
  16. 2025Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPscited by 7
  17. 2021Explore and Control with Adversarial Surprisecited by 6
  18. 2023Provably Efficient UCB-type Algorithms For Learning Predictive State Representationscited by 6
  19. 2022Reward-Mixing MDPs with a Few Latent Contexts are Learnablecited by 5
  20. 2024RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluationcited by 5
  21. 2025Scalable Policy-Based RL Algorithms for POMDPscited by 4
  22. 2022Tractable Optimality in Episodic Latent MABscited by 3
  23. 2024Near-Optimal Learning and Planning in Separated Latent MDPscited by 3
  24. 2025Multilinear Tensor Low-Rank Approximation for Policy-Gradient Methods in Reinforcement Learningcited by 3
  25. 2023Representations and Exploration for Deep Reinforcement Learning using Singular Value Decompositioncited by 2
  26. 2024Tractable Offline Learning of Regular Decision Processescited by 2
  27. 2021Optimization Algorithm for Feedback and Feedforward Policies towards Robot Control Robust to Sensing Failurescited by 1
  28. 2021Dynamic programming with incomplete information to overcome navigational uncertainty in a nautical environmentcited by 1
  29. 2024Track-MDP: Reinforcement Learning for Target Tracking with Controlled Sensingcited by 1
  30. 2024Solving Truly Massive Budgeted Monotonic POMDPs with Oracle-Guided Meta-Reinforcement Learningcited by 1
  31. 2024Efficient Learning of POMDPs with Known Observation Model in Average-Reward Settingcited by 1
  32. 2025Near-Optimal Clustering in Mixture of Markov Chainscited by 1
  33. 2026Toward Learning POMDPs Beyond Full-Rank Actions and State Observabilitycited by 1
  34. 2023Learning Optimal Admission Control in Partially Observable Queueing Networkscited by 0
  35. 2023Posterior Sampling-based Online Learning for Episodic POMDPscited by 0
  36. 2025Achieving widetildeO(√T) Regret in Average-Reward POMDPs with Known Observation Modelscited by 0
  37. 2025Memoryless Policy Iteration for Episodic POMDPscited by 0
  38. 2026Adaptive Exploration for Latent-State Banditscited by 0

50 most cited of 51 All 51 (JSON)