Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalities
Not on the map. Why?
Abstract (arXiv)
We study model-based reinforcement learning in an unknown finite communicating Markov decision process. We propose a simple algorithm that leverages a variance based confidence interval. We show that the proposed algorithm, UCRL-V, achieves the optimal regret tildeO(√DSAT) up to logarithmic factors, and so our work closes a gap with the lower bound without additional assumptions on the MDP. We perform experiments in a variety of environments that validates the theoretical bounds as well as prove UCRL-V to be better than the state-of-the-art algorithms.
Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). First posted on arXiv 27 May 2019.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 4; 2022: 1; 2023: 7; 2024: 2; 2025: 1.
15 papers.
Sort:
By area:
- 2021A Survey of Exploration Methods in Reinforcement Learningcited by 68
- 2021Tactical Optimism and Pessimism for Deep Reinforcement Learningcited by 55
- 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
- 2021Reinforcement Learning in Reward-Mixing MDPscited by 15
- 2021Communication Efficient Parallel Reinforcement Learningcited by 10
- 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
- 2023Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learningcited by 7
- 2023Quantum Computing Provides Exponential Regret Improvement in Episodic Reinforcement Learningcited by 6
- 2023Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learningcited by 5
- 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
- 2025Sample-Efficient Reinforcement Learning from Human Feedback via Information-Directed Samplingcited by 4
- 2023Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Spacecited by 2
- 2025Sample-Efficient Reinforcement Learning from Human Feedback via Information-Directed Sampling8 Feb 2025
- 2024Provably Adaptive Average Reward Reinforcement Learning for Metric Spaces25 Oct 2024
- 2024Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learning29 May 2024
- 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedback14 Nov 2023
- 2023Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learning30 Oct 2023
- 2023Learning Optimal Admission Control in Partially Observable Queueing Networks4 Aug 2023
- 2023Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learning15 Jun 2023
- 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewards9 Mar 2023
- 2023Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space21 Feb 2023
- 2023Quantum Computing Provides Exponential Regret Improvement in Episodic Reinforcement Learning16 Feb 2023
- 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation23 Jun 2022
- 2021Reinforcement Learning in Reward-Mixing MDPs7 Oct 2021
3 more
- 2021A Survey of Exploration Methods in Reinforcement Learningcited by 68
- 2021Tactical Optimism and Pessimism for Deep Reinforcement Learningcited by 55
- 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
- 2021Communication Efficient Parallel Reinforcement Learningcited by 10
- 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
- 2023Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learningcited by 7
- 2023Quantum Computing Provides Exponential Regret Improvement in Episodic Reinforcement Learningcited by 6
- 2023Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learningcited by 5
- 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
- 2023Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Spacecited by 2
- 2024Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learningcited by 1
- 2023Learning Optimal Admission Control in Partially Observable Queueing Networkscited by 0
12 most cited of 13 All 13 (JSON)
- 2024Provably Adaptive Average Reward Reinforcement Learning for Metric Spaces25 Oct 2024
- 2024Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learning29 May 2024
- 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedback14 Nov 2023
- 2023Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learning30 Oct 2023
- 2023Learning Optimal Admission Control in Partially Observable Queueing Networks4 Aug 2023
- 2023Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learning15 Jun 2023
- 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewards9 Mar 2023
- 2023Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space21 Feb 2023
- 2023Quantum Computing Provides Exponential Regret Improvement in Episodic Reinforcement Learning16 Feb 2023
- 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation23 Jun 2022
- 2021A Survey of Exploration Methods in Reinforcement Learning1 Sep 2021
- 2021Communication Efficient Parallel Reinforcement Learning22 Feb 2021
12 newest of 13 All 13 (JSON)