20 citations · 164 across the 63 of their papers we have counts for
10 papers · 1 filter
Exponential Hardness of Reinforcement Learning with Linear Function Approximation
Daniel Kane, Sihan Liu, Shachar Lovett +3
A fundamental question in reinforcement learning theory is: suppose the optimal value functions are linear in given features, can we learn them efficiently? This problem's counterp…
Do PAC-Learners Learn the Marginal Distribution?
Max Hopkins, Daniel M. Kane, Shachar Lovett +1
The Fundamental Theorem of PAC Learning asserts that learnability of a concept class is equivalent to the of empirical error in to its mean,…
Computational-Statistical Gaps in Reinforcement Learning
Daniel Kane, Sihan Liu, Shachar Lovett +1
Reinforcement learning with function approximation has recently achieved tremendous results in applications with large state spaces. This empirical success has motivated a growing…
Realizable Learning is All You Need
Max Hopkins, Daniel M. Kane, Shachar Lovett +1
The equivalence of realizable and agnostic learnability is a fundamental phenomenon in learning theory. With variants ranging from classical settings like PAC learning and regressi…
Bilinear Classes: A Structural Framework for Provable Generalization in RL
Simon S. Du, Sham M. Kakade, Jason D. Lee +4
This work introduces Bilinear Classes, a new structural framework, which permit generalization in reinforcement learning in a wide variety of settings through the use of function a…
Bounded Memory Active Learning through Enriched Queries
Max Hopkins, Daniel Kane, Shachar Lovett +1
The explosive growth of easily-accessible unlabeled data has lead to growing interest in active learning, a paradigm in which data-hungry learning algorithms adaptively select info…