10 papers
Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs
Tianhao Wu, Matthew Zurek, Weina Wang +1
We study the sample complexity of learning in average-reward weakly-coupled Markov decision processes (WCMDPs) and Restless Bandits (RBs) under a generative model. Naive reduction…
Optimality of a Threshold Policy for a Queueing System with One Fast Server and Two Identical Slow Servers
Weina Wang, Taha Ameen, Yudong Chen +3
This paper studies the optimal control problem of a queueing system with three servers: one fast server and two identical slow servers. The two-server version of this problem, with…
Faster Fixed-Point Methods for Multichain MDPs
Matthew Zurek, Yudong Chen
We study value-iteration (VI) algorithms for solving general (a.k.a. multichain) Markov decision processes (MDPs) under the average-reward criterion, a fundamental but theoreticall…
Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
Matthew Zurek, Guy Zamir, Yudong Chen
We study offline reinforcement learning in average-reward MDPs, which presents increased challenges from the perspectives of distribution shift and non-uniform coverage, and has be…
Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
Guy Zamir, Matthew Zurek, Yudong Chen
Online reinforcement learning in infinite-horizon Markov decision processes (MDPs) remains less theoretically and algorithmically developed than its episodic counterpart, with many…
Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RL
Matthew Zurek, Yudong Chen
We study the sample complexity of finding an -optimal policy in average-reward Markov Decision Processes (MDPs) with a generative model. The minimax optimal span-based…