What can online reinforcement learning with function approximation benefit from general coverage conditions?

2023-04-25 · Fanghui Liu, Luca Viano, Volkan Cevher

In online reinforcement learning (RL), instead of employing standard structural assumptions on Markov decision processes (MDPs), using a certain coverage condition (original from offline RL) is enough to ensure sample-efficient guarantees (Xie et al. 2023). In this work, we focus on this new direction by digging more possible and general coverage conditions, and study the potential and the utility of them in efficient online RL. We identify more concepts, including the $L^p$ variant of concentrability, the density ratio realizability, and trade-off on the partial/rest coverage condition, that can be also beneficial to sample-efficient online RL, achieving improved regret bound. Furthermore, if exploratory offline data are used, under our coverage conditions, both statistically and computationally efficient guarantees can be achieved for online RL. Besides, even though the MDP structure is given, e.g., linear MDP, we elucidate that, good coverage conditions are still beneficial to obtain faster regret bound beyond $\widetilde{O}(\sqrt{T})$ and even a logarithmic order regret. These results provide a good justification for the usage of general coverage conditions in efficient online RL.

📄 PDF Abstract BibTeX arXiv:2304.12886

Code (0)

등록된 구현이 없습니다.

Tasks

Offline RL Reinforcement Learning (RL)

SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation

2017-12-29 · ICML 2018 7 · Bo Dai, Albert Shaw, Lihong Li, Lin Xiao 외

When function approximation is used, solving the Bellman optimality equation with stability guarantees has remained a major open problem in reinforcement learning for decades. The fundamental difficulty is that the Bellm…

Q-Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Two-Timescale Networks for Nonlinear Value Function Approximation

2019-05-01 · ICLR 2019 5 · Wesley Chung, Somjit Nath, Ajin Joseph, Martha White

A key component for many reinforcement learning agents is to learn a value function, either for policy evaluation or control. Many of the algorithms for learning values, however, are designed for linear function approxim…

Q-Learning Reinforcement Learning Vocal Bursts Valence Prediction

Going Beyond Linear RL: Sample Efficient Neural Function Approximation

2021-07-14 · NeurIPS 2021 12 · Baihe Huang, Kaixuan Huang, Sham M. Kakade, Jason D. Lee 외

Deep Reinforcement Learning (RL) powered by neural net approximation of the Q function has had enormous empirical success. While the theory of RL has traditionally focused on linear function approximation (or eluder dime…

Deep Reinforcement Learning Reinforcement Learning (RL)

Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation

2021-11-21 · Dylan J. Foster, Akshay Krishnamurthy, David Simchi-Levi, Yunzong Xu

We consider the offline reinforcement learning problem, where the aim is to learn a decision making policy from logged data. Offline RL -- particularly when coupled with (value) function approximation to allow for genera…

Decision Making Offline RL reinforcement-learning Reinforcement Learning+1

Reinforcement Learning with Function Approximation: From Linear to Nonlinear

2023-02-20 · Jihao Long, Jiequn Han

Function approximation has been an indispensable component in modern reinforcement learning algorithms designed to tackle problems with large state spaces in high dimensions. This paper reviews recent results on error an…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)