In “Active Learning Ranking from Pairwise Preferences with Almost Optimal Query Complexity“, Ailon (2011) presents a method for ordering a set based on noisy comparisons of elements.  He proves that his adaptive method approximates the NP Hard optimal solution (Alon 2006) to within $(1+\epsilon)$ times the minimum error after $f(\epsilon^{-1}, n)$ comparisons where $f$ is a polynomial.  Ailon builds on the work of Kenyon-Mathieu and Schudy (2007) who also developed a polynomial time algorithm for approximate ranking.  The Kenyon-Mathieu and Schudy algorithm was not query efficient.

Related Posts via Categories

• AlphaGo is changing how the Game is Played
• Counterfactual Regret Minimization
• Link: In Two Moves, AlphaGo and Lee Sedol Redefined the Future
• A Short Informal Description of Partially Observable Markov Decision Processes
• University of Alberta Solves Poker
• A review of “Playing Atari with Deep Reinforcement Learning”
• An AI for 2048 — Part 1
• “Generalized Thompson sampling for sequential decision-making and causal inference”
• Reinforcement Learning for Linear Control Systems
• The 20 most striking papers, workshops, and presentations from NIPS 2012