DocumentCode :
1451953
Title :
A Note on Performance Limitations in Bandit Problems With Side Information
Author :
Goldenshluger, Alexander ; Zeevi, Assaf
Author_Institution :
Dept. of Stat., Haifa Univ., Haifa, Israel
Volume :
57
Issue :
3
fYear :
2011
fDate :
3/1/2011 12:00:00 AM
Firstpage :
1707
Lastpage :
1713
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.
Keywords :
covariance analysis; minimax techniques; random processes; covariate property; minimax lower bound; random variable; sequential adaptive allocation problem; side information; sufficient statistical diversity; two armed bandit problem; Complexity theory; Context; Error probability; Linear regression; Random variables; Resource management; Testing; Allocation rule; inferior sampling rate; lower bound; side information; two-armed bandit;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.2011.2104450
Filename :
5714284
Link To Document :
بازگشت