Bandits Dueling on Partially Ordered Sets
We address the problem of dueling bandits defined on partially ordered sets, or posets. In this setting, arms may not be comparable, and there may be several (incomparable) optimal arms. We propose an algorithm, UnchainedBandits, that efficiently finds the set of optimal arms -the Pareto front-of any poset even when pairs of comparable arms cannot be a priori distinguished from pairs of incomparable arms, with a set of minimal assumptions. This means that UnchainedBandits does not require information about comparability and can be used with limited knowledge of the poset. To achieve this, the algorithm relies on the concept of decoys, which stems from social psychology. We also provide theoretical guarantees on both the regret incurred and the number of comparison required by UnchainedBandits, and we report compelling empirical results.
The paper addresses a variant of the dueling bandit problem where certain comparisons are not resolvable by the algorithm. In other words, whereas dueling bandit algorithms deal with tournaments (i.e. fully connected directed graphs), the algorithms in this paper deal with more general directed graphs.
The authors offer only vague conceptual reasons for the significance of this new problem setting, however from a practical point of view, this is an extremely important problem that the existing literature does not address at all. More specifically, ties between arms are major stumbling blocks for most dueling bandit algorithms; indeed, many papers in the literature explicitly exclude problems with ties from their analyses. On the other hand, in practice one often has to deal with "virtual ties": these are pairs of arms that could not be distinguished from each other given the number of samples available to the algorithm.
A good example to keep in mind is a product manager at Bing or Google who has to pick the best ranker from a pool of a hundred proposed rankers using pairwise interleaved comparisons, but only has access to say %1 of the traffic for a week: if it happens to be that there are certain pairs of rankers in the pool that are so similar to each other that they couldn't be distinguished from each other even using the entirety of the available samples, then for all practical purposes the are ties in the resulting dueling bandit problem. So, our product manager would want an algorithm that would not waste the whole traffic on such virtual ties.
The authors propose two algorithms that deal with this problem under two different levels of generality:
1- an algorithm to find an \eps-approximation of the pareto front in the more general social poset setting, which is an extension of the Condorcet assumption in the full tournament case;
2- as algorithm to find the exact pareto front in the much more restrictive poset setting, which is an analogue of the total ordering assumption for regular dueling bandits.
I personally find the former much more interesting and important because there is plenty of experimental evidence that transitivity is very unlikely to hold in practice, although the second algorithm could lead to very interesting future work.
The authors use a peeling method that uses epochs with exponentially increasing lengths to gradually eliminate arms with smaller and smaller gaps. In the analysis, this has the effect of rendering the regret incurred from most edges in the comparison graph negligible, hence the linear dependence on the gaps in regret bounds. The price that one pays for this simpler proof technique is an extra factor of K, which in the worst case makes the bound of the form O(K^2 log T / \Delta).
As a general comment, I think it would be a good idea for the authors to devote more space in the paper to situating the results presented here with respect to the existing dueling bandit literature: I think that would be much more helpful to the reader than the lengthy discussion on decoys, for instance. In particular, there is a very precise lower bound proven for Condorcet dueling bandits in (Komiyama et al, COLT 2015), and I think it's important for the authors to specify the discrepancy between the result in Theorem 1 and this lower bound in the full tournament setting when \eps is smaller than the smallest gap in the preference matrix.
Furthermore, given the numerous open questions that arise out of this work, I highly recommend having a lengthier discussion of future work. For instance, there is some recent work on using Thompson Sampling for dueling bandits in (Wu and Liu, NIPS 2016) and it is an interesting question whether or not their methods could be extended to this setting. Moreover, it would be interesting to find out if more refined results for the von Neumann problem, such as those presented in (Balsubramani et al, COLT 2016) can be transported here.
Another criticism that I have of the write-up is that in the experiments it's not at all clear how IF2 and RUCB were modified, so please elaborate on the specifics of that.