Bandit Learning with Positive Externalities
In many platforms, user arrivals exhibit a self-reinforcing behavior: future user arrivals are likely to have preferences similar to users who were satisfied in the past. In other words, arrivals exhibit positive externalities. We study multiarmed bandit (MAB) problems with positive externalities. We show that the self-reinforcing preferences may lead standard benchmark algorithms such as UCB to exhibit linear regret. We develop a new algorithm, Balanced Exploration (BE), which explores arms carefully to avoid suboptimal convergence of arrivals before sufficient evidence is gathered. We also introduce an adaptive variant of BE which successively eliminates suboptimal arms. We analyze their asymptotic regret, and establish optimality by showing that no algorithm can perform better.
In this paper, the authors study the effects of positive externalities in MAB. In real platforms such as news site, the positive externalities come from the fact that if one of the arms generates rewards, then the users who prefer that arm become more likely to arrive in the future. If the platform knows the user preferences or could infer it from data, the usual way for handling positive externalities is to use contextual bandits: the services are personalized for each kind of users. However, most of the time the contexts are not very informative about the user preferences.  The usual alternative is to consider that the reward process evolves during time, and hence to use adversarial bandits or piecewise stationary bandits. Here, the authors propose to take advantage of prior knowledge on how the reward process evolves during time: the positive externalities.   The positive externalities change the usual trade-off between exploration and exploitation. Indeed, the effects of the choices of the platform are amplified. If the platform chooses the optimal arm, then this choice is amplified by the arriving of the users that like the optimal arm. However, if the algorithm chooses a sub-optimal arm, the price to pay in terms of future rewards can be dramatic. In order to analyze the positive externality effect, the authors introduce the regret against an Oracle which knows the optimal arm.  Depending on the value of \alpha, which measures the strength of positive externalities, a regret lower bound of MAB with positive externalities is provided. Then they bring out that classical approaches are suboptimal. Firstly, they show that UCB algorithm achieves a linear regret for bandits with positive externalities. Secondly, they show that explore then exploit algorithm may incur a linear regret when \alpha > 1. A first algorithm called Balanced Exploration (BE) is introduced. In the exploration phase the arm which has the lowest cumulated reward is chosen, while in the exploitation phase the arm which has been the less chosen in the exploration phase is played. it is worth noting that BE algorithm needs only to know the time horizon. The analysis of this algorithm shows that it is near optimal. A second algorithm, that assumes that in addition to the time horizon the parameters of positive externalities are known (\alpha and \theta_a), is proposed. This algorithm uses an unbiased estimator of the mean reward thanks to the knowledge of the arrival probability. The algorithm plays the arm that has received the least rewards in order to explore. In order to exploit, the suboptimal arms are eliminated when their upper bounds are lesser that the lower bound of the estimated best arm. The authors show that Balanced Exploration with Arm Elimination is optimal.  I regret that there are no experiments because it could be interesting for the reader to observe the gap in performances between BE, where the arrival probabilities are unknown and BE-AE, where the arrival probabilities are known.  Overall, the paper is very interesting and I vote for acceptance.   Minor Comments: The notation \theta^\alpha line 151 is misleading. You use the notation power alpha for N_a^\alpha and for \theta^\alpha but it does not mean the same thing. I suggest to use \theta(\alpha). Line 196, there is a typo u_a(0) = \infty and not 0.