research
∙
02/22/2023
Provably Efficient Reinforcement Learning via Surprise Bound
Value function approximation is important in modern reinforcement learni...
share
research
∙
10/20/2022
Horizon-Free Reinforcement Learning for Latent Markov Decision Processes
We study regret minimization for reinforcement learning (RL) in Latent M...
research
∙
05/26/2022
Variance-Aware Sparse Linear Bandits
It is well-known that the worst-case minimax regret for sparse linear ba...
research
∙
11/01/2021
Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning
Recently there is a surge of interest in understanding the horizon-depen...
research
∙
06/14/2021
Online Sub-Sampling for Reinforcement Learning with General Function Approximation
Designing provably efficient algorithms with general function approximat...
research
∙
03/23/2021
An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
A fundamental question in the theory of reinforcement learning is: suppo...
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
∙
03/08/2021
Instabilities of Offline RL with Pre-Trained Neural Representation
In offline reinforcement learning (RL), we seek to utilize offline data ...
research
∙
10/22/2020
What are the Statistical Limits of Offline RL with Linear Function Approximation?
Offline reinforcement learning seeks to utilize offline (observational) ...
research
∙
10/22/2020
Planning with Submodular Objective Functions
We study planning with submodular objective functions, where instead of ...
research
∙
06/19/2020
On Reward-Free Reinforcement Learning with Linear Function Approximation
Reward-free reinforcement learning (RL) is a framework which is suitable...
research
∙
06/16/2020
Preference-based Reinforcement Learning with Finite-Time Guarantees
Preference-based Reinforcement Learning (PbRL) replaces reward values in...
research
∙
06/15/2020
Nearly Linear Row Sampling Algorithm for Quantile Regression
We give a row sampling algorithm for the quantile loss function with sam...
research
∙
05/21/2020
Provably Efficient Reinforcement Learning with General Value Function Approximation
Value function approximation has demonstrated phenomenal empirical succe...
research
∙
05/01/2020
Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
Learning to plan for long horizons is a central challenge in episodic re...
research
∙
03/15/2020
Provably Efficient Exploration for RL with Unsupervised Learning
We study how to use unsupervised learning for efficient exploration in r...
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
∙
12/09/2019
Optimism in Reinforcement Learning with Generalized Linear Function Approximation
We design a new provably efficient algorithm for episodic reinforcement ...
research
∙
11/03/2019
Enhanced Convolutional Neural Tangent Kernels
Recent research shows that for training with ℓ_2 loss, convolutional neu...
research
∙
10/30/2019
Continuous Control with Contexts, Provably
A fundamental challenge in artificial intelligence is to build an agent ...
research
∙
10/07/2019
Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
Modern deep learning methods provide an effective means to learn good re...
research
∙
10/04/2019
Efficient Symmetric Norm Regression via Linear Sketching
We provide efficient algorithms for overconstrained linear regression pr...
research
∙
10/03/2019
Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks
Recent research shows that the following two models are equivalent: (a) ...
research
∙
06/14/2019
Provably Efficient Q-learning with Function Approximation via Distribution Shift Error Checking Oracle
Q-learning with function approximation is one of the most popular method...
research
∙
06/13/2019
The Communication Complexity of Optimization
We consider the communication complexity of a number of distributed opti...
research
∙
05/30/2019
Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
While graph kernels (GKs) are easy to train and enjoy provable theoretic...
research
∙
05/14/2019
Dimensionality Reduction for Tukey Regression
We give the first dimensionality reduction methods for the overconstrain...
research
∙
04/26/2019
On Exact Computation with an Infinitely Wide Neural Net
How well does a classic deep net architecture like AlexNet or VGG19 clas...
research
∙
04/11/2019
Tight Bounds for the Subspace Sketch Problem with Applications
In the subspace sketch problem one is given an n× d matrix A with O((nd)...
research
∙
01/24/2019
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
Recent works have cast some light on the mystery of why deep nets fit an...
research
∙
11/19/2018
Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols
The polynomial method from circuit complexity has been applied to severa...
research
∙
01/13/2018
Tight Bounds for ℓ_p Oblivious Subspace Embeddings
An ℓ_p oblivious subspace embedding is a distribution over r × n matrice...
research
∙
06/04/2017