Is there a generalisation of $k$-handed bandit to $n$-handed player in a sense that the sample is taken not from just one distribution (one bandit from $k$ bandits) but from n distributons ($n$ bandits) where $n<k$?

In other words instead of predicting best ad banner in terms of click though rate I'd need to predict a set of ad banners that will be shown simultaneously on the page (but only one clicked or not and it does not matter which).

Or yet another way to formulate is to say that the generalized $n$-arm is a vector of bandits arms instead of one banidts arm. The pool of bandits is fixed.

  • $\begingroup$ If there are no interactions, you could choose the top n arms. Otherwise you have you define the quality of the set. And then you run into a combinatorial optimization problem. $\endgroup$
    – Emre
    Feb 23, 2016 at 3:03
  • $\begingroup$ Thanks Emre, taking top n arms will probably work to some extent. What I am after is how to design efficient learning algorithm when you don't show just one ad but many at the same time. There is obviously a very strong interaction because click on one ad steals it from the others. It appears to me to be a very common problem for online shops etc. so I thought there will be some work done around exactly this type of the problem already. It is more of a practical concern where you don't want to build yet another web shop just to test the ctr of your ads one by one. $\endgroup$
    – Diego
    Feb 23, 2016 at 10:00
  • 1
    $\begingroup$ If n is fixed: Multi-armed bandit problems with multiple plays and switching cost $\endgroup$
    – Emre
    Feb 23, 2016 at 16:58


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.