TY - GEN

T1 - Parametrized stochastic multi-armed bandits with binary rewards

AU - Jiang, Chong

AU - Srikant, R.

PY - 2011

Y1 - 2011

N2 - In this paper, we consider the problem of multi-armed bandits with a large number of correlated arms. We assume that the arms have Bernoulli distributed rewards, independent across time, where the probabilities of success are parametrized by known attribute vectors for each arm, as well as an unknown preference vector, each of dimension n. For this model, we seek an algorithm with a total regret that is sub-linear in time and independent of the number of arms. We present such an algorithm, which we call the Three-phase Algorithm, and analyze its performance. We show an upper bound on the total regret which applies uniformly in time. The asymptotics of this bound show that for any f ∈ ω(log(T)), the total regret can be made to be O(n·f(T)), independent of the number of arms.

AB - In this paper, we consider the problem of multi-armed bandits with a large number of correlated arms. We assume that the arms have Bernoulli distributed rewards, independent across time, where the probabilities of success are parametrized by known attribute vectors for each arm, as well as an unknown preference vector, each of dimension n. For this model, we seek an algorithm with a total regret that is sub-linear in time and independent of the number of arms. We present such an algorithm, which we call the Three-phase Algorithm, and analyze its performance. We show an upper bound on the total regret which applies uniformly in time. The asymptotics of this bound show that for any f ∈ ω(log(T)), the total regret can be made to be O(n·f(T)), independent of the number of arms.

UR - http://www.scopus.com/inward/record.url?scp=80053170101&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80053170101&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:80053170101

SN - 9781457700804

T3 - Proceedings of the American Control Conference

SP - 119

EP - 124

BT - Proceedings of the 2011 American Control Conference, ACC 2011

T2 - 2011 American Control Conference, ACC 2011

Y2 - 29 June 2011 through 1 July 2011

ER -