Browse publications
All topics
Stochastic approximation
Reinforcement learning
Games & multi-agent learning
Bandits & online decisions
Stochastic networks
All by year
Wasserstein-p Central Limit Theorem Rates: From Local Dependence to Markov Chains
Yixuan Zhang,
and Qiaomin Xie
In ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems
2026
Best Student Paper
central limit theorem
Wasserstein distance
dependent data
Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive Stochastic Approximation
Yixuan Zhang,
Dongyan (Lucy) Huo,
Yudong Chen,
and Qiaomin Xie
Operations Research
2026
stochastic approximation
coupling
steady-state convergence
Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes
Dongyan Huo,
Yudong Chen,
and Qiaomin Xie
Mathematics of Operations Research
2026
linear stochastic approximation
Markovian data
bias extrapolation
A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression
Yixuan Zhang,
Dongyan (Lucy) Huo,
Yudong Chen,
and Qiaomin Xie
In ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems
2025
stochastic gradient descent
Lyapunov analysis
robust regression
Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Way
Jeongyeol Kwon,
Luke Dotson,
Yudong Chen,
and Qiaomin Xie
In International Conference on Artificial Intelligence and Statistics (AISTATS)
2025
linear stochastic approximation
two timescales
constant stepsize
Coupling-based Convergence Diagnostic and Stepsize Scheme for Stochastic Gradient Descent
Xiang Li,
and Qiaomin Xie
In AAAI Conference on Artificial Intelligence
2025
stochastic gradient descent
coupling
stepsize selection
The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize
Dongyan (Lucy) Huo,
Yixuan Zhang,
Yudong Chen,
and Qiaomin Xie
In Advances in Neural Information Processing Systems (NeurIPS), Spotlight
2024
stochastic approximation
constant stepsize
Markovian noise
Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation
Yixuan Zhang,
and Qiaomin Xie
In Reinforcement Learning Conference (RLC)
2024
Q-learning
constant stepsize
distributional convergence
Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive Stochastic Approximation
Yixuan Zhang,
Dongyan (Lucy) Huo,
Yudong Chen,
and Qiaomin Xie
In ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems
2024
stochastic approximation
coupling
constant stepsize
Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements
Emmanouil-Vasileios Vlatakis-Gkaragkounis,
Angeliki Giannou,
Yudong Chen,
and Qiaomin Xie
In International Conference on Artificial Intelligence and Statistics (AISTATS), Oral
2024
variational inequalities
stochastic optimization
ergodicity
Effectiveness of Constant Stepsize in Markovian LSA and Statistical Inference
Dongyan (Lucy) Huo,
Yudong Chen,
and Qiaomin Xie
In AAAI Conference on Artificial Intelligence
2024
linear stochastic approximation
statistical inference
constant stepsize
Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes
Dongyan (Lucy) Huo,
Yudong Chen,
and Qiaomin Xie
In ACM Sigmetrics
2023
linear stochastic approximation
Markovian data
constant stepsize
Optimal Regret for Policy Optimization in Average Reward MDPs Without Mixing
William Powell,
Jeongyeol Kwon,
Qiaomin Xie ,
and Hanbaek Lyu
In Reinforcement Learning Conference (RLC)
2026
policy optimization
average-reward MDPs
regret
Offline Actor-Critic for Average Reward MDPs
William Powell,
Jeongyeol Kwon,
Qiaomin Xie ,
and Hanbaek Lyu
In Advances in Neural Information Processing Systems (NeurIPS)
2025
offline RL
actor-critic
average-reward MDPs
Stable Offline Value Function Learning with Bisimulation-based Representations
Brahma S. Pavse,
Yudong Chen,
Qiaomin Xie ,
and Josiah P. Hanna
In International Conference on Machine Learning (ICML)
2025
offline RL
value functions
representation learning
Learning to Stabilize Online Reinforcement Learning in Unbounded State Spaces
Brahma S. Pavse,
Matthew Zurek,
Yudong Chen,
Qiaomin Xie ,
and Josiah P. Hanna
In International Conference on Machine Learning (ICML)
2024
online RL
stability
unbounded state spaces
Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes
Zihan Zhang,
and Qiaomin Xie
In Conference on Learning Theory (COLT)
2023
average-reward MDPs
model-free RL
sample complexity
ORSuite: Benchmarking Suite for Sequential Operations Models
Christopher Archer,
Siddhartha Banerjee,
Mayleen Cortez,
Carrie Rucker,
Sean R. Sinclair,
Max Solberg,
Qiaomin Xie ,
and Christina Lee Yu
SIGMETRICS Performance Evaluation Review
2022
reinforcement learning
operations research
benchmarking
Reinforcement learning (RL) has received widespread attention across multiple communities, but the experiments have focused primarily on large-scale game playing and robotics tasks. In this paper we introduce ORSuite, an open-source library containing environments, algorithms, and instrumentation for operational problems. Our package is designed to motivate researchers in the reinforcement learning community to develop and evaluate algorithms on operational tasks, and to consider the true multi-objective nature of these problems by considering metrics beyond cumulative reward.
Nonasymptotic Analysis of Monte Carlo Tree Search
Devavrat Shah,
Qiaomin Xie ,
and Zhi Xu
Operations Research
2022
Monte Carlo tree search
planning
nonasymptotic analysis
Dynamic Regret of Policy Optimization in Non-Stationary Environments
Yingjie Fei,
Zhuoran Yang,
Zhaoran Wang,
and Qiaomin Xie
In Advances in Neural Information Processing Systems (NeurIPS)
2020
policy optimization
nonstationarity
dynamic regret
POLY-HOOT: Monte-Carlo Planning in Continuous Space MDPs with Non-Asymptotic Analysis
Weichao Mao,
Kaiqing Zhang,
Qiaomin Xie ,
and Tamer Basar
In Advances in Neural Information Processing Systems (NeurIPS)
2020
Monte Carlo planning
continuous spaces
nonasymptotic analysis
Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret
Yingjie Fei,
Zhuoran Yang,
Yudong Chen,
Zhaoran Wang,
and Qiaomin Xie
In Advances in Neural Information Processing Systems (NeurIPS)
2020
risk-sensitive RL
regret
sample complexity
Stable Reinforcement Learning with Unbounded State Space
Devavrat Shah,
Qiaomin Xie ,
and Zhi Xu
In Learning for Dynamics and Control (L4DC)
2020
stability
unbounded state spaces
reinforcement learning
Non-asymptotic analysis of Monte Carlo tree search
Devavrat Shah,
Qiaomin Xie ,
and Zhi Xu
In ACM Sigmetrics
2020
Monte Carlo tree search
planning
nonasymptotic analysis
Q-learning with nearest neighbors
Devavrat Shah,
and Qiaomin Xie
In Advances in Neural Information Processing Systems (NeurIPS)
2018
Q-learning
function approximation
continuous state spaces
Inception: Efficiently Computable Misinformation Attacks on Markov Games
Jeremy McMahan,
Young Wu,
Yudong Chen,
Xiaojin Zhu,
and Qiaomin Xie
In Reinforcement Learning Conference (RLC)
2024
Markov games
misinformation attacks
learning security
Roping in Uncertainty: Robustness and Regularization in Markov Games
Jeremy McMahan,
Giovanni Artiglio,
and Qiaomin Xie
In International Conference on Machine Learning (ICML)
2024
Markov games
robustness
regularization
Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value
Young Wu,
Jeremy McMahan,
Yiding Chen,
Yudong Chen,
Xiaojin Zhu,
and Qiaomin Xie
In International Conference on Machine Learning (ICML)
2024
Markov games
Nash equilibrium
game modification
Data Poisoning to Fake a Nash Equilibrium in Markov Games
Young Wu,
Jeremy McMahan,
Xiaojin Zhu,
and Qiaomin Xie
In AAAI Conference on Artificial Intelligence
2024
Markov games
data poisoning
Nash equilibrium
Exact Policy Recovery in Offline RL with Both Heavy-Tailed Rewards and Data Corruption
Yiding Chen,
Xuezhou Zhang,
Qiaomin Xie ,
and Xiaojin Zhu
In AAAI Conference on Artificial Intelligence
2024
offline RL
data corruption
robust learning
Optimal Attack and Defense for Reinforcement Learning
Jeremy McMahan,
Young Wu,
Xiaojin Zhu,
and Qiaomin Xie
In AAAI Conference on Artificial Intelligence
2024
reinforcement learning
adversarial attacks
defense
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
Qiaomin Xie ,
Yudong Chen,
Zhaoran Wang,
and Zhuoran Yang
Mathematics of Operations Research
2023
Markov games
function approximation
correlated equilibrium
We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games with simultaneous moves. To incorporate function approximation, we consider a family of Markov games where the reward function and transition kernel possess a linear structure. Both the offline and online settings of the problems are considered. In the offline setting, we control both players and aim to find the Nash equilibrium by minimizing the duality gap. In the online setting, we control a single player playing against an arbitrary opponent and aim to minimize the regret. For both settings, we propose an optimistic variant of the least-squares minimax value iteration algorithm. We show that our algorithm is computationally efficient and provably achieves an O(d3H3T) upper bound on the duality gap and regret, where d is the linear dimension, H the horizon and T the total number of timesteps. Our results do not require additional assumptions on the sampling model. Our setting requires overcoming several new challenges that are absent in Markov decision processes or turn-based Markov games. In particular, to achieve optimism with simultaneous moves, we construct both upper and lower confidence bounds of the value function, and then compute the optimistic policy by solving a general-sum matrix game with these bounds as the payoff matrices. As finding the Nash equilibrium of a general-sum game is computationally hard, our algorithm instead solves for a coarse correlated equilibrium (CCE), which can be obtained efficiently. To our best knowledge, such a CCE-based scheme for optimism has not appeared in the literature and might be of interest in its own right.
Reward Poisoning Attacks on Offline Multi-Agent Reinforcement Learning
Young Wu,
Jermey McMahan,
Xiaojin Zhu,
and Qiaomin Xie
In AAAI Conference on Artificial Intelligence
2023
multi-agent RL
data poisoning
offline learning
Learning While Playing in Mean-Field Games: Convergence and Optimality
Qiaomin Xie ,
Zhuoran Yang,
Zhaoran Wang,
and Andreea Minca
In International Conference on Machine Learning (ICML)
2021
mean-field games
learning dynamics
equilibrium
On Reinforcement Learning for Turn-based Zero-sum Markov Games
Devavrat Shah,
Varun Somani,
Qiaomin Xie ,
and Zhi Xu
In Proceedings of the 2020 ACM-IMS on Foundations of Data Science Conference
2020
Markov games
zero-sum games
reinforcement learning
Learning zero-sum simultaneous-move Markov games using function approximation and correlated equilibrium
Qiaomin Xie ,
Yudong Chen,
Zhaoran Wang,
and Zhuoran Yang
In Conference on Learning Theory
2020
Markov games
function approximation
correlated equilibrium
Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs
Tianhao Wu,
Matthew Zurek,
Weina Wang,
and Qiaomin Xie
In Conference on Learning Theory (COLT)
2026
weakly-coupled MDPs
restless bandits
sample complexity
On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimization
Yixuan Zhang,
Ruihao Zhu,
and Qiaomin Xie
arXiv preprint arXiv:2603.18514
2026
nonstationary bandits
satisficing regret
online learning
Contextual Online Pricing with (Biased) Offline Data
Yixuan Zhang,
Ruihao Zhu,
and Qiaomin Xie
In Advances in Neural Information Processing Systems (NeurIPS)
2025
online pricing
offline data
contextual bandits
Unichain and aperiodicity are sufficient for asymptotic optimality of average-reward restless bandits
Yige Hong,
Qiaomin Xie ,
Yudong Chen,
and Weina Wang
Mathematics of Operations Research
2025
restless bandits
average reward
asymptotic optimality
Pretraining Decision Transformers with Reward Prediction for In-Context Multi-task Structured Bandit Learning
Subhojyoti Mukherjee,
Josiah P Hanna,
Qiaomin Xie ,
and Robert Nowak
In Reinforcement Learning Conference (RLC)
2025
decision transformers
in-context learning
structured bandits
Multi-task Representation Learning for Fixed Budget Pure-Exploration in Linear and Bilinear Bandits
Subhojyoti Mukherjee,
Qiaomin Xie ,
and Robert Nowak
In Reinforcement Learning Conference (RLC)
2025
pure exploration
multi-task learning
linear bandits
SPEED: Experimental Design for Policy Evaluation in Linear Heteroscedastic Bandits
Subhojyoti Mukherjee,
Qiaomin Xie ,
Josiah Hanna,
and Robert Nowak
In International Conference on Artificial Intelligence and Statistics (AISTATS)
2024
linear bandits
experimental design
policy evaluation
Multi-task Representation Learning for Pure Exploration in Bilinear Bandits
Subhojyoti Mukherjee,
Qiaomin Xie ,
Josiah Hanna,
and Robert Nowak
In Advances in Neural Information Processing Systems (NeurIPS)
2023
pure exploration
representation learning
bilinear bandits
Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption
Yige Hong,
Qiaomin Xie ,
Yudong Chen,
and Weina Wang
In Advances in Neural Information Processing Systems (NeurIPS), Spotlight,
2023
restless bandits
average reward
index policies
Near-Optimal Stochastic Bin-Packing in Large Service Systems with Time-Varying Item Sizes
Yige Hong,
Qiaomin Xie ,
and Weina Wang
In ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems
2024
bin packing
service systems
time-varying demand
Distributed Threshold-based Offloading for Heterogeneous Mobile Edge Computing
Xudong Qin,
Qiaomin Xie ,
and Bin Li
In International Conference on Distributed Computing Systems (ICDCS)
2023
mobile edge computing
offloading
distributed systems
RL-QN: A Reinforcement Learning Framework for Optimal Control of Queueing Systems
Bai Liu,
Qiaomin Xie ,
and Eytan Modiano
ACM Transactions on Modeling and Performance Evaluation of Computing Systems
2022
reinforcement learning
queueing networks
network control
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 characterize. Finding a good network control policy is of significant importance to achieve desirable network performance (e.g., high throughput or low delay). In this work, we consider using model-based reinforcement learning (RL) to learn the optimal control policy for queueing networks so that the average job delay (or equivalently the average queue backlog) is minimized. Traditional approaches in RL, however, cannot handle the unbounded state spaces of the network control problem. To overcome this difficulty, we propose a new algorithm, called RL for Queueing Networks (RL-QN), which applies model-based RL methods over a finite subset of the state space while applying a known stabilizing policy for the rest of the states. We establish that the average queue backlog under RL-QN with an appropriately constructed subset can be arbitrarily close to the optimal result. We evaluate RL-QN in dynamic server allocation, routing, and switching problems. Simulation results show that RL-QN minimizes the average queue backlog effectively.
Zero queueing for multi-server jobs
Weina Wang,
Qiaomin Xie ,
and Mor Harchol-Balter
In ACM Sigmetrics
2021
queueing systems
multi-server jobs
service systems
Greed works—online algorithms for unrelated machine stochastic scheduling
Varun Gupta,
Benjamin Moseley,
Marc Uetz,
and Qiaomin Xie
Mathematics of operations research
2020
online scheduling
stochastic systems
unrelated machines
Reinforcement learning for optimal control of queueing systems
Bai Liu,
Qiaomin Xie ,
and Eytan Modiano
In 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton)
2019
reinforcement learning
queueing systems
network control
Stochastic online scheduling on unrelated machines
Varun Gupta,
Benjamin Moseley,
Marc Uetz,
and Qiaomin Xie
In International Conference on Integer Programming and Combinatorial Optimization
2017
online scheduling
stochastic systems
unrelated machines
Centralized Congestion Control and Scheduling in a Datacenter
Devavrat Shah,
and Qiaomin Xie
arXiv preprint arXiv:1710.02548
2017
datacenter networks
congestion control
scheduling
Scheduling with Multi-level Data Locality: Throughput and Heavy-Traffic Optimality
Qiaomin Xie ,
Ali Yekkehkhany,
and Yi Lu
In 2016 IEEE Conference on Computer Communications (INFOCOM)
2016
scheduling
data locality
heavy traffic
Pandas: robust locality-aware scheduling with stochastic delay optimality
Qiaomin Xie ,
Mayank Pundir,
Yi Lu,
Cristina L Abad,
and Roy H Campbell
IEEE/ACM Transactions on Networking
2016
scheduling
data locality
delay optimality
Power of d Choices for Large-Scale Bin Packing: A Loss Model
Qiaomin Xie ,
Xiaobo Dong,
Yi Lu,
and R Srikant
In ACM Sigmetrics
2015
bin packing
large-scale systems
load balancing
Priority algorithm for near-data scheduling: Throughput and heavy-traffic optimality
Qiaomin Xie ,
and Yi Lu
In 2015 IEEE Conference on Computer Communications (INFOCOM)
2015
scheduling
data locality
heavy traffic
Degree-guided map-reduce task assignment with data locality constraint
Qiaomin Xie ,
and Yi Lu
In 2012 IEEE International Symposium on Information Theory Proceedings
2012
task assignment
data locality
MapReduce
Join-idle-queue: A novel load balancing algorithm for dynamically scalable web services
Yi Lu,
Qiaomin Xie ,
Gabriel Kliot,
Alan Geller,
James R Larus,
and Albert Greenberg
Performance Evaluation
2011
Best Paper Award
load balancing
queueing systems
web services
2026
Optimal Regret for Policy Optimization in Average Reward MDPs Without Mixing
William Powell,
Jeongyeol Kwon,
Qiaomin Xie ,
and Hanbaek Lyu
In Reinforcement Learning Conference (RLC)
2026
policy optimization
average-reward MDPs
regret
Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs
Tianhao Wu,
Matthew Zurek,
Weina Wang,
and Qiaomin Xie
In Conference on Learning Theory (COLT)
2026
weakly-coupled MDPs
restless bandits
sample complexity
Wasserstein-p Central Limit Theorem Rates: From Local Dependence to Markov Chains
Yixuan Zhang,
and Qiaomin Xie
In ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems
2026
Best Student Paper
central limit theorem
Wasserstein distance
dependent data
Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive Stochastic Approximation
Yixuan Zhang,
Dongyan (Lucy) Huo,
Yudong Chen,
and Qiaomin Xie
Operations Research
2026
stochastic approximation
coupling
steady-state convergence
On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimization
Yixuan Zhang,
Ruihao Zhu,
and Qiaomin Xie
arXiv preprint arXiv:2603.18514
2026
nonstationary bandits
satisficing regret
online learning
Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes
Dongyan Huo,
Yudong Chen,
and Qiaomin Xie
Mathematics of Operations Research
2026
linear stochastic approximation
Markovian data
bias extrapolation
2025
Offline Actor-Critic for Average Reward MDPs
William Powell,
Jeongyeol Kwon,
Qiaomin Xie ,
and Hanbaek Lyu
In Advances in Neural Information Processing Systems (NeurIPS)
2025
offline RL
actor-critic
average-reward MDPs
Contextual Online Pricing with (Biased) Offline Data
Yixuan Zhang,
Ruihao Zhu,
and Qiaomin Xie
In Advances in Neural Information Processing Systems (NeurIPS)
2025
online pricing
offline data
contextual bandits
Unichain and aperiodicity are sufficient for asymptotic optimality of average-reward restless bandits
Yige Hong,
Qiaomin Xie ,
Yudong Chen,
and Weina Wang
Mathematics of Operations Research
2025
restless bandits
average reward
asymptotic optimality
Pretraining Decision Transformers with Reward Prediction for In-Context Multi-task Structured Bandit Learning
Subhojyoti Mukherjee,
Josiah P Hanna,
Qiaomin Xie ,
and Robert Nowak
In Reinforcement Learning Conference (RLC)
2025
decision transformers
in-context learning
structured bandits
Multi-task Representation Learning for Fixed Budget Pure-Exploration in Linear and Bilinear Bandits
Subhojyoti Mukherjee,
Qiaomin Xie ,
and Robert Nowak
In Reinforcement Learning Conference (RLC)
2025
pure exploration
multi-task learning
linear bandits
Stable Offline Value Function Learning with Bisimulation-based Representations
Brahma S. Pavse,
Yudong Chen,
Qiaomin Xie ,
and Josiah P. Hanna
In International Conference on Machine Learning (ICML)
2025
offline RL
value functions
representation learning
A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression
Yixuan Zhang,
Dongyan (Lucy) Huo,
Yudong Chen,
and Qiaomin Xie
In ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems
2025
stochastic gradient descent
Lyapunov analysis
robust regression
Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Way
Jeongyeol Kwon,
Luke Dotson,
Yudong Chen,
and Qiaomin Xie
In International Conference on Artificial Intelligence and Statistics (AISTATS)
2025
linear stochastic approximation
two timescales
constant stepsize
Coupling-based Convergence Diagnostic and Stepsize Scheme for Stochastic Gradient Descent
Xiang Li,
and Qiaomin Xie
In AAAI Conference on Artificial Intelligence
2025
stochastic gradient descent
coupling
stepsize selection
2024
The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize
Dongyan (Lucy) Huo,
Yixuan Zhang,
Yudong Chen,
and Qiaomin Xie
In Advances in Neural Information Processing Systems (NeurIPS), Spotlight
2024
stochastic approximation
constant stepsize
Markovian noise
Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation
Yixuan Zhang,
and Qiaomin Xie
In Reinforcement Learning Conference (RLC)
2024
Q-learning
constant stepsize
distributional convergence
Inception: Efficiently Computable Misinformation Attacks on Markov Games
Jeremy McMahan,
Young Wu,
Yudong Chen,
Xiaojin Zhu,
and Qiaomin Xie
In Reinforcement Learning Conference (RLC)
2024
Markov games
misinformation attacks
learning security
Roping in Uncertainty: Robustness and Regularization in Markov Games
Jeremy McMahan,
Giovanni Artiglio,
and Qiaomin Xie
In International Conference on Machine Learning (ICML)
2024
Markov games
robustness
regularization
Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value
Young Wu,
Jeremy McMahan,
Yiding Chen,
Yudong Chen,
Xiaojin Zhu,
and Qiaomin Xie
In International Conference on Machine Learning (ICML)
2024
Markov games
Nash equilibrium
game modification
Learning to Stabilize Online Reinforcement Learning in Unbounded State Spaces
Brahma S. Pavse,
Matthew Zurek,
Yudong Chen,
Qiaomin Xie ,
and Josiah P. Hanna
In International Conference on Machine Learning (ICML)
2024
online RL
stability
unbounded state spaces
Near-Optimal Stochastic Bin-Packing in Large Service Systems with Time-Varying Item Sizes
Yige Hong,
Qiaomin Xie ,
and Weina Wang
In ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems
2024
bin packing
service systems
time-varying demand
Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive Stochastic Approximation
Yixuan Zhang,
Dongyan (Lucy) Huo,
Yudong Chen,
and Qiaomin Xie
In ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems
2024
stochastic approximation
coupling
constant stepsize
SPEED: Experimental Design for Policy Evaluation in Linear Heteroscedastic Bandits
Subhojyoti Mukherjee,
Qiaomin Xie ,
Josiah Hanna,
and Robert Nowak
In International Conference on Artificial Intelligence and Statistics (AISTATS)
2024
linear bandits
experimental design
policy evaluation
Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements
Emmanouil-Vasileios Vlatakis-Gkaragkounis,
Angeliki Giannou,
Yudong Chen,
and Qiaomin Xie
In International Conference on Artificial Intelligence and Statistics (AISTATS), Oral
2024
variational inequalities
stochastic optimization
ergodicity
Data Poisoning to Fake a Nash Equilibrium in Markov Games
Young Wu,
Jeremy McMahan,
Xiaojin Zhu,
and Qiaomin Xie
In AAAI Conference on Artificial Intelligence
2024
Markov games
data poisoning
Nash equilibrium
Effectiveness of Constant Stepsize in Markovian LSA and Statistical Inference
Dongyan (Lucy) Huo,
Yudong Chen,
and Qiaomin Xie
In AAAI Conference on Artificial Intelligence
2024
linear stochastic approximation
statistical inference
constant stepsize
Exact Policy Recovery in Offline RL with Both Heavy-Tailed Rewards and Data Corruption
Yiding Chen,
Xuezhou Zhang,
Qiaomin Xie ,
and Xiaojin Zhu
In AAAI Conference on Artificial Intelligence
2024
offline RL
data corruption
robust learning
Optimal Attack and Defense for Reinforcement Learning
Jeremy McMahan,
Young Wu,
Xiaojin Zhu,
and Qiaomin Xie
In AAAI Conference on Artificial Intelligence
2024
reinforcement learning
adversarial attacks
defense
2023
Multi-task Representation Learning for Pure Exploration in Bilinear Bandits
Subhojyoti Mukherjee,
Qiaomin Xie ,
Josiah Hanna,
and Robert Nowak
In Advances in Neural Information Processing Systems (NeurIPS)
2023
pure exploration
representation learning
bilinear bandits
Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption
Yige Hong,
Qiaomin Xie ,
Yudong Chen,
and Weina Wang
In Advances in Neural Information Processing Systems (NeurIPS), Spotlight,
2023
restless bandits
average reward
index policies
Distributed Threshold-based Offloading for Heterogeneous Mobile Edge Computing
Xudong Qin,
Qiaomin Xie ,
and Bin Li
In International Conference on Distributed Computing Systems (ICDCS)
2023
mobile edge computing
offloading
distributed systems
Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes
Zihan Zhang,
and Qiaomin Xie
In Conference on Learning Theory (COLT)
2023
average-reward MDPs
model-free RL
sample complexity
Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes
Dongyan (Lucy) Huo,
Yudong Chen,
and Qiaomin Xie
In ACM Sigmetrics
2023
linear stochastic approximation
Markovian data
constant stepsize
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
Qiaomin Xie ,
Yudong Chen,
Zhaoran Wang,
and Zhuoran Yang
Mathematics of Operations Research
2023
Markov games
function approximation
correlated equilibrium
We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games with simultaneous moves. To incorporate function approximation, we consider a family of Markov games where the reward function and transition kernel possess a linear structure. Both the offline and online settings of the problems are considered. In the offline setting, we control both players and aim to find the Nash equilibrium by minimizing the duality gap. In the online setting, we control a single player playing against an arbitrary opponent and aim to minimize the regret. For both settings, we propose an optimistic variant of the least-squares minimax value iteration algorithm. We show that our algorithm is computationally efficient and provably achieves an O(d3H3T) upper bound on the duality gap and regret, where d is the linear dimension, H the horizon and T the total number of timesteps. Our results do not require additional assumptions on the sampling model. Our setting requires overcoming several new challenges that are absent in Markov decision processes or turn-based Markov games. In particular, to achieve optimism with simultaneous moves, we construct both upper and lower confidence bounds of the value function, and then compute the optimistic policy by solving a general-sum matrix game with these bounds as the payoff matrices. As finding the Nash equilibrium of a general-sum game is computationally hard, our algorithm instead solves for a coarse correlated equilibrium (CCE), which can be obtained efficiently. To our best knowledge, such a CCE-based scheme for optimism has not appeared in the literature and might be of interest in its own right.
Reward Poisoning Attacks on Offline Multi-Agent Reinforcement Learning
Young Wu,
Jermey McMahan,
Xiaojin Zhu,
and Qiaomin Xie
In AAAI Conference on Artificial Intelligence
2023
multi-agent RL
data poisoning
offline learning
2022
RL-QN: A Reinforcement Learning Framework for Optimal Control of Queueing Systems
Bai Liu,
Qiaomin Xie ,
and Eytan Modiano
ACM Transactions on Modeling and Performance Evaluation of Computing Systems
2022
reinforcement learning
queueing networks
network control
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 characterize. Finding a good network control policy is of significant importance to achieve desirable network performance (e.g., high throughput or low delay). In this work, we consider using model-based reinforcement learning (RL) to learn the optimal control policy for queueing networks so that the average job delay (or equivalently the average queue backlog) is minimized. Traditional approaches in RL, however, cannot handle the unbounded state spaces of the network control problem. To overcome this difficulty, we propose a new algorithm, called RL for Queueing Networks (RL-QN), which applies model-based RL methods over a finite subset of the state space while applying a known stabilizing policy for the rest of the states. We establish that the average queue backlog under RL-QN with an appropriately constructed subset can be arbitrarily close to the optimal result. We evaluate RL-QN in dynamic server allocation, routing, and switching problems. Simulation results show that RL-QN minimizes the average queue backlog effectively.
ORSuite: Benchmarking Suite for Sequential Operations Models
Christopher Archer,
Siddhartha Banerjee,
Mayleen Cortez,
Carrie Rucker,
Sean R. Sinclair,
Max Solberg,
Qiaomin Xie ,
and Christina Lee Yu
SIGMETRICS Performance Evaluation Review
2022
reinforcement learning
operations research
benchmarking
Reinforcement learning (RL) has received widespread attention across multiple communities, but the experiments have focused primarily on large-scale game playing and robotics tasks. In this paper we introduce ORSuite, an open-source library containing environments, algorithms, and instrumentation for operational problems. Our package is designed to motivate researchers in the reinforcement learning community to develop and evaluate algorithms on operational tasks, and to consider the true multi-objective nature of these problems by considering metrics beyond cumulative reward.
Nonasymptotic Analysis of Monte Carlo Tree Search
Devavrat Shah,
Qiaomin Xie ,
and Zhi Xu
Operations Research
2022
Monte Carlo tree search
planning
nonasymptotic analysis
2021
Learning While Playing in Mean-Field Games: Convergence and Optimality
Qiaomin Xie ,
Zhuoran Yang,
Zhaoran Wang,
and Andreea Minca
In International Conference on Machine Learning (ICML)
2021
mean-field games
learning dynamics
equilibrium
Zero queueing for multi-server jobs
Weina Wang,
Qiaomin Xie ,
and Mor Harchol-Balter
In ACM Sigmetrics
2021
queueing systems
multi-server jobs
service systems
2020
Dynamic Regret of Policy Optimization in Non-Stationary Environments
Yingjie Fei,
Zhuoran Yang,
Zhaoran Wang,
and Qiaomin Xie
In Advances in Neural Information Processing Systems (NeurIPS)
2020
policy optimization
nonstationarity
dynamic regret
POLY-HOOT: Monte-Carlo Planning in Continuous Space MDPs with Non-Asymptotic Analysis
Weichao Mao,
Kaiqing Zhang,
Qiaomin Xie ,
and Tamer Basar
In Advances in Neural Information Processing Systems (NeurIPS)
2020
Monte Carlo planning
continuous spaces
nonasymptotic analysis
Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret
Yingjie Fei,
Zhuoran Yang,
Yudong Chen,
Zhaoran Wang,
and Qiaomin Xie
In Advances in Neural Information Processing Systems (NeurIPS)
2020
risk-sensitive RL
regret
sample complexity
Stable Reinforcement Learning with Unbounded State Space
Devavrat Shah,
Qiaomin Xie ,
and Zhi Xu
In Learning for Dynamics and Control (L4DC)
2020
stability
unbounded state spaces
reinforcement learning
On Reinforcement Learning for Turn-based Zero-sum Markov Games
Devavrat Shah,
Varun Somani,
Qiaomin Xie ,
and Zhi Xu
In Proceedings of the 2020 ACM-IMS on Foundations of Data Science Conference
2020
Markov games
zero-sum games
reinforcement learning
Learning zero-sum simultaneous-move Markov games using function approximation and correlated equilibrium
Qiaomin Xie ,
Yudong Chen,
Zhaoran Wang,
and Zhuoran Yang
In Conference on Learning Theory
2020
Markov games
function approximation
correlated equilibrium
Non-asymptotic analysis of Monte Carlo tree search
Devavrat Shah,
Qiaomin Xie ,
and Zhi Xu
In ACM Sigmetrics
2020
Monte Carlo tree search
planning
nonasymptotic analysis
Greed works—online algorithms for unrelated machine stochastic scheduling
Varun Gupta,
Benjamin Moseley,
Marc Uetz,
and Qiaomin Xie
Mathematics of operations research
2020
online scheduling
stochastic systems
unrelated machines
2019
Reinforcement learning for optimal control of queueing systems
Bai Liu,
Qiaomin Xie ,
and Eytan Modiano
In 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton)
2019
reinforcement learning
queueing systems
network control
2018
Q-learning with nearest neighbors
Devavrat Shah,
and Qiaomin Xie
In Advances in Neural Information Processing Systems (NeurIPS)
2018
Q-learning
function approximation
continuous state spaces
2017
Stochastic online scheduling on unrelated machines
Varun Gupta,
Benjamin Moseley,
Marc Uetz,
and Qiaomin Xie
In International Conference on Integer Programming and Combinatorial Optimization
2017
online scheduling
stochastic systems
unrelated machines
Centralized Congestion Control and Scheduling in a Datacenter
Devavrat Shah,
and Qiaomin Xie
arXiv preprint arXiv:1710.02548
2017
datacenter networks
congestion control
scheduling
2016
Scheduling with Multi-level Data Locality: Throughput and Heavy-Traffic Optimality
Qiaomin Xie ,
Ali Yekkehkhany,
and Yi Lu
In 2016 IEEE Conference on Computer Communications (INFOCOM)
2016
scheduling
data locality
heavy traffic
Pandas: robust locality-aware scheduling with stochastic delay optimality
Qiaomin Xie ,
Mayank Pundir,
Yi Lu,
Cristina L Abad,
and Roy H Campbell
IEEE/ACM Transactions on Networking
2016
scheduling
data locality
delay optimality
2015
Power of d Choices for Large-Scale Bin Packing: A Loss Model
Qiaomin Xie ,
Xiaobo Dong,
Yi Lu,
and R Srikant
In ACM Sigmetrics
2015
bin packing
large-scale systems
load balancing
Priority algorithm for near-data scheduling: Throughput and heavy-traffic optimality
Qiaomin Xie ,
and Yi Lu
In 2015 IEEE Conference on Computer Communications (INFOCOM)
2015
scheduling
data locality
heavy traffic
2012
Degree-guided map-reduce task assignment with data locality constraint
Qiaomin Xie ,
and Yi Lu
In 2012 IEEE International Symposium on Information Theory Proceedings
2012
task assignment
data locality
MapReduce
2011
Join-idle-queue: A novel load balancing algorithm for dynamically scalable web services
Yi Lu,
Qiaomin Xie ,
Gabriel Kliot,
Alan Geller,
James R Larus,
and Albert Greenberg
Performance Evaluation
2011
Best Paper Award
load balancing
queueing systems
web services