# Posterior Sampling for Continuing Environments

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 23 references that are in the map.
- First posted on arXiv 29 Nov 2022.

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

- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Generalization and Exploration via Randomized Value Functions](https://mlsanity.com/paper/1402.0635/) (2014)
- [Sample Efficient Reinforcement Learning with REINFORCE](https://mlsanity.com/paper/2010.11364/) (2020)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [Learning Unknown Markov Decision Processes: A Thompson Sampling Approach](https://mlsanity.com/paper/1709.04570/) (2017)
- [Reinforcement Learning, Bit by Bit](https://mlsanity.com/paper/2103.04047/) (2021)
- [Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP](https://mlsanity.com/paper/1901.09311/) (2019)
- [Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent States](https://mlsanity.com/paper/2102.05261/) (2021)
- [Hypermodels for Exploration](https://mlsanity.com/paper/2006.07464/) (2020)
- [How to Discount Deep Reinforcement Learning: Towards New Dynamic Strategies](https://mlsanity.com/paper/1512.02011/) (2015)
- [Discounted Reinforcement Learning Is Not an Optimization Problem](https://mlsanity.com/paper/1910.02140/) (2019)

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

- [Toward Efficient Exploration by Large Language Model Agents](https://mlsanity.com/paper/2504.20997/) (2025)
- [The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective](https://mlsanity.com/paper/2501.15910/) (2025)
- [Learning a Fast Mixing Exogenous Block MDP using a Single Trajectory](https://mlsanity.com/paper/2410.03016/) (2024)
- [Concurrent Learning with Aggregated States via Randomized Least Squares Value Iteration](https://mlsanity.com/paper/2501.13394/) (2025)

## Abstract (arXiv)

We develop an extension of posterior sampling for reinforcement learning (PSRL) that is suited for a continuing agent-environment interface and integrates naturally into agent designs that scale to complex environments. The approach, continuing PSRL, maintains a statistically plausible model of the environment and follows a policy that maximizes expected γ-discounted return in that model. At each time, with probability 1-γ, the model is replaced by a sample from the posterior distribution over environments. For a choice of discount factor that suitably depends on the horizon T, we establish an tildeO(τ S √A T) bound on the Bayesian regret, where S is the number of environment states, A is the number of actions, and τ denotes the reward averaging time, which is a bound on the duration required to accurately estimate the average reward of any policy. Our work is the first to formalize and rigorously analyze the resampling approach with randomized exploration.