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

arXiv: https://arxiv.org/abs/2204.09787 · HTML: https://mlsanity.com/paper/2204.09787/

## Key facts

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

## Builds on (most cited first, 24 of 24)

- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Generalization and Exploration via Randomized Value Functions](https://mlsanity.com/paper/1402.0635/) (2014)
- [PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning](https://mlsanity.com/paper/2007.08459/) (2020)
- [Information Theoretic Regret Bounds for Online Nonlinear Control](https://mlsanity.com/paper/2006.12466/) (2020)
- [RL for Latent MDPs: Regret Guarantees and a Lower Bound](https://mlsanity.com/paper/2102.04939/) (2021)
- [Sample-Efficient Reinforcement Learning of Undercomplete POMDPs](https://mlsanity.com/paper/2006.12484/) (2020)
- [Reinforcement Learning of POMDPs using Spectral Methods](https://mlsanity.com/paper/1602.07764/) (2016)
- [AlphaStar: An Evolutionary Computation Perspective](https://mlsanity.com/paper/1902.01724/) (2019)
- [Causal Inference Under Unmeasured Confounding With Negative Controls: A Minimax Learning Approach](https://mlsanity.com/paper/2103.14029/) (2021)
- [Proximal Reinforcement Learning: Efficient Off-Policy Evaluation in Partially Observed Markov Decision Processes](https://mlsanity.com/paper/2110.15332/) (2021)
- [A PAC RL Algorithm for Episodic POMDPs](https://mlsanity.com/paper/1605.08062/) (2016)
- [Planning in Observable POMDPs in Quasipolynomial Time](https://mlsanity.com/paper/2201.04735/) (2022)
- [Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recall](https://mlsanity.com/paper/2106.06279/) (2021)
- [A Spectral Approach to Off-Policy Evaluation for POMDPs](https://mlsanity.com/paper/2109.10502/) (2021)
- [Sublinear Regret for Learning POMDPs](https://mlsanity.com/paper/2107.03635/) (2021)
- [A Selective Review of Negative Control Methods in Epidemiology](https://mlsanity.com/paper/2009.05641/) (2020)

## Built on by (most cited first, 16 of 16)

- [Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithms](https://mlsanity.com/paper/2209.14990/) (2022)
- [Learning in POMDPs is Sample-Efficient with Hindsight Observability](https://mlsanity.com/paper/2301.13857/) (2023)
- [Lower Bounds for Learning in Revealing POMDPs](https://mlsanity.com/paper/2302.01333/) (2023)
- [Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient](https://mlsanity.com/paper/2210.00750/) (2022)
- [Partially Observable Mean Field Multi-Agent Reinforcement Learning Based on Graph-Attention](https://mlsanity.com/paper/2304.12653/) (2023)
- [Optimistic MLE -- A Generic Model-based Algorithm for Partially Observable Sequential Decision Making](https://mlsanity.com/paper/2209.14997/) (2022)
- [Reward-Mixing MDPs with a Few Latent Contexts are Learnable](https://mlsanity.com/paper/2210.02594/) (2022)
- [Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsight](https://mlsanity.com/paper/2307.02884/) (2023)
- [Reinforcement Learning with Continuous Actions Under Unmeasured Confounding](https://mlsanity.com/paper/2505.00304/) (2025)
- [Policy Evaluation in Decentralized POMDPs with Belief Sharing](https://mlsanity.com/paper/2302.04151/) (2023)
- [A Theoretical Framework for Partially Observed Reward-States in RLHF](https://mlsanity.com/paper/2402.03282/) (2024)
- [Reinforcement Learning with Action-Triggered Observations](https://mlsanity.com/paper/2510.02149/) (2025)
- [Near-Optimal Partially Observable Reinforcement Learning with Partial Online State Information](https://mlsanity.com/paper/2306.08762/) (2023)
- [Provably Efficient Partially Observable Risk-Sensitive Reinforcement Learning with Hindsight Observation](https://mlsanity.com/paper/2402.18149/) (2024)
- [Learning POMDPs with Linear Function Approximation and Finite Memory](https://mlsanity.com/paper/2505.14879/) (2025)
- [Reinforcement Learning with Function Approximation for Non-Markov Processes](https://mlsanity.com/paper/2601.00151/) (2026)

## 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.