23 citations · 94 across the 23 of their papers we have counts for
23 papers
VISER: A Tractable Solution Concept for Games with Information Asymmetry
Jeremy McMahan, Young Wu, Yudong Chen +2
Many real-world games suffer from information asymmetry: one player is only aware of their own payoffs while the other player has the full game information. Examples include the cr…
Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements
Emmanouil-Vasileios Vlatakis-Gkaragkounis, Angeliki Giannou, Yudong Chen +1
For min-max optimization and variational inequalities problems (VIP) encountered in diverse machine learning tasks, Stochastic Extragradient (SEG) and Stochastic Gradient Descent A…
Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes
Zihan Zhang, Qiaomin Xie
We develop several provably efficient model-free reinforcement learning (RL) algorithms for infinite-horizon average-reward Markov Decision Processes (MDPs). We consider both onlin…
Data Poisoning to Fake a Nash Equilibrium in Markov Games
Young Wu, Jeremy McMahan, Xiaojin Zhu +1
We characterize offline data poisoning attacks on Multi-Agent Reinforcement Learning (MARL), where an attacker may change a data set in an attempt to install a (potentially fictiti…
Learning to Stabilize Online Reinforcement Learning in Unbounded State Spaces
Brahma S. Pavse, Matthew Zurek, Yudong Chen +2
In many reinforcement learning (RL) applications, we want policies that reach desired states and then keep the controlled system within an acceptable region around the desired stat…
Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption
Yige Hong, Qiaomin Xie, Yudong Chen +1
We study the infinite-horizon restless bandit problem with the average reward criterion, in both discrete-time and continuous-time settings. A fundamental goal is to efficiently co…
SPEED: Experimental Design for Policy Evaluation in Linear Heteroscedastic Bandits
Subhojyoti Mukherjee, Qiaomin Xie, Josiah Hanna +1
In this paper, we study the problem of optimal data collection for policy evaluation in linear bandits. In policy evaluation, we are given a target policy and asked to estimate the…
Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes
Dongyan Huo, Yudong Chen, Qiaomin Xie
We consider Linear Stochastic Approximation (LSA) with a constant stepsize and Markovian data. Viewing the joint process of the data and LSA iterate as a time-homogeneous Markov ch…
Near-Optimal Stochastic Bin-Packing in Large Service Systems with Time-Varying Item Sizes
Yige Hong, Qiaomin Xie, Weina Wang
In modern computing systems, jobs' resource requirements often vary over time. Accounting for this temporal variability during job scheduling is essential for meeting performance g…
Reward Poisoning Attacks on Offline Multi-Agent Reinforcement Learning
Young Wu, Jeremy McMahan, Xiaojin Zhu +1
In offline multi-agent reinforcement learning (MARL), agents estimate policies from a given dataset. We study reward-poisoning attacks in this setting where an exogenous attacker m…
Zero Queueing for Multi-Server Jobs
Weina Wang, Qiaomin Xie, Mor Harchol-Balter
Cloud computing today is dominated by multi-server jobs. These are jobs that request multiple servers simultaneously and hold onto all of these servers for the duration of the job.…
RL-QN: A Reinforcement Learning Framework for Optimal Control of Queueing Systems
Bai Liu, Qiaomin Xie, Eytan Modiano
With the rapid advance of information technology, network systems have become increasingly complex and hence the underlying system dynamics are often unknown or difficult to charac…
Provable Fictitious Play for General Mean-Field Games
Qiaomin Xie, Zhuoran Yang, Zhaoran Wang +1
We propose a reinforcement learning algorithm for stationary mean-field games, where the goal is to learn a pair of mean-field state and stationary policy that constitutes the Nash…
Dynamic Regret of Policy Optimization in Non-stationary Environments
Yingjie Fei, Zhuoran Yang, Zhaoran Wang +1
We consider reinforcement learning (RL) in episodic MDPs with adversarial full-information reward feedback and unknown fixed transition kernels. We propose two model-free policy op…
Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret
Yingjie Fei, Zhuoran Yang, Yudong Chen +2
We study risk-sensitive reinforcement learning in episodic Markov decision processes with unknown transition kernels, where the goal is to optimize the total reward under the risk…
Stable Reinforcement Learning with Unbounded State Space
Devavrat Shah, Qiaomin Xie, Zhi Xu
We consider the problem of reinforcement learning (RL) with unbounded state space motivated by the classical problem of scheduling in a queueing network. Traditional policies as we…
POLY-HOOT: Monte-Carlo Planning in Continuous Space MDPs with Non-Asymptotic Analysis
Weichao Mao, Kaiqing Zhang, Qiaomin Xie +1
Monte-Carlo planning, as exemplified by Monte-Carlo Tree Search (MCTS), has demonstrated remarkable performance in applications with finite spaces. In this paper, we consider Monte…
On Reinforcement Learning for Turn-based Zero-sum Markov Games
Devavrat Shah, Varun Somani, Qiaomin Xie +1
We consider the problem of finding Nash equilibrium for two-player turn-based zero-sum games. Inspired by the AlphaGo Zero (AGZ) algorithm, we develop a Reinforcement Learning base…
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
Qiaomin Xie, Yudong Chen, Zhaoran Wang +1
We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games with simultaneous moves. To incorporate function approximation,…
Non-Asymptotic Analysis of Monte Carlo Tree Search
Devavrat Shah, Qiaomin Xie, Zhi Xu
In this work, we consider the popular tree-based search strategy within the framework of reinforcement learning, the Monte Carlo Tree Search (MCTS), in the context of infinite-hori…
Q-learning with Nearest Neighbors
Devavrat Shah, Qiaomin Xie
We consider model-free reinforcement learning for infinite-horizon discounted Markov Decision Processes (MDPs) with a continuous state space and unknown transition kernel, when onl…
Centralized Congestion Control and Scheduling in a Datacenter
Devavrat Shah, Qiaomin Xie
We consider the problem of designing a packet-level congestion control and scheduling policy for datacenter networks. Current datacenter networks primarily inherit the principles t…
Greed Works -- Online Algorithms For Unrelated Machine Stochastic Scheduling
Varun Gupta, Benjamin Moseley, Marc Uetz +1
This paper establishes performance guarantees for online algorithms that schedule stochastic, nonpreemptive jobs on unrelated machines to minimize the expected total weighted compl…