← Back to all news
arXiv Machine Learning

Best Arm Identification for Bandits with Shifting Means

arXiv:2610. 10488v1 Announce Type: cross Abstract: We study the best arm identification problem in a stochastic environment with a novel form of adversarial perturbations, which we coin Shifting Means.

Related stories

arXiv Machine Learning
20h ago

The Price of Current-Effect Inference in Nonstationary Multi-Armed Bandits

The paper studies the trade‑off between maximizing rewards and accurately estimating current treatment effects in nonstationary multi‑armed bandits. For $K$‑armed bandits with H"older‑smooth mean rewards, the authors derive minimax bounds on expected dynamic regret under a high‑probability simultaneous coverage requirement for all current effects. They propose the TRACE algorithm, which achieves a regret–precision trade‑off that separates reward‑learning regret from the unavoidable cost of refreshing current‑effect estimates, and extend the method with an empirical‑Bernstein e‑process to adapt exploration while preserving worst‑case guarantees.

By Sharan Sahu, Martin T. Wells
reinforcement-learning
More like this →
arXiv Machine Learning
Jun 15

A Complexity Measure for Active Learning in Multi-group Mean Estimation

arXiv:2606. 14690v1 Announce Type: new Abstract: We study a \emph{max-risk} objective for active learning in a multi-group mean estimation $d$-armed bandits: a learner adaptively allocates a budget of $T$ samples across $d$ groups to minimize the worst-case uncertainty index $\max_{k\in[d]}\sigma_k^2/n_k$, where $\sigma_k$ is the standard deviation of the distribution of arm $d$, and $n_k$ is the number of times arm $d$ is sampled.

By Abdellah Aznag, Rachel Cummings, Adam N. Elmachtoub
benchmarks
More like this →
arXiv Machine Learning
6d ago

Transfer Learning in Bandits from Unknown Adaptive Policies: Problem-Dependent Lower and Upper Bounds

The paper investigates transfer learning in stochastic multi‑armed bandits when historical data come from an unknown adaptive policy. It establishes asymptotic problem‑dependent lower bounds and introduces the KL‑UCB‑Transfer algorithm, which combines online and historical data to achieve logarithmic regret with an improved constant under certain mean‑gap conditions. The study also relaxes the source‑target discrepancy assumption to a one‑sided condition, demonstrating that logarithmic regret can still be achieved under misspecification and identifying regimes of improvement, degradation, or loss of guarantee.

By Adrien Prevost, Timothee Mathieu, Waris Radji, Odalric-Ambrym Maillard
fine-tuning
More like this →
arXiv Machine Learning
Oct 8

Allocation Stability and Wald Inference under Variance-Aware UCB

The paper investigates when allocation stability is required for Gaussian inference in a two‑armed, fixed‑horizon variance‑aware UCB policy with bounded rewards that may change with the horizon. It establishes a precise criterion involving the reward gap and variances that determines whether the optimal‑arm count can be approximated deterministically with vanishing relative error, while noting that the suboptimal‑arm count is always stable. The authors prove that the ordinary Wald statistic for any fixed nonzero coefficient vector converges to a standard normal distribution provided the product of pull count and reward variance diverges for each arm; however, uniform Gaussian approximation over deterministic coefficient vectors holds only if the optimal‑arm count is stable. The analysis relies on a pathwise comparison with an auxiliary policy and joint limits for the rescaled optimal‑arm count and studentized sample‑mean errors.

By Yingying Fan, Yuxuan Han, Jinchi Lv, Xiaocong Xu, Zhengyuan Zhou
reinforcement-learning
More like this →