The DOI matches its DataCite record.
PAC Reinforcement Learning with Rich Observations
Open accessAbstract
We propose and study a new model for reinforcement learning with rich observations, generalizing contextual bandits to sequential decision making. These models require an agent to take actions based on observations (features) with the goal of achieving long-term performance competitive with a large set of policies. To avoid barriers to sample-efficient learning associated with large observation spaces and general POMDPs, we focus on problems that can be summarized by a small number of hidden states and have long-term rewards that are predictable by a reactive function class. In this setting, we design and analyze a new reinforcement learning algorithm, Least Squares Value Elimination by Exploration. We prove that the algorithm learns near optimal behavior after a number of episodes that is polynomial in all relevant parameters, logarithmic in the number of policies, and independent of the size of the observation space. Our result provides theoretical justification for reinforcement learning with function approximation.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Partially observable MDPs are widely studied.
“Partially observable MDPs are widely studied (Papadimitriou and Tsitsiklis, 1987; Vlassis et al., 2012; Krishnamurthy et al., 2016; Tennenholtz et al., 2020; Xiong et al., 2022).”
From Reinforcement Learning with History-Dependent Dynamic Contexts (2023) · cites this paper as Krishnamurthy et al., 2016
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
No references could be resolved yet.
Research works printed but not linked: 19
- [1][1] Alekh Agarwal, Miroslav Dud´ ık, Satyen Kale, John Langford, and Robert E Schapire. Contextual bandit learning with predictable rewards. In AISTATS , 2012. -
- [4][4] Kamyar Azizzadenesheli, Alessandro Lazaric, and Animashree Anandkumar. Reinforcement learning of POMDPs using spectral methods. In COLT , 2016. -
- [5][5] Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In ICML , 1995. -
- [6][6] Ronen I Brafman and Moshe Tennenholtz. R-max - a general polynomial time algorithm for nearoptimal reinforcement learning. JMLR , 2003. -
- [7][7] Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforcement learning. In NIPS , 2015. -
- [8][8] Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang. Efficient optimal learning for contextual bandits. In UAI , 2011. -
- [9][9] Nan Jiang, Alex Kulesza, and Satinder Singh. Abstraction selection in model-based reinforcement learning. In ICML , 2015. -
- [11][11] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In ICML , 2002. -
- [12][12] Sham Kakade, Michael J Kearns, and John Langford. Exploration in metric state spaces. In ICML , 2003. -
- [14][14] Michael J Kearns, Yishay Mansour, and Andrew Y Ng. Approximate planning in large POMDPs via reusable trajectories. In NIPS , 1999. -
- [16][16] John Langford and Tong Zhang. The epoch-greedy algorithm for multi-armed bandits with side information. In NIPS , 2008. -
- [19][19] Yishay Mansour. Reinforcement learning and mistake bounded algorithms. In COLT , 1999. -
- [20][20] Nicolas Meuleau, Leonid Peshkin, Kee-Eung Kim, and Leslie Pack Kaelbling. Learning finite-state controllers for partially observable environments. In UAI , 1999. -
- [22][22] Phuong Nguyen, Odalric-Ambrym Maillard, Daniil Ryabko, and Ronald Ortner. Competing with an infinite set of models in reinforcement learning. In AISTATS , 2013. -
- [23][23] Jason Pazis and Ronald Parr. Efficient PAC-optimal exploration in concurrent, continuous state MDPs with delayed updates. In AAAI , 2016. -
- [24][24] Theodore J Perkins and Doina Precup. A convergent form of approximate policy iteration. In NIPS , 2002. -
- [26][26] Alexander L Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L Littman. PAC modelfree reinforcement learning. In ICML , 2006. -
- [27][27] Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In NIPS , 1999. -
- [28][28] John N Tsitsiklis and Benjamin Van Roy. An analysis of temporal-difference learning with function approximation. IEEE TAC , 1997.
Cited by
Sorted by citations
Reinforcement Learning with History-Dependent Dynamic Contexts
Tennenholtz, G., Merlis, N., Shani, L., Mladenov, M., & Boutilier, C. (2023) · arXiv · doi:10.48550/arxiv.2302.02061
Metadata
- Authors
- Krishnamurthy, A., Agarwal, A., & Langford, J.
- Affiliations
- University of Massachusetts Amherst (US)
- Microsoft Research New York City (United States) (US)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2016
- Volume
- 29
- Pages
- 1848-1856
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1602.02722
- OpenAlex
- W2542999299
- Cited by
- 13
- References
- 0
- Citations by year
- 2025: 2 · 2024: 2 · 2023: 1 · 2022: 1 · 2021: 2 · 2020: 1 · 2018: 1 · 2017: 2 · 2016: 1
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- neural information processing systems
- Funders
- Microsoft Research
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
- Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Bandit Algorithms Research
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
- Keywords
- contextual bandits, sequential decision making, function approximation, sample efficiency, hidden states
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
