102 citations · 786 across the 51 of their papers we have counts for
11 papers · 1 filter
How Does an Approximate Model Help in Reinforcement Learning?
Fei Feng, Wotao Yin, Lin F. Yang
One of the key approaches to save samples in reinforcement learning (RL) is to use knowledge from an approximate model such as its simulator. However, how much does an approximate…
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…
Efficient Symmetric Norm Regression via Linear Sketching
Zhao Song, Ruosong Wang, Lin F. Yang +2
We provide efficient algorithms for overconstrained linear regression problems with size when the loss function is a symmetric norm (a norm invariant under sign-flips…
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?…
Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity
Aaron Sidford, Mengdi Wang, Lin F. Yang +1
In this paper, we settle the sampling complexity of solving discounted two-player turn-based zero-sum stochastic games up to polylogarithmic factors. Given a stochastic game with d…
Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
Lin F. Yang, Mengdi Wang
Exploration in reinforcement learning (RL) suffers from the curse of dimensionality when the state-action space is large. A common practice is to parameterize the high-dimensional…
Feature-Based Q-Learning for Two-Player Stochastic Games
Zeyu Jia, Lin F. Yang, Mengdi Wang
Consider a two-player zero-sum stochastic game where the transition function can be embedded in a given feature space. We propose a two-player Q-learning algorithm for approximatin…
Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal
Alekh Agarwal, Sham Kakade, Lin F. Yang
This work considers the sample and computational complexity of obtaining an -optimal policy in a discounted Markov Decision Process (MDP), given only access to a generative mode…
Learning to Control in Metric Space with Optimal Regret
Lin F. Yang, Chengzhuo Ni, Mengdi Wang
We study online reinforcement learning for finite-horizon deterministic control systems with {\it arbitrary} state and action spaces. Suppose that the transition dynamics and rewar…
The One-Way Communication Complexity of Dynamic Time Warping Distance
Vladimir Braverman, Moses Charikar, William Kuszmaul +2
We resolve the randomized one-way communication complexity of Dynamic Time Warping (DTW) distance. We show that there is an efficient one-way communication protocol using $\widetil…
Sample-Optimal Parametric Q-Learning Using Linearly Additive Features
Lin F. Yang, Mengdi Wang
Consider a Markov decision process (MDP) that admits a set of state-action features, which can linearly express the process's probabilistic transition model. We propose a parametri…