# Online Reinforcement Learning with Uncertain Episode Lengths

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 30 references that are in the map.
- First posted on arXiv 7 Feb 2023.

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

- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [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)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Hyperbolic Discounting and Learning over Multiple Horizons](https://mlsanity.com/paper/1902.06865/) (2019)
- [Near-optimal Regret Bounds for Stochastic Shortest Path](https://mlsanity.com/paper/2002.09869/) (2020)
- [Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition](https://mlsanity.com/paper/2006.05606/) (2020)
- [Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs](https://mlsanity.com/paper/2010.00587/) (2020)
- [Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret](https://mlsanity.com/paper/2104.11186/) (2021)
- [Rethinking the Discount Factor in Reinforcement Learning: A Decision Theoretic Approach](https://mlsanity.com/paper/1902.02893/) (2019)
- [Minimax Regret for Stochastic Shortest Path](https://mlsanity.com/paper/2103.13056/) (2021)

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

- [The Courage to Stop: Overcoming Sunk Cost Fallacy in Deep Reinforcement Learning](https://mlsanity.com/paper/2506.13672/) (2025)
- [Reinforcement Learning with Random Time Horizons](https://mlsanity.com/paper/2506.00962/) (2025)
- [OPTWIN: Drift identification with optimal sub-windows](https://mlsanity.com/paper/2305.11942/) (2023)
- [Reinforcement Learning with Action-Triggered Observations](https://mlsanity.com/paper/2510.02149/) (2025)

## Abstract (arXiv)

Existing episodic reinforcement algorithms assume that the length of an episode is fixed across time and known a priori. In this paper, we consider a general framework of episodic reinforcement learning when the length of each episode is drawn from a distribution. We first establish that this problem is equivalent to online reinforcement learning with general discounting where the learner is trying to optimize the expected discounted sum of rewards over an infinite horizon, but where the discounting function is not necessarily geometric. We show that minimizing regret with this new general discounting is equivalent to minimizing regret with uncertain episode lengths. We then design a reinforcement learning algorithm that minimizes regret with general discounting but acts for the setting with uncertain episode lengths. We instantiate our general bound for different types of discounting, including geometric and polynomial discounting. We also show that we can obtain similar regret bounds even when the uncertainty over the episode lengths is unknown, by estimating the unknown distribution over time. Finally, we compare our learning algorithms with existing value-iteration based episodic RL algorithms in a grid-world environment.