384 citations · 1.1k across the 22 of their papers we have counts for
15 papers · 1 filter
Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning
Yuanzhi Li, Ruosong Wang, Lin F. Yang
Recently there is a surge of interest in understanding the horizon-dependence of the sample complexity in reinforcement learning (RL). Notably, for an RL environment with horizon l…
An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
Yuanhao Wang, Ruosong Wang, Sham M. Kakade
A fundamental question in the theory of reinforcement learning is: suppose the optimal -function lies in the linear span of a given dimensional feature mapping, is sample-ef…
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…
Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
Ruosong Wang, Ruslan Salakhutdinov, Lin F. Yang
Value function approximation has demonstrated phenomenal empirical success in reinforcement learning (RL). Nevertheless, despite a handful of recent progress on developing theory f…
Preference-based Reinforcement Learning with Finite-Time Guarantees
Yichong Xu, Ruosong Wang, Lin F. Yang +2
Preference-based Reinforcement Learning (PbRL) replaces reward values in traditional reinforcement learning by preferences to better elicit human opinion on the target objective, e…
Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning
Fei Feng, Ruosong Wang, Wotao Yin +2
Motivated by the prevailing paradigm of using unsupervised learning for efficient exploration in reinforcement learning (RL) problems [tang2017exploration,bellemare2016unifying], w…
Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
Simon S. Du, Jason D. Lee, Gaurav Mahajan +1
The current paper studies the problem of agnostic -learning with function approximation in deterministic systems where the optimal -function is approximable by a function in…
Enhanced Convolutional Neural Tangent Kernels
Zhiyuan Li, Ruosong Wang, Dingli Yu +4
Recent research shows that for training with loss, convolutional neural networks (CNNs) whose width (number of channels in convolutional layers) goes to infinity correspon…
Continuous Control with Contexts, Provably
Simon S. Du, Ruosong Wang, Mengdi Wang +1
A fundamental challenge in artificial intelligence is to build an agent that generalizes and adapts to unseen environments. A common strategy is to build a decoder that takes the c…
Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks
Sanjeev Arora, Simon S. Du, Zhiyuan Li +3
Recent research shows that the following two models are equivalent: (a) infinitely wide neural networks (NNs) trained under l2 loss by gradient descent with infinitesimally small l…
Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
Simon S. Du, Sham M. Kakade, Ruosong Wang +1
Modern deep learning methods provide effective means to learn good representations. However, is a good representation itself sufficient for sample efficient reinforcement learning?…
Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
Simon S. Du, Kangcheng Hou, Barnabás Póczos +3
While graph kernels (GKs) are easy to train and enjoy provable theoretical guarantees, their practical performances are limited by their expressive power, as the kernel function of…
On Exact Computation with an Infinitely Wide Neural Net
Sanjeev Arora, Simon S. Du, Wei Hu +3
How well does a classic deep net architecture like AlexNet or VGG19 classify on a standard dataset such as CIFAR-10 when its width --- namely, number of channels in convolutional l…
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
Sanjeev Arora, Simon S. Du, Wei Hu +2
Recent works have cast some light on the mystery of why deep nets fit any data and generalize despite being very overparametrized. This paper analyzes training and generalization f…
Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration
Lijie Chen, Anupam Gupta, Jian Li +2
We study the combinatorial pure exploration problem Best-Set in stochastic multi-armed bandits. In a Best-Set instance, we are given arms with unknown reward distributions, as…