Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension

2020-05-21 · NeurIPS 2020 12 · Ruosong Wang, Ruslan Salakhutdinov, Lin F. Yang

Value function approximation has demonstrated phenomenal empirical success in reinforcement learning (RL). Nevertheless, despite a handful of recent progress on developing theory for RL with linear function approximation, the understanding of general function approximation schemes largely remains missing. In this paper, we establish a provably efficient RL algorithm with general value function approximation. We show that if the value functions admit an approximation with a function class $\mathcal{F}$, our algorithm achieves a regret bound of $\widetilde{O}(\mathrm{poly}(dH)\sqrt{T})$ where $d$ is a complexity measure of $\mathcal{F}$ that depends on the eluder dimension [Russo and Van Roy, 2013] and log-covering numbers, $H$ is the planning horizon, and $T$ is the number interactions with the environment. Our theory generalizes recent progress on RL with linear value function approximation and does not make explicit assumptions on the model of the environment. Moreover, our algorithm is model-free and provides a framework to justify the effectiveness of algorithms used in practice.

📄 PDF Abstract BibTeX arXiv:2005.10804

Code (0)

등록된 구현이 없습니다.

Tasks

Reinforcement Learning (RL)

Bellman Unbiasedness: Toward Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation

2024-07-31 · Taehyun Cho, Seungyub Han, Seokhun Ju, Dohyeong Kim 외

Distributional reinforcement learning improves performance by capturing environmental stochasticity, but a comprehensive theoretical understanding of its effectiveness remains elusive. In addition, the intractable elemen…

Distributional Reinforcement Learning reinforcement-learning Reinforcement Learning

Provably Efficient Reinforcement Learning via Surprise Bound

2023-02-22 · Hanlin Zhu, Ruosong Wang, Jason D. Lee

Value function approximation is important in modern reinforcement learning (RL) problems especially when the state space is (infinitely) large. Despite the importance and wide applicability of value function approximatio…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Provably Efficient Offline-to-Online Value Adaptation with General Function Approximation

2026-04-15 · Shangzhe Li, Weitong Zhang arxiv

We study value adaptation in offline-to-online reinforcement learning under general function approximation. Starting from an imperfect offline pretrained $Q$-function, the learner aims to adapt it to the target environme…

Reinforcement Learning

Provably Efficient Q-learning with Function Approximation via Distribution Shift Error Checking Oracle

2019-12-01 · NeurIPS 2019 12 · Simon S. Du, Yuping Luo, Ruosong Wang, Hanrui Zhang

Q-learning with function approximation is one of the most popular methods in reinforcement learning. Though the idea of using function approximation was proposed at least 60 years ago, even in the simplest setup, i.e, ap…

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

Provably Efficient $Q$-learning with Function Approximation via Distribution Shift Error Checking Oracle

2019-06-14 · Simon S. Du, Yuping Luo, Ruosong Wang, Hanrui Zhang

$Q$-learning with function approximation is one of the most popular methods in reinforcement learning. Though the idea of using function approximation was proposed at least 60 years ago, even in the simplest setup, i.e, …