Model-Free Reinforcement Learning with the Decision-Estimation Coefficient

2022-11-25 · NeurIPS 2023 11

We consider the problem of interactive decision making, encompassing structured bandits and reinforcement learning with general function approximation. Recently, Foster et al. (2021) introduced the Decision-Estimation Coefficient, a measure of statistical complexity that lower bounds the optimal regret for interactive decision making, as well as a meta-algorithm, Estimation-to-Decisions, which achieves upper bounds in terms of the same quantity. Estimation-to-Decisions is a reduction, which lifts algorithms for (supervised) online estimation into algorithms for decision making. In this paper, we show that by combining Estimation-to-Decisions with a specialized form of optimistic estimation introduced by Zhang (2022), it is possible to obtain guarantees that improve upon those of Foster et al. (2021) by accommodating more lenient notions of estimation error. We use this approach to derive regret bounds for model-free reinforcement learning with value function approximation, and give structural results showing when it can and cannot help more generally.

📄 PDF Abstract BibTeX arXiv:2211.14250

Code (0)

등록된 구현이 없습니다.

Tasks

Decision Making reinforcement-learning Reinforcement Learning

The Statistical Complexity of Interactive Decision Making

2021-12-27 · Dylan J. Foster, Sham M. Kakade, Jian Qian, Alexander Rakhlin

A fundamental challenge in interactive learning and decision making, ranging from bandit problems to reinforcement learning, is to provide sample-efficient, adaptive learning algorithms that achieve near-optimal regret. …

Decision Making reinforcement-learning Reinforcement Learning (RL)

On the Complexity of Adversarial Decision Making

2022-06-27 · Dylan J. Foster, Alexander Rakhlin, Ayush Sekhari, Karthik Sridharan

A central problem in online learning and decision making -- from bandits to reinforcement learning -- is to understand what modeling assumptions lead to sample-efficient learning guarantees. We consider a general adversa…

Decision Making reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient

2023-01-19 · Dylan J. Foster, Noah Golowich, Yanjun Han

A foundational problem in reinforcement learning and interactive decision making is to understand what modeling assumptions lead to sample-efficient learning guarantees, and what algorithm design principles achieve optim…

Decision Making reinforcement-learning Reinforcement Learning (RL)

Unified Algorithms for RL with Decision-Estimation Coefficients: PAC, Reward-Free, Preference-Based Learning, and Beyond

2022-09-23 · Fan Chen, Song Mei, Yu Bai

Modern Reinforcement Learning (RL) is more than just learning the optimal policy; Alternative learning goals such as exploring the environment, estimating the underlying model, and learning from preference feedback are a…

PAC learning Reinforcement Learning (RL)

On the Complexity of Offline Reinforcement Learning with $Q^\star$-Approximation and Partial Coverage

2026-02-12 · Haolin Liu, Braham Snyder, Chen-Yu Wei arxiv

We study offline reinforcement learning under $Q^\star$-approximation and partial coverage, a setting that motivates practical algorithms such as Conservative $Q$-Learning (CQL; Kumar et al., 2020) but has received limit…

Reinforcement Learning Offline RL