# Online Regret Bounds for Undiscounted Continuous Reinforcement Learning

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Feb 2013.

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

- [A Survey of Exploration Methods in Reinforcement Learning](https://mlsanity.com/paper/2109.00157/) (2021)
- [Sublinear Regret for Learning POMDPs](https://mlsanity.com/paper/2107.03635/) (2021)
- [Learning to Control Linear Systems can be Hard](https://mlsanity.com/paper/2205.14035/) (2022)
- [No-Regret Reinforcement Learning in Smooth MDPs](https://mlsanity.com/paper/2402.03792/) (2024)
- [Augmented RBMLE-UCB Approach for Adaptive Control of Linear Quadratic Systems](https://mlsanity.com/paper/2201.10542/) (2022)
- [Autoregressive Bandits](https://mlsanity.com/paper/2212.06251/) (2022)
- [Coarse-Grained Smoothness for RL in Metric Spaces](https://mlsanity.com/paper/2110.12276/) (2021)
- [Preferences Evolve And So Should Your Bandits: Bandits with Evolving States for Online Platforms](https://mlsanity.com/paper/2307.11655/) (2023)
- [Multi-Agent Probabilistic Ensembles with Trajectory Sampling for Connected Autonomous Vehicles](https://mlsanity.com/paper/2312.13910/) (2023)
- [Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2405.18793/) (2024)
- [Efficient Learning of POMDPs with Known Observation Model in Average-Reward Setting](https://mlsanity.com/paper/2410.01331/) (2024)
- [Safe Learning Under Irreversible Dynamics via Asking for Help](https://mlsanity.com/paper/2502.14043/) (2025)
- [A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model](https://mlsanity.com/paper/2507.22854/) (2025)
- [Fundamental Limits of Reinforcement Learning in Environment with Endogeneous and Exogeneous Uncertainty](https://mlsanity.com/paper/2106.08477/) (2021)
- [Provably Adaptive Average Reward Reinforcement Learning for Metric Spaces](https://mlsanity.com/paper/2410.19919/) (2024)
- [Achieving widetildeO(√T) Regret in Average-Reward POMDPs with Known Observation Models](https://mlsanity.com/paper/2501.18790/) (2025)
- [DyBBT: Dynamic Balance via Bandit-inspired Targeting for Dialog Policy with Cognitive Dual-Systems](https://mlsanity.com/paper/2509.19695/) (2025)

## Abstract (arXiv)

We derive sublinear regret bounds for undiscounted reinforcement learning in continuous state space. The proposed algorithm combines state aggregation with the use of upper confidence bounds for implementing optimism in the face of uncertainty. Beside the existence of an optimal policy which satisfies the Poisson equation, the only assumptions made are Holder continuity of rewards and transition probabilities.