# Achieving widetildeO(√T) Regret in Average-Reward POMDPs with Known Observation Models

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 47 references that are in the map.
- First posted on arXiv 30 Jan 2025.

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

- [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)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [When Is Partially Observable Reinforcement Learning Not Scary?](https://mlsanity.com/paper/2204.08967/) (2022)
- [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)
- [A PAC RL Algorithm for Episodic POMDPs](https://mlsanity.com/paper/1605.08062/) (2016)
- [Partially Observed Markov Decision Processes. Problem Sets and Internet Supplement](https://mlsanity.com/paper/1604.08127/) (2016)
- [Virtual vs. Real: Trading Off Simulations and Physical Experiments in Reinforcement Learning with Bayesian Optimization](https://mlsanity.com/paper/1703.01250/) (2017)
- [Online Regret Bounds for Undiscounted Continuous Reinforcement Learning](https://mlsanity.com/paper/1302.2550/) (2013)
- [Online Learning for Unknown Partially Observable MDPs](https://mlsanity.com/paper/2102.12661/) (2021)
- [Lower Bounds for Learning in Revealing POMDPs](https://mlsanity.com/paper/2302.01333/) (2023)
- [Regime Switching Bandits](https://mlsanity.com/paper/2001.09390/) (2020)
- [Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism](https://mlsanity.com/paper/2011.00330/) (2020)
- [Efficient Learning of POMDPs with Known Observation Model in Average-Reward Setting](https://mlsanity.com/paper/2410.01331/) (2024)

## Abstract (arXiv)

We tackle average-reward infinite-horizon POMDPs with an unknown transition model but a known observation model, a setting that has been previously addressed in two limiting ways: (i) frequentist methods relying on suboptimal stochastic policies having a minimum probability of choosing each action, and (ii) Bayesian approaches employing the optimal policy class but requiring strong assumptions about the consistency of employed estimators. Our work removes these limitations by proving convenient estimation guarantees for the transition model and introducing an optimistic algorithm that leverages the optimal class of deterministic belief-based policies. We introduce modifications to existing estimation techniques providing theoretical guarantees separately for each estimated action transition matrix. Unlike existing estimation methods that are unable to use samples from different policies, we present a novel and simple estimator that overcomes this barrier. This new data-efficient technique, combined with the proposed Action-wise OAS-UCRL algorithm and a tighter theoretical analysis, leads to the first approach enjoying a regret guarantee of order O(√T ,log T) when compared against the optimal policy, thus improving over state of the art techniques. Finally, theoretical results are validated through numerical simulations showing the efficacy of our method against baseline methods.