6 papers
Online Control via Counterfactual Tracking
Yunzong Xu
We develop a method for online control that competes with general classes of causal policies, beyond the linear-controller classes used by most existing algorithms. Over a horizon…
Finite-Time Queue Peak Laws in Stochastic Networks: Logarithmic Scaling After Geometric Thresholds
Hao Liang, Cheng Tang, Yunzong Xu
We study finite-horizon queue peaks in generalized switches, a standard stochastic-network model in which many queues share constrained service resources. Arrivals may be dependent…
Optimal Hidden-Target Learning for Online Inventory Optimization on General Convex Sets
Anthony Pineci, Yunzong Xu
Online inventory optimization (OIO) is online convex optimization with physical memory: inventory carryover makes the feasible action set depend on the past. A natural principle, u…
Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure
Aleksandrs Slivkins, Yunzong Xu, Shiliang Zuo
We study the greedy (exploitation-only) algorithm in bandit problems with a known reward structure. We allow arbitrary finite reward structures, while prior work focused on a few s…
Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
Dylan J. Foster, Alexander Rakhlin, David Simchi-Levi +1
In the classical multi-armed bandit problem, instance-dependent algorithms attain improved performance on "easy" problems with a gap between the best and second-best arm. Are simil…
Phase Transitions in Bandits with Switching Constraints
David Simchi-Levi, Yunzong Xu
We consider the classical stochastic multi-armed bandit problem with a constraint that limits the total cost incurred by switching between actions to be no larger than a given swit…