Abstract
We consider two regret minimisation problems over subsets of a finite ground set [n], with subset-wise relative preference information feedback according to the Multinomial logit choice model. The first setting requires the learner to test subsets of size bounded by a maximum size followed by receiving top-m rank-ordered feedback, while in the second setting the learner is restricted to play subsets of a fixed size k with a full ranking observed as feedback. For both settings, we devise new, order-optimal regret algorithms, and derive fundamental limits on the regret performance of online learning with subset-wise preferences. Our results also show the value of eliciting a general top m-rank-ordered feedback over single winner feedback (m=1).
Abstract (translated by Google)
URL
http://arxiv.org/abs/1903.00543