Pith. sign in

REVIEW 2 cited by

Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

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

arxiv 2102.00815 v4 pith:RF5LE3TG submitted 2021-02-01 cs.LG cs.AIstat.ML

Chi Jin , Qinghua Liu , Sobhan Miryoosefi This is my paper · ORCID
classification cs.LGcs.AIstat.ML
keywords problemsdimensionbellmaneluderalgorithmalgorithmscomplexityexisting
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

Finding the minimal structural assumptions that empower sample-efficient learning is one of the most important research directions in Reinforcement Learning (RL). This paper advances our understanding of this fundamental question by introducing a new complexity measure -- Bellman Eluder (BE) dimension. We show that the family of RL problems of low BE dimension is remarkably rich, which subsumes a vast majority of existing tractable RL problems including but not limited to tabular MDPs, linear MDPs, reactive POMDPs, low Bellman rank problems as well as low Eluder dimension problems. This paper further designs a new optimization-based algorithm -- GOLF, and reanalyzes a hypothesis elimination-based algorithm -- OLIVE (proposed in Jiang et al., 2017). We prove that both algorithms learn the near-optimal policies of low BE dimension problems in a number of samples that is polynomial in all relevant parameters, but independent of the size of state-action space. Our regret and sample complexity results match or improve the best existing results for several well-known subclasses of low BE dimension problems.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Online KL-Regularized Reinforcement Learning with Function Approximation under Misspecification

    cs.LG 2026-06 unverdicted novelty 7.0 of 10

    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.

  2. Pretraining in Actor-Critic Reinforcement Learning for Locomotion

    cs.RO 2025-10 conditional novelty 6.0 of 10

    Pretraining an inverse dynamics model on task-agnostic exploration data and using its weights to initialize PPO actor and critic improves sample efficiency by ~37% and final performance by ~7% across nine simulated lo...

Pith tools