mlsanityData to 7 Oct 2026

Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency

arXiv 2204.09787 ↗First posted 20 Apr 2022cs.LG math.OC stat.MLcited by 15

Not on the map. Why?

Abstract (arXiv)

We study reinforcement learning for partially observed Markov decision processes (POMDPs) with infinite observation and state spaces, which remains less investigated theoretically. To this end, we make the first attempt at bridging partial observability and function approximation for a class of POMDPs with a linear structure. In detail, we propose a reinforcement learning algorithm (Optimistic Exploration via Adversarial Integral Equation or OP-TENET) that attains an ε-optimal policy within O(1/ε2) episodes. In particular, the sample complexity scales polynomially in the intrinsic dimension of the linear structure and is independent of the size of the observation and state spaces. The sample efficiency of OP-TENET is enabled by a sequence of ingredients: (i) a Bellman operator with finite memory, which represents the value function in a recursive manner, (ii) the identification and estimation of such an operator via an adversarial integral equation, which features a smoothed discriminator tailored to the linear structure, and (iii) the exploration of the observation and state spaces via optimism, which is based on quantifying the uncertainty in the adversarial integral equation.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). Builds on 24 of its 41 references that are in the map. First posted on arXiv 20 Apr 2022.

Builds on

24 of 41 references.

References · 24

  1. 2019Dota 2 with Large Scale Deep Reinforcement Learningcited by 1,084
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  6. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  7. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  8. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  9. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  10. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  11. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
  12. 2020Information Theoretic Regret Bounds for Online Nonlinear Controlcited by 87
12 more
  1. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
  2. 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
  3. 2016Reinforcement Learning of POMDPs using Spectral Methodscited by 51
  4. 2019AlphaStar: An Evolutionary Computation Perspectivecited by 50
  5. 2021Causal Inference Under Unmeasured Confounding With Negative Controls: A Minimax Learning Approachcited by 43
  6. 2021Proximal Reinforcement Learning: Efficient Off-Policy Evaluation in Partially Observed Markov Decision Processescited by 40
  7. 2016A PAC RL Algorithm for Episodic POMDPscited by 37
  8. 2022Planning in Observable POMDPs in Quasipolynomial Timecited by 25
  9. 2021Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recallcited by 21
  10. 2021A Spectral Approach to Off-Policy Evaluation for POMDPscited by 20
  11. 2021Sublinear Regret for Learning POMDPscited by 19
  12. 2020A Selective Review of Negative Control Methods in Epidemiologycited by 15

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 4; 2023: 6; 2024: 2; 2025: 2; 2026: 1.

15 papers.

Sort:

By area:

  1. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  2. 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 17
  3. 2023Lower Bounds for Learning in Revealing POMDPscited by 14
  4. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
  5. 2023Partially Observable Mean Field Multi-Agent Reinforcement Learning Based on Graph-Attentioncited by 7
  6. 2022Optimistic MLE -- A Generic Model-based Algorithm for Partially Observable Sequential Decision Makingcited by 6
  7. 2022Reward-Mixing MDPs with a Few Latent Contexts are Learnablecited by 5
  8. 2023Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsightcited by 3
  9. 2025Reinforcement Learning with Continuous Actions Under Unmeasured Confoundingcited by 3
  10. 2023Policy Evaluation in Decentralized POMDPs with Belief Sharingcited by 1
  11. 2024A Theoretical Framework for Partially Observed Reward-States in RLHFcited by 1
  12. 2025Reinforcement Learning with Action-Triggered Observationscited by 1
3 more
  1. 2023Near-Optimal Partially Observable Reinforcement Learning with Partial Online State Informationcited by 0
  2. 2024Provably Efficient Partially Observable Risk-Sensitive Reinforcement Learning with Hindsight Observationcited by 0
  3. 2026Reinforcement Learning with Function Approximation for Non-Markov Processescited by 0