Assaf Zeevi

A Note on Performance Limitations in Bandit Problems with Side Information

Coauthor(s): Alexander Goldenshluger.

Download:

Adobe Acrobat PDF

Abstract:

We consider a sequential adaptive allocation problem which is formulated as a traditional two armed bandit problem but with one important modification: at each time step t, before selecting which arm to pull, the decision maker has access to a random variable Xt which provides information on the reward in each arm. Performance is measured as the fraction of time an inferior arm (generating lower mean reward) is pulled. We derive a minimax lower bound that proves that in the absence of sufficient statistical "diversity" in the distribution of the covariate X, a property that we shall refer to as lack of persistent excitation, no policy can improve on the best achievable performance in the traditional bandit problem without side information.

© Copyright 2011 IEEE.

Source: IEEE Transactions on Information Theory
Exact Citation:
Zeevi, Assaf, and Alexander Goldenshluger. "A Note on Performance Limitations in Bandit Problems with Side Information." IEEE Transactions on Information Theory 57, no. 3 (March 2011): 1707-1713.
Volume: 57
Number: 3
Pages: 1707-1713
Date: 3 2011