Upper-Confidence-Bound Algorithms for Active Learning in Multi-armed Bandits

DOI10.1007/978-3-642-24412-4_17MaRDI QIDQ3093949zbMATH OpenOpenAlexFDO

Authors Alexandra Carpentier, Alessandro Lazaric, Mohammad Ghavamzadeh, Rémi Munos, Peter Auer

Publication date 19 October 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.04523

Mathematics Subject Classification ID

Rationality and learning in game theory (91A26) Probabilistic games; gambling (91A60)

Abstract: In this paper, we study the problem of estimating uniformly well the mean values of several distributions given a finite budget of samples. If the variance of the distributions were known, one could design an optimal sampling strategy by collecting a number of independent samples per distribution that is proportional to their variance. However, in the more realistic case where the distributions are not known in advance, one needs to design adaptive sampling strategies in order to select which distribution to sample from according to the previously observed samples. We describe two strategies based on pulling the distributions a number of times that is proportional to a high-probability upper-confidence-bound on their variance (built from previous observed samples) and report a finite-sample performance analysis on the excess estimation error compared to the optimal allocation. We show that the performance of these allocation strategies depends not only on the variances but also on the full shape of the distributions.

Recommendations

• Active Learning in Multi-armed Bandits
• Probability bounds for active learning in the regression problem
• Infinite Arms Bandit: Optimality via Confidence Bounds
• Minimax Bounds for Active Learning
• Minimax Bounds for Active Learning

Cited in

(10)

• Exploration-exploitation tradeoff using variance estimates in multi-armed bandits
• Foraging decisions as multi-armed bandit problems: applying reinforcement learning algorithms to foraging data
• An Efficient Algorithm for Learning with Semi-bandit Feedback
• Tuning Bandit Algorithms in Stochastic Environments
• Active Learning in Multi-armed Bandits
• scientific article; zbMATH DE number 6982311 (Why is no real title available?)
• Learning the distribution with largest mean: two bandit frameworks
• On the bias, risk, and consistency of sample means in multi-armed bandits
• Best arm identification for contaminated bandits
• Sequential design for ranking response surfaces

This page was built for publication: Upper-Confidence-Bound Algorithms for Active Learning in Multi-armed Bandits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3093949)