Xiao-Jing Zhang

Variance-Aware Non-Stationary Bandits:All-Budget Regret Bounds and Adaptation Costs

Low reward variance reduces estimation cost, but does not eliminate monitoring of arms that may improve while unobserved. We refine the variance--variation tradeoff and characterize how both costs depend on supplied variance and variation budgets in bounded, non-stationary multi-armed bandits. Let $A$ be the number of...