The Bandit Channel

Motivated by distributed multi-armed bandit, we introduce the two-player L-armed "bandit channel" with independent Bernoulli rewards, where users choose actions (input) and observe rewards (output). We derive a bound on the error exponent as a minimum of two types of errors that we then analyze separately. We further study the mutual information and show that the support of the optimal input distribution is a subset of the three best arms. We also compute the Shannon upper bound of the capacity as a special case of a two-way channel. In the case of identically distributed arms, the upper and lower bounds are very close.