102 citations · 786 across the 51 of their papers we have counts for
31 papers · 1 filter
Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP
Jinghan Wang, Mengdi Wang, Lin F. Yang
This work considers the sample complexity of obtaining an -optimal policy in an average reward Markov Decision Process (AMDP), given access to a generative model (simu…
Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally
Nived Rajaraman, Yanjun Han, Lin F. Yang +2
We study the statistical limits of Imitation Learning (IL) in episodic Markov Decision Processes (MDPs) with a state space . We focus on the known-transition setting w…
A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
Minbo Gao, Tianle Xie, Simon S. Du +1
Many real-world applications, such as those in medical domains, recommendation systems, etc, can be formulated as large state space reinforcement learning problems with only a smal…
Minimax Sample Complexity for Turn-based Stochastic Game
Qiwen Cui, Lin F. Yang
The empirical success of Multi-agent reinforcement learning is encouraging, while few theoretical guarantees have been revealed. In this work, we prove that the plug-in solver appr…
Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning
Jingfeng Wu, Vladimir Braverman, Lin F. Yang
In this paper we consider multi-objective reinforcement learning where the objectives are balanced using preferences. In practice, the preferences are often given in an adversarial…
Episodic Linear Quadratic Regulators with Low-rank Transitions
Tianyu Wang, Lin F. Yang
Linear Quadratic Regulators (LQR) achieve enormous successful real-world applications. Very recently, people have been focusing on efficient learning algorithms for LQRs when their…
Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?
Qiwen Cui, Lin F. Yang
It is believed that a model-based approach for reinforcement learning (RL) is the key to reduce sample complexity. However, the understanding of the sample optimality of model-base…
Toward the Fundamental Limits of Imitation Learning
Nived Rajaraman, Lin F. Yang, Jiantao Jiao +1
Imitation learning (IL) aims to mimic the behavior of an expert policy in a sequential decision-making problem given only demonstrations. In this paper, we focus on understanding t…
Obtaining Adjustable Regularization for Free via Iterate Averaging
Jingfeng Wu, Vladimir Braverman, Lin F. Yang
Regularization for optimization is a crucial technique to avoid overfitting in machine learning. In order to obtain the best performance, we usually train a model by tuning the reg…
Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity
Kaiqing Zhang, Sham M. Kakade, Tamer Başar +1
Model-based reinforcement learning (RL), which finds an optimal policy using an empirical model, has long been recognized as one of the corner stones of RL. It is especially suitab…
On Reward-Free Reinforcement Learning with Linear Function Approximation
Ruosong Wang, Simon S. Du, Lin F. Yang +1
Reward-free reinforcement learning (RL) is a framework which is suitable for both the batch RL setting and the setting where there are many reward functions of interest. During the…
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…
-learning with Logarithmic Regret
Kunhe Yang, Lin F. Yang, Simon S. Du
This paper presents the first non-asymptotic result showing that a model-free algorithm can achieve a logarithmic cumulative regret for episodic tabular reinforcement learning if t…
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…
Model-Based Reinforcement Learning with Value-Targeted Regression
Alex Ayoub, Zeyu Jia, Csaba Szepesvari +2
This paper studies model-based reinforcement learning (RL) for regret minimization. We focus on finite-horizon episodic RL where the transition model belongs to a known family…
Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
Ruosong Wang, Simon S. Du, Lin F. Yang +1
Learning to plan for long horizons is a central challenge in episodic reinforcement learning problems. A fundamental question is to understand how the difficulty of the problem sca…
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…
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…
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…