On Gap-dependent Bounds for Offline Reinforcement Learning

2022-06-01 · Xinqi Wang, Qiwen Cui, Simon S. Du

This paper presents a systematic study on gap-dependent sample complexity in offline reinforcement learning. Prior work showed when the density ratio between an optimal policy and the behavior policy is upper bounded (the optimal policy coverage assumption), then the agent can achieve an $O\left(\frac{1}{\epsilon^2}\right)$ rate, which is also minimax optimal. We show under the optimal policy coverage assumption, the rate can be improved to $O\left(\frac{1}{\epsilon}\right)$ when there is a positive sub-optimality gap in the optimal $Q$-function. Furthermore, we show when the visitation probabilities of the behavior policy are uniformly lower bounded for states where an optimal policy's visitation probabilities are positive (the uniform optimal policy coverage assumption), the sample complexity of identifying an optimal policy is independent of $\frac{1}{\epsilon}$. Lastly, we present nearly-matching lower bounds to complement our gap-dependent upper bounds.

📄 PDF Abstract BibTeX arXiv:2206.00177

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures

2025-01-03 · Ming Yin, Mengdi Wang, Yu-Xiang Wang

This article reviews the recent advances on the statistical foundation of reinforcement learning (RL) in the offline and low-adaptive settings. We will start by arguing why offline RL is the appropriate model for almost …

Offline RL Reinforcement Learning (RL)

On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation

2022-11-23 · Thanh Nguyen-Tang, Ming Yin, Sunil Gupta, Svetha Venkatesh 외

Sample-efficient offline reinforcement learning (RL) with linear function approximation has recently been studied extensively. Much of prior work has yielded the minimax-optimal bound of $\tilde{\mathcal{O}}(\frac{1}{\sq…

Offline RL reinforcement-learning Reinforcement Learning (RL)

Order-Optimal Instance-Dependent Bounds for Offline Reinforcement Learning with Preference Feedback

2024-06-18 · Zhirui Chen, Vincent Y. F. Tan

We consider offline reinforcement learning (RL) with preference feedback in which the implicit reward is a linear function of an unknown parameter. Given an offline dataset, our objective consists in ascertaining the opt…

Offline RL Reinforcement Learning (RL)

The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learning

2023-05-25 · NeurIPS 2023 11 · Kaiwen Wang, Kevin Zhou, Runzhe Wu, Nathan Kallus 외

While distributional reinforcement learning (DistRL) has been empirically effective, the question of when and why it is better than vanilla, non-distributional RL has remained unanswered. This paper explains the benefits…

Distributional Reinforcement Learning Offline RL reinforcement-learning

More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learning

2024-02-11 · Kaiwen Wang, Owen Oertell, Alekh Agarwal, Nathan Kallus 외

In this paper, we prove that Distributional Reinforcement Learning (DistRL), which learns the return distribution, can obtain second-order bounds in both online and offline RL in general settings with function approximat…

Distributional Reinforcement Learning Multi-Armed Bandits Offline RL