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$).

Source link