UC San Diego

PAC maximum selection (maxing) and ranking of $n$ elements via random

pairwise comparisons have diverse applications and have been studied

under many models and assumptions. We consider $(\epsilon,\delta)$-PAC

maxing and ranking using pairwise comparisons for \nobreak{general}

probabilistic models. We present a comprehensive understanding of

three important problems in PAC preference learning: maxing, ranking,

and estimating \emph{all} pairwise preference probabilities, in the

adaptive setting.

{\bf SST + STI:} We consider $(\epsilon,\delta)$-PAC maximum-selection

and ranking using pairwise comparisons for \nobreak{general}

probabilistic models whose comparison probabilities satisfy

\emph{strong stochastic transitivity (SST)} and \emph{stochastic

triangle inequality (STI)}. Modifying the popular knockout

tournament, we propose a simple maximum-selection algorithm that uses

$\mathcal{O}\left(\frac{n}{\epsilon^2} \log

\frac1{\delta}\right)$ comparisons, optimal up to a constant

factor. We then derive a general framework that uses noisy binary

search to speed up many ranking algorithms, and combine it with merge

sort to obtain a ranking algorithm that uses $\mathcal{O}\left(\frac

n{\epsilon^2}\log n(\log \log n)^3\right)$ comparisons for

$\delta=\frac1n$, optimal up to a $(\log \log n)^3$ factor.

{\bf SST +/- STI and Borda:} With just one simple natural assumption:

\emph{strong stochastic transitivity (SST)}, we show that maxing can

be performed with linearly many comparisons yet ranking requires

quadratically many. With no assumptions at all, we show that for the

Borda-score metric, maximum selection can be performed with linearly

many comparisons and ranking can be performed with $\cO(n\log n)$

comparisons.

{\bf General Transitive Models} With just \emph{Weak Stochastic

Transitivity (WST)}, we show that maxing requires $\Omega(n^2)$

comparisons and with slightly more restrictive \emph{Medium Stochastic

Transitivity (MST)}, we present a linear complexity maxing

algorithm. With \emph{Strong Stochastic Transitivity (SST)} and

\emph{Stochastic Triangle Inequality (STI)}, we derive a ranking

algorithm with optimal $\mathcal{O}(n\log n)$ complexity and an

optimal algorithm that estimates all pairwise preference

probabilities.

{\bf Sequential and Competitive} We extend the well-known

\emph{secretary problem} to a probabilistic setting, and apply the

intuition gained to derive the first query-optimal sequential

algorithm for probabilistic-maxing. Furthermore, departing from

previous assumptions, the algorithm and performance guarantees apply

even for infinitely many items, hence in particular do not require

a-priori knowledge of the number of items. The algorithm has linear

complexity, and is optimal also in the streaming setting and for both

traditional- and dueling-bandits. In a non-streaming setting, a

modification of the algorithm is \emph{competitive} in that it

requires essentially the lowest number of queries not just in the

worst case, but for every underlying distribution.