Publications (18)
Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
Chi Jin, Tiancheng Jin, Haipeng Luo +2
We consider the problem of learning in episodic finite-horizon Markov decision processes with an unknown transition function, bandit feedback, and adversarial losses. We propose an…
Reward-Free Exploration for Reinforcement Learning
Chi Jin, Akshay Krishnamurthy, Max Simchowitz +1
Exploration is widely regarded as one of the most challenging aspects of reinforcement learning (RL), with many naive approaches succumbing to exponential sample complexity. To iso…
Near-Optimal Learning of Extensive-Form Games with Imperfect Information
Yu Bai, Chi Jin, Song Mei +1
This paper resolves the open question of designing near-optimal algorithms for learning imperfect-information extensive-form games from bandit feedback. We present the first line o…
Efficient Policy Learning for Non-Stationary MDPs under Adversarial Manipulation
Tiancheng Yu, Suvrit Sra
A Markov Decision Process (MDP) is a popular model for reinforcement learning. However, its commonly used assumption of stationary dynamics and rewards is too stringent and fails t…
V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL
Chi Jin, Qinghua Liu, Yuanhao Wang +1
A major challenge of multiagent reinforcement learning (MARL) is the curse of multiagents, where the size of the joint action space scales exponentially with the number of agents.…
Atomic-Scale Tracking Phase Transition Dynamics of Berezinskii-Kosterlitz-Thouless Polar Vortex-Antivortex
Ruixue Zhu, Sizheng Zheng, Xiaomei Li +8
Particle-like topologies, such as vortex-antivortex (V-AV) pairs, have garnered significant attention in the field of condensed matter. However, the detailed phase transition dynam…
Phase transition characteristics of Faraday waves
Peizhao Li, Tiancheng Yu, Xuechang Tu +3
Through experimentation, we have discovered that with the changing of driving conditions, the Faraday waves undergo two abrupt transitions in spatiotemporal order: onset and instab…
Near-Optimal Reinforcement Learning with Self-Play
Yu Bai, Chi Jin, Tiancheng Yu
This paper considers the problem of designing optimal algorithms for reinforcement learning in two-player zero-sum games. We focus on self-play algorithms which learn the optimal p…
Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descent
Yu Bai, Chi Jin, Song Mei +2
A conceptually appealing approach for learning Extensive-Form Games (EFGs) is to convert them to Normal-Form Games (NFGs). This approach enables us to directly translate state-of-t…
Regret Minimization with Adaptive Opponents in Repeated Games
Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu +1
In this paper, we study regret minimization in repeated games with \emph{adaptive} opponents who can respond based on histories of play. The standard metric of \emph{external regre…
Provably Efficient Algorithms for Multi-Objective Competitive RL
Tiancheng Yu, Yi Tian, Jingzhao Zhang +1
We study multi-objective reinforcement learning (RL) where an agent's reward is represented as a vector. In settings where an agent competes against opponents, its performance is m…
Online Learning in Unknown Markov Games
Yi Tian, Yuanhao Wang, Tiancheng Yu +1
We study online learning in unknown Markov games, a problem that arises in episodic multi-agent reinforcement learning where the actions of the opponents are unobservable. We show…
A Sharp Analysis of Model-based Reinforcement Learning with Self-Play
Qinghua Liu, Tiancheng Yu, Yu Bai +1
Model-based algorithms -- algorithms that explore the environment through building and utilizing an estimated model -- are widely used in reinforcement learning practice and theore…
Entropy Rate Estimation for Markov Chains with Large State Space
Yanjun Han, Jiantao Jiao, Chuan-Zheng Lee +3
Estimating the entropy based on data is one of the prototypical problems in distribution property testing and estimation. For estimating the Shannon entropy of a distribution on $S…
A General Framework for Analyzing Stochastic Dynamics in Learning Algorithms
Chi-Ning Chou, Juspreet Singh Sandhu, Mien Brabeeba Wang +1
One of the challenges in analyzing learning algorithms is the circular entanglement between the objective value and the stochastic noise. This is also known as the "chicken and egg…
The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces
Chi Jin, Qinghua Liu, Tiancheng Yu
Modern reinforcement learning (RL) commonly engages practical problems with large state spaces, where function approximation must be deployed to approximate either the value functi…
The Power of Regularization in Solving Extensive-Form Games
Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu +1
In this paper, we investigate the power of {\it regularization}, a common technique in reinforcement learning and optimization, in solving extensive-form games (EFGs). We propose a…
Near Optimal Stratified Sampling
Tiancheng Yu, Xiyu Zhai, Suvrit Sra
The performance of a machine learning system is usually evaluated by using i.i.d.\ observations with true labels. However, acquiring ground truth labels is expensive, while obtaini…