Header menu link for other important links
X
Efficient-UCBV: An almost optimal algorithm using variance estimates
Published in
2018
Pages: 6417 - 6424
Abstract
We propose a novel variant of the UCB algorithm (referred to as Efficient-UCB-Variance (EUCBV)) for minimizing cumulative regret in the stochastic multi-armed bandit (MAB) setting. EUCBV incorporates the arm elimination strategy proposed in UCB-Improved (Auer and Ortner 2010), while taking into account the variance estimates to compute the arms' confidence bounds, similar to UCBV (Audibert, Munos, and Szepesvári 2009). Through a theoretical analysis we establish that EUCBV incurs a gap-dependent regret bound of O Kσ max 2 log( T Δ2/K) after T trials, where Δ is the min-Δ imal gap between optimal and sub-optimal arms; the above bound is an improvement over that of existing state-of-the-art UCB algorithms (such as UCB1, UCB-Improved, UCBV, MOSS). Further, EUCBV incurs a gap-independent regret bound of O KT which is an improvement over that of UCB1, UCBV and UCB-Improved, while being comparable with that of MOSS and OCUCB. Through an extensive numerical study we show that EUCBV significantly outperforms the popular UCB variants (like MOSS, OCUCB, etc.) as well as Thompson sampling and Bayes-UCB algorithms. Copyright © 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
About the journal
Journal32nd AAAI Conference on Artificial Intelligence, AAAI 2018
Open AccessNo