2019/03/01 by Aadirupa Saha, Saha, Aadirupa, Aditya Gopalan +1
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #Imbalanced Data Classification Techniques #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1903.00558
openalex publication_date 2019/03/01 · openalex created_date 2022/10/05 · openalex updated_date 2026/07/28
We consider PAC-learning a good item from k-subsetwise feedback information\nsampled from a Plackett-Luce probability model, with instance-dependent sample\ncomplexity performance. In the setting where subsets of a fixed size can be\ntested and top-ranked feedback is made available to the learner, we give an\nalgorithm with optimal instance-dependent sample complexity, for PAC best arm\nidentification, of O\( frac\θ[k]k\∑i =\n2n\max\(1,\(1)/(\Δi2)\) \ln\(k)/(\δ)\(\ln\n\(1)/(\Δi)\)\), \Δi being the Plackett-Luce parameter\ngap between the best and the ith best item, and \θ[k] is the sum\nof the pl , parameters for the top-k items. The algorithm is based on a\nwrapper around a PAC winner-finding algorithm with weaker performance\nguarantees to adapt to the hardness of the input instance. The sample\ncomplexity is also shown to be multiplicatively better depending on the length\nof rank-ordered feedback available in each subset-wise play. We show optimality\nof our algorithms with matching sample complexity lower bounds. We next address\nthe winner-finding problem in Plackett-Luce models in the fixed-budget setting\nwith instance dependent upper and lower bounds on the misidentification\nprobability, of \Ω\(\exp(-2 \Δ Q) \) for a given\nbudget Q, where \Δ is an explicit instance-dependent problem\ncomplexity parameter. Numerical performance results are also reported.\n