REVIEW 6 cited by
The Role of Coverage in Online Reinforcement Learning
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
The Role of Coverage in Online Reinforcement Learning
read the original abstract
Coverage conditions -- which assert that the data logging distribution adequately covers the state space -- play a fundamental role in determining the sample complexity of offline reinforcement learning. While such conditions might seem irrelevant to online reinforcement learning at first glance, we establish a new connection by showing -- somewhat surprisingly -- that the mere existence of a data distribution with good coverage can enable sample-efficient online RL. Concretely, we show that coverability -- that is, existence of a data distribution that satisfies a ubiquitous coverage condition called concentrability -- can be viewed as a structural property of the underlying MDP, and can be exploited by standard algorithms for sample-efficient exploration, even when the agent does not know said distribution. We complement this result by proving that several weaker notions of coverage, despite being sufficient for offline RL, are insufficient for online RL. We also show that existing complexity measures for online RL, including Bellman rank and Bellman-Eluder dimension, fail to optimally capture coverability, and propose a new complexity measure, the sequential extrapolation coefficient, to provide a unification.
Forward citations
Cited by 6 Pith papers
-
Fitted Occupancy-Ratio Evaluation without Bellman Completeness
FORE estimates discounted occupancy ratios by iterating KL-projected adjoint Bellman updates, achieving convergence under ratio realizability alone without Bellman completeness.
-
Fitted Occupancy-Ratio Evaluation without Bellman Completeness
Fitted occupancy-ratio evaluation (FORE) contracts in KL divergence under only occupancy-ratio realizability, enabling offline policy evaluation without Bellman completeness.
-
Online KL-Regularized Reinforcement Learning with Function Approximation under Misspecification
Introduces KL misspecification for bandits and RL under function approximation and proves explicit KL-regret bounds for regression-based Gibbs algorithms that recover the realizable case.
-
Towards Differentially Private Reinforcement Learning with General Function Approximation
The work establishes the first DP regret bound of order O(K^{3/5}) for model-free online RL under general function approximation and the first coverability-based regret bound for batched non-private RL.
-
Quantile of Means: A Bonus-Free Ensemble Method for Minimax Optimal Reinforcement Learning
A quantile-of-means ensemble method achieves minimax optimal variance-dependent regret bounds for finite-horizon MDPs without count-based uncertainty estimates.
-
Online KL-Regularized Reinforcement Learning with Function Approximation under Misspecification
Optimistic regression algorithms with Gibbs updates achieve high-probability KL-regret that degrades gracefully under pointwise KL misspecification for bandits and stagewise KL Bellman misspecification for episodic RL.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.