research
∙
02/28/2023
Learning Hidden Markov Models Using Conditional Samples
This paper is concerned with the computational complexity of learning th...
share
research
∙
02/25/2023
Exponential Hardness of Reinforcement Learning with Linear Function Approximation
A fundamental question in reinforcement learning theory is: suppose the ...
research
∙
02/13/2023
Do PAC-Learners Learn the Marginal Distribution?
We study a foundational variant of Valiant and Vapnik and Chervonenkis' ...
research
∙
02/22/2022
Convergence of online k-means
We prove asymptotic convergence for a general class of k-means algorithm...
research
∙
02/11/2022
Computational-Statistical Gaps in Reinforcement Learning
Reinforcement learning with function approximation has recently achieved...
research
∙
01/11/2022
Learning what to remember
We consider a lifelong learning scenario in which a learner faces a neve...
research
∙
11/08/2021
Realizable Learning is All You Need
The equivalence of realizable and agnostic learnability is a fundamental...
research
∙
03/19/2021
Bilinear Classes: A Structural Framework for Provable Generalization in RL
This work introduces Bilinear Classes, a new structural framework, which...
research
∙
04/23/2020
Point Location and Active Learning: Learning Halfspaces Almost Optimally
Given a finite set X ⊂ℝ^d and a binary linear classifier c: ℝ^d →{0,1}, ...
research
∙
02/17/2020
Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
The current paper studies the problem of agnostic Q-learning with functi...
research
∙
01/15/2020
Noise-tolerant, Reliable Active Classification with Comparison Queries
With the explosion of massive, widely available unlabeled data in the pa...
research
∙
08/01/2019