Parametrized Stochastic Multi-armed Bandits with Binary Rewards

Details Parametrized Stochastic Multi-armed Bandits with Binary Rewards Parametrized Stochastic Multi-armed Bandits with Binary Rewards

2011-11-18

arxiv.org/abs/1111.4460v1

Computer Science

Learning

10 pages, 3 figures

Scientific paper

In this paper, we consider the problem of multi-armed bandits with a large, possibly infinite 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 Two-Phase Algorithm, and analyze its performance. We show upper bounds on the total regret which applies uniformly in time, for both the finite and infinite arm cases. The asymptotics of the finite arm bound show that for any $f \in \omega(\log(T))$, the total regret can be made to be $O(n \cdot f(T))$. In the infinite arm case, the total regret is $O(\sqrt{n^3 T})$.

Affiliated with

Also associated with

No associations

Rating

Parametrized Stochastic Multi-armed Bandits with Binary Rewards does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Parametrized Stochastic Multi-armed Bandits with Binary Rewards, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parametrized Stochastic Multi-armed Bandits with Binary Rewards will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-550237