IEEE Transactions on Automatic Control, Vol.45, No.11, 2135-2140, 2000
On the value of learning for Bernoulli bandits with unknown parameters
In this paper, we investigate the multiarmed bandit problem, where each arm generates an infinite sequence of Bernoulli distributed rewards. The parameters of these Bernoulli distributions are unknown and initially assumed to be beta-distributed. Every time a bandit is selected, its beta-distribution is updated to new information in a Bayesian way. The objective is to maximize the long-term discounted rewards. We study the relationship between the necessity of acquiring additional information and the reward, This is done by considering two extreme situations, which occur when a bandit has been played N times: the situation where the decision maker stops Learning and the situation where the decision maker acquires full information about that bandit. We show that the difference in reward between this lower and upper bound goes to zero as N grows large.