From PAC to Instance-Optimal Sample Complexity in the Plackett-Luce Model
This work addresses the sample efficiency challenge in ranking and selection tasks for applications like recommendation systems, offering an incremental improvement by optimizing instance-dependent complexity in a specific model.
The paper tackles the problem of PAC-learning the best item from subsetwise feedback in the Plackett-Luce model, achieving an optimal instance-dependent sample complexity of O(θ_{[k]}/k * Σ_{i=2}^n max(1, 1/Δ_i^2) ln(k/δ) ln(1/Δ_i)) and providing matching lower bounds, with numerical results validating the approach.
We consider PAC-learning a good item from $k$-subsetwise feedback information sampled from a Plackett-Luce probability model, with instance-dependent sample complexity performance. In the setting where subsets of a fixed size can be tested and top-ranked feedback is made available to the learner, we give an algorithm with optimal instance-dependent sample complexity, for PAC best arm identification, of $O\bigg(\frac{θ_{[k]}}{k}\sum_{i = 2}^n\max\Big(1,\frac{1}{Δ_i^2}\Big) \ln\frac{k}δ\Big(\ln \frac{1}{Δ_i}\Big)\bigg)$, $Δ_i$ being the Plackett-Luce parameter gap between the best and the $i^{th}$ best item, and $θ_{[k]}$ is the sum of the \pl\, parameters for the top-$k$ items. The algorithm is based on a wrapper around a PAC winner-finding algorithm with weaker performance guarantees to adapt to the hardness of the input instance. The sample complexity is also shown to be multiplicatively better depending on the length of rank-ordered feedback available in each subset-wise play. We show optimality of our algorithms with matching sample complexity lower bounds. We next address the winner-finding problem in Plackett-Luce models in the fixed-budget setting with instance dependent upper and lower bounds on the misidentification probability, of $Ω\left(\exp(-2 \tilde ΔQ) \right)$ for a given budget $Q$, where $\tilde Δ$ is an explicit instance-dependent problem complexity parameter. Numerical performance results are also reported.