5 papers
Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
Shaddin Dughmi, Yusuf Hakan Kalayci, Xinyu Liu
When uncertainty meets costly information gathering, a fundamental question emerges: which data points should we probe to unlock near-optimal solutions? Sparsification of stochasti…
Pure Exploration via Frank-Wolfe Self-Play
Xinyu Liu, Chao Qin, Wei You
We study pure exploration in structured stochastic multi-armed bandits, aiming to efficiently identify the correct hypothesis from a finite set of alternatives. For a broad class o…
Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features
Zixuan Xie, Xinyu Liu, Rohan Chandra +1
Linear TD() is one of the most fundamental reinforcement learning algorithms for policy evaluation. Previously, convergence rates are typically established under the assumption…
Linear -Learning Does Not Diverge in : Convergence Rates to a Bounded Set
Xinyu Liu, Zixuan Xie, Shangtong Zhang
-learning is one of the most fundamental reinforcement learning algorithms. It is widely believed that -learning with linear function approximation (i.e., linear -learning…
Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise
Xiaochi Qian, Zixuan Xie, Xinyu Liu +1
This paper establishes the first almost sure convergence rate and the first maximal concentration bound with exponential tails for general contractive stochastic approximation algo…