Beyond No Regret: Instance-Dependent PAC Reinforcement Learning

2021-08-05 · Andrew Wagenmaker, Max Simchowitz, Kevin Jamieson

The theory of reinforcement learning has focused on two fundamental problems: achieving low regret, and identifying $\epsilon$-optimal policies. While a simple reduction allows one to apply a low-regret algorithm to obtain an $\epsilon$-optimal policy and achieve the worst-case optimal rate, it is unknown whether low-regret algorithms can obtain the instance-optimal rate for policy identification. We show this is not possible -- there exists a fundamental tradeoff between achieving low regret and identifying an $\epsilon$-optimal policy at the instance-optimal rate. Motivated by our negative finding, we propose a new measure of instance-dependent sample complexity for PAC tabular reinforcement learning which explicitly accounts for the attainable state visitation distributions in the underlying MDP. We then propose and analyze a novel, planning-based algorithm which attains this sample complexity -- yielding a complexity which scales with the suboptimality gaps and the "reachability" of a state. We show our algorithm is nearly minimax optimal, and on several examples that our instance-dependent sample complexity offers significant improvements over worst-case bounds.

📄 PDF Abstract BibTeX arXiv:2108.02717

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Tail Distribution of Regret in Optimistic Reinforcement Learning

2025-11-23 · Sajad Khodadadian, Mehrdad Moharrami arxiv

We derive instance-dependent tail bounds for the regret of optimism-based reinforcement learning in finite-horizon tabular Markov decision processes with unknown transition dynamics. We first study a UCBVI-type (model-ba…

Reinforcement Learning

Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning

2021-07-02 · NeurIPS 2021 12 · Christoph Dann, Teodor V. Marinov, Mehryar Mohri, Julian Zimmert

We provide improved gap-dependent regret bounds for reinforcement learning in finite episodic Markov decision processes. Compared to prior work, our bounds depend on alternative definitions of gaps. These definitions are…

reinforcement-learning Reinforcement Learning (RL)

Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective

2020-10-07 · Dylan J. Foster, Alexander Rakhlin, David Simchi-Levi, Yunzong Xu

In the classical multi-armed bandit problem, instance-dependent algorithms attain improved performance on "easy" problems with a gap between the best and second-best arm. Are similar guarantees possible for contextual ba…

Active Learning Multi-Armed Bandits reinforcement-learning Reinforcement Learning+1

Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function Approximation

2023-12-07 · Jiayi Huang, Han Zhong, LiWei Wang, Lin F. Yang

To tackle long planning horizon problems in reinforcement learning with general function approximation, we propose the first algorithm, termed as UCRL-WVTR, that achieves both \emph{horizon-free} and \emph{instance-depen…

regression

Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning

2026-05-06 · Harin Lee, Min-hwan Oh arxiv

We study the distribution of regret in stochastic multi-armed bandits and episodic reinforcement learning through a unified framework. We formalize a distributional regret bound as a probabilistic guarantee that holds un…

Reinforcement Learning Multi-Armed Bandits