6 papers · 1 filter
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…
Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning
Xinyu Liu, Zixuan Xie, Shangtong Zhang
The Robbins-Siegmund theorem establishes the convergence of stochastic processes that are almost supermartingales and is one of the most commonly used approaches for analyzing stoc…
Measurement-Based Quantum Diffusion Models
Xinyu Liu, Jingze Zhuang, Wanda Hou +1
We introduce measurement-based quantum diffusion models that bridge classical and quantum diffusion theory through randomized weak measurements. The measurement-based approach natu…
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…