# Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs

November 27, 2022

## Abstract

In probably approximately correct (PAC) reinforcement learning (RL), an agent is required to identify an $\epsilon$-optimal policy with probability $1-\delta$. While minimax optimal algorithms exist for this problem, its instance-dependent complexity remains elusive in episodic Markov decision processes (MDPs). In this paper, we propose the first nearly matching (up to a horizon squared factor and logarithmic terms) upper and lower bounds on the sample complexity of PAC RL in deterministic episodic MDPs with finite state and action spaces. In particular, our bounds feature a new notion of sub-optimality gap for state-action pairs that we call the deterministic return gap. While our instance-dependent lower bound is written as a linear program, our algorithms are very simple and do not require solving such an optimization problem during learning. Their design and analyses employ novel ideas, including graph-theoretical concepts (minimum flows) and a new maximum-coverage exploration strategy.

#### AUTHORS

Written by

Andrea Tirinzoni

Aymen Al Marjani

Emilie Kaufmann

Publisher

NeurIPS

Research Topics

Reinforcement Learning

### Related Publications

November 28, 2022

#### Neural Attentive Circuits

Nicolas Ballas, Bernhard Schölkopf, Chris Pal, Francesco Locatello, Li Erran, Martin Weiss, Nasim Rahaman, Yoshua Bengio

November 28, 2022

November 16, 2022

#### Memorization Without Overfitting: Analyzing the Training Dynamics of Large Language Models

Kushal Tirumala, Aram H. Markosyan, Armen Aghajanyan, Luke Zettlemoyer

November 16, 2022

November 10, 2022

#### Learning State-Aware Visual Representations from Audible Interactions

Unnat Jain, Abhinav Gupta, Himangi Mittal, Pedro Morgado

November 10, 2022

November 09, 2022

#### VisCo Grids: Surface Reconstruction with Viscosity and Coarea Grids

Yaron Lipman, Albert Pumarola, Ali Thabet, Artsiom Sanakoyeu, Lior Yariv

November 09, 2022

Tools

Research

Blog

People