In this paper, we introduce the Preselection Bandit problem, in which the learner preselects a subset of arms (choice alternatives) for a user, which then chooses the final arm from this subset. The learner is not aware of the user's preferences, but can learn them from observed choices. In our concrete setting, we allow these choices to be stochastic and model the user's actions by means of the Plackett-Luce model. The learner's main task is to preselect subsets that eventually lead to highly preferred choices. To formalize this goal, we introduce a reasonable notion of regret and derive lower bounds on the expected regret. Moreover, we propose algorithms for which the upper bound on expected regret matches the lower bound up to a logarithmic term of the time horizon.
The flexible Pre-Bandit problem has obvious connections to the dueling bandits resp. battling bandits setting, with the freedom of adjusting the size of comparison for each time instance. In @cite_2 , the effect of this flexibility is investigated in an active PAC-framework for finding the best arm under the PL model, while the active top-k-arm identification problem in this model is studied in @cite_11 . Recently, this scenario was considered in terms of a regret minimization problem with top- @math -ranking feedback in @cite_13 , although the authors do not provide an algorithm for dealing with winner feedback (as we do in this paper). Yet, they provide gap-dependent lower bounds for winner feedback for a slightly different notion of regret.
@cite_11 @cite_13 @cite_2
1518788040 8700100 2750919793 2132876566
This paper proposes a new method for the K-armed dueling bandit problem, a variation on the regular K-armed bandit problem that offers only relative feedback about pairs of arms. Our approach extends the Upper Confidence Bound algorithm to the relative setting by using estimates of the pairwise probabilities to select a promising arm and applying Upper Confidence Bound with the winner as a benchmark. We prove a sharp finite-time regret bound of order O(K log T) on a very general class of dueling bandit problems that matches a lower bound proven in (, 2012). In addition, our empirical results using real data from an information retrieval application show that it greatly outperforms the state of the art. We consider the problem of eciently exploring the arms of a stochastic bandit to identify the best subset of a specied size. Under the PAC and the xed-budget formulations, we derive improved bounds by using KL-divergence-based condence intervals. Whereas the application of a similar idea in the regret setting has yielded bounds in terms of the KL-divergence between the arms, our bounds in the pure-exploration setting involve the information" between the arms. In addition to introducing this novel quantity to the bandits literature, we contribute a comparison between strategies based on uniform and adaptive sampling for pure-exploration problems, nding evidence in favor of the latter. We study combinatorial multi-armed bandit with probabilistically triggered arms (CMAB-T) and semi-bandit feedback. We resolve a serious issue in the prior CMAB-T studies where the regret bounds contain a possibly exponentially large factor of 1 p*, where p* is the minimum positive probability that an arm is triggered by any action. We address this issue by introducing a triggering probability modulated (TPM) bounded smoothness condition into the influence maximization bandit and combinatorial cascading bandit satisfy this TPM condition. As a result, we completely remove the factor of 1 p* from the regret bounds, achieving significantly better regret bounds for influence maximization and cascading bandits than before. Finally, we provide lower bound results showing that the factor 1 p* is unavoidable for general CMAB-T problems, suggesting that the TPM condition is crucial in removing this factor. We consider the multi-armed bandit problem under the PAC ("probably approximately correct") model. It was shown by Even- (2002) that given n arms, a total of O((n e2)log(1 δ)) trials suffices in order to find an e-optimal arm with probability at least 1-δ. We establish a matching lower bound on the expected number of trials under any sampling policy. We furthermore generalize the lower bound, and show an explicit dependence on the (unknown) statistics of the arms. We also provide a similar bound within a Bayesian setting. The case where the statistics of the arms are known but the identities of the arms are not, is also discussed. For this case, we provide a lower bound of Θ((1 e2)(n+log(1 δ))) on the expected number of trials, as well as a sampling policy with a matching upper bound. If instead of the expected number of trials, we consider the maximum (over all sample paths) number of trials, we establish a matching upper and lower bound of the form Θ((n e2)log(1 δ)). Finally, we derive lower bounds on the expected regret, in the spirit of Lai and Robbins.