Sample Complexity Reduction via Policy Difference Estimation in Tabular Reinforcement Learning
On the map: Deep reinforcement learning methods → RL theory and sample complexity
Abstract (arXiv)
In this paper, we study the non-asymptotic sample complexity for the pure exploration problem in contextual bandits and tabular reinforcement learning (RL): identifying an epsilon-optimal policy from a set of policies with high probability. Existing work in bandits has shown that it is possible to identify the best policy by estimating only the difference between the behaviors of individual policies, which can be substantially cheaper than estimating the behavior of each policy directly. However, the best-known complexities in RL fail to take advantage of this and instead estimate the behavior of each policy directly. Does it suffice to estimate only the differences in the behaviors of policies in RL? We answer this question positively for contextual bandits but in the negative for tabular RL, showing a separation between contextual bandits and RL. However, inspired by this, we show that it almost suffices to estimate only the differences in RL: if we can estimate the behavior of a single reference policy, it suffices to only estimate how any other policy deviates from this reference policy. We develop an algorithm which instantiates this principle and obtains, to the best of our knowledge, the tightest known bound on the sample complexity of tabular RL.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 6 of its 51 references that are in the map. First posted on arXiv 11 Jun 2024.
Builds on
6 of 51 references.
References · 6
- 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
- 2018Exploration in Structured Reinforcement Learningcited by 34
- 2024Offline Multi-task Transfer RL with Representational Penalizationcited by 14
- 2022Asymptotic Instance-Optimal Algorithms for Interactive Decision Makingcited by 7
- 2023Towards Instance-Optimality in Online PAC Reinforcement Learningcited by 7
- 2023Initializing Services in Interactive ML Systems for Diverse Userscited by 5
Built on by
Citing papers per year: 2025: 1; 2026: 2.
3 papers.
- 2026Eluder dimension: localise it!cited by 3
- 2025Policy Testing in Markov Decision Processescited by 2
- 2026Pure Exploration for a Good Policy in Reinforcement Learning with Bandit Feedbackcited by 0
- 2026Pure Exploration for a Good Policy in Reinforcement Learning with Bandit Feedback22 May 2026
- 2026Eluder dimension: localise it!14 Jan 2026
- 2025Policy Testing in Markov Decision Processes21 May 2025
Similar, not cited
Close in wording, no citation either way
- 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
- 2026Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning
- 2021Importance of Empirical Sample Complexity Analysis for Offline Reinforcement Learning
- 2024Model-Free Active Exploration in Reinforcement Learning
- 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples
- 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
- 2026Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation
- 2023Offline Policy Evaluation for Reinforcement Learning with Adaptively Collected Data