Efficient-UCBV: An Almost Optimal Algorithm Using Variance Estimates

Authors

  • Subhojyoti Mukherjee Indian Institute of Technology Madras
  • K. P. Naveen Indian Institute of Technology Tirupati
  • Nandan Sudarsanam Indian Institute of Technology Madras, Robert Bosch Centre for Data Science and AI (RBC-DSAI)
  • Balaraman Ravindran Indian Institute of Technology Madras, Robert Bosch Centre for Data Science and AI (RBC-DSAI)

Keywords:

Bandits, UCB-Improved, UCBV, Regret

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, while taking into account the variance estimates to compute the arms' confidence bounds, similar to UCBV. Through a theoretical analysis we establish that EUCBV incurs a gap-dependent regret bound which 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 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.

Downloads

Published

2018-04-26

How to Cite

Mukherjee, S., Naveen, K. P., Sudarsanam, N., & Ravindran, B. (2018). Efficient-UCBV: An Almost Optimal Algorithm Using Variance Estimates. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/12110

Issue

Section

AAAI Technical Track: Reasoning under Uncertainty