Tight Bounds for Learning RUMs from Small Slates

This paper studies the learning of Random Utility Models (RUMs). A RUM is a probability distribution $P$ over the set of permutations over $[n]$. Fix a permutation $\pi$ and consider any subset $T \subseteq [n]$, known as a slate. The winner of the slate (corresponding to $\pi$) is the highest ranked element in $T$ accordint to $\pi$. We can imagine fixing a slate $T$, and consider the distribution of the winner of the slate $T$ as we draw $\pi$ from $P$. In the problem of learning RUMs, one is given a set of slates, together with the corresponding distribution of the winner of that slate. The task is to reconstruct the distribution of the winner of every possible slate.

Specifically, this paper considers the problem when the example slates given to a learning algorithm are at most a size $k$. The main result of the paper is that having access to the winning distributions of all slates of size at most $O(k)$ is necessary and sufficient for the task of learning RUMs. The same result also holds if one has only sample access to the winning distributions of all slates of this size. The authors present two algorithms that achieve the upper bound: 1) a proper algorithm, that constructs a RUM in time $n^{O(n)}$, and thereafter, given any slate, returns an approximation to the winning distribution of that slate in polynomial time 2) an improper algorithm, that does not construct a RUM, but runs in time $n^{O(\sqrt{n})}$, and thereafter, given any slate, returns an approximation to the winning distribution of that slate in time $2^{O(\sqrt{n})}$. The latter algorithm thus, in time $n^{O(\sqrt{n})}$, approximates the winning distribution of the full slate $[n]$ in $l_\infty$, which is an improvement over the previous best running time of $2^{O(n)}$ for the same task, implicit in prior work. The latter algorithm can also be adapted to yield the following guarantee: given a prespecified slate $T \subseteq [n]$, one can approximate the winning distribution of $T$ in $l_\infty$ in time polynomial in $n$, by querying slates of size at most $O(|T|/\log|T|)$. The authors also show that any algorithm that only accesses slates of size $o(\sqrt{n})$ can not successfully learn the winning distribution of the full slate. This shows that their earlier two algorithms are optimal in the maximum size of the slates they access. Finally, the authors define fractional versions of two classic problems in the intersection of combinatorics and computer science: $k$-deck and trace reconstruction. Using their techniques for learning RUMs with small slates, they are able to obtain new results for the fractional versions of both these problems (similar quantitative results would be major breakthroughs for the original problems).

The upper bounds rely crucially on results by Sherstov in 2008, and on the state-of-the-art approximation of the AND function by low degree polynomials due to Huang and Viola, 2022. The lower bound is a reduction to a lower bound on the approximation of the AND function by low-degree polynomials, due to Bogdanov et al. 2016.

This paper studies the problem of learning a Random Utility Model with limited information. A RUM is a distribution on the symmetric group on $n$ letters and a slate is a nonempty subset of the universe of letters. The paper studies the problem of learning the RUM given access to the probabilities that a given letter $s$ is most preferred by a sample from the RUM out of all of the elements in a given slate $S$. The authors apply classical techniques to derive an information theoretic upper bound for the necessary size of a slate in order to learn the RUM to additive error $\epsilon$, which is complemented by a matching lower bound at the end of the paper. They then provide two algorithms bounding the sample complexity of learning the RUM with such slates: one relying on solving a linear program requiring $n^{O(n)}$ samples and another algorithm relying on polynomial approximations for the Boolean AND. The latter algorithm is then applied to demonstrate that large slates can be used to learn an RUM in polynomial time to constant accuracy. The paper concludes with applications of their techniques to two other problems in the intersection of combinatorics and CS theory.

A random utility model is defined by a distribution over permutations of $1,2,\dots,n$. Given a non-empty subset $S \subseteq \{1,2,\dots,n\}$, an oracle stochastically returns which one in $S$ is the highest according to this distribution. This paper considers the problem of estimating a random utility model from winning probabilities for small $S$.

• This paper first proposes an algorithm that queries all $S$ with $|S| = \tilde{O}(\sqrt{n})$ and then estimates a RUM by solving an LP. The authors shows that this estimated model has small error even for large $S$. This algorithm takes $n^{O(n)}$ time.
• Next the authors consider an approach of expressing RUMs by polynomials. The proposed algorithm again queries all $S$ with $|S| = \tilde{O}(\sqrt{n})$. However, as the expression of an estimated RUM does not require $n!$ dimensions, both the estimation and prediction takes $n^{\tilde{O}(\sqrt{n})}$ time.
• The authors also provide a lower bound. That is, if two RUMs coincide on all $S \subseteq [n]$ with $|S| = O(\sqrt{n})$, the error for $S = [n]$ can be very large.
• The last contributions are on the fractional versions of the $k$-deck and trace reconstruction problems. The authors give lower bounds on the sample complexity for these problems based on the RUM lower bound.

The paper considers the Random Utility Model (RUM) problem and gives upper and lower bound on plate size.

RUM is a classic economic model that is used to understand user behavior by modeling choices from subsets of available items. In the RUM problem, there is a set of element $[n]$ and there is a probability distribution $P$ over the permutation of $[n]$. The algorithm could query a set of $k$ elements, and either observe the one with the highest rank (sampled from $P$) or the winning distribution on these $k$ elements. The paper seeks to understand the optimal value of $k$, such that the algorithm could figure out the permutation distribution (up to small error) given all plate of size $k$. The answer turns out to be $k = \Theta(\sqrt{n})$.

In particular,

1. The upper bound shows that knowledge of choices from slates of size$O(\sqrt{n})$ allows approximating the choice distribution for any slate with high accuracy. Moreover, it gives an algorithm that learns RUMs efficiently: A proper learning algorithm with $n^{n}$ time and an improper learning algorithm with $n^{\sqrt{n}}$ time.
2. Lower bounds are derived, indicating that learning from slates smaller than $\sqrt{n}$ results in high prediction errors. These results also contribute to understanding the k-deck and trace reconstruction problems.

In terms of technique, the proofs rely on connections between RUM learning and the approximation of Boolean functions by polynomials. The paper leverages results from the approximation of the AND function to develop their bounds and algorithms.

Overall, the paper solves a meaningful problem and characterizes the optimal plater size. The drawback is that that query complexity and the runtime is exponential.

We thank the reviewers for their insights, and the time and efforts spent reviewing our work. We consider each comment carefully below, but let us begin by addressing a common concern regarding the computational complexity. While the asymptotic complexity of the algorithms is high, there are some interesting special cases for which the algorithms are practical.

1. Our learning algorithm is able to infer the winning distributions of slates up to size $\sim k^2$ by looking at the $\sim n^k$ slates of size at most $k$. For moderate values of $k$, e.g., constant $k$, this algorithm is practical and is a significant improvement over the trivial $\sim n^{k^2}$ algorithm.

2. For modest values of $n$, e.g., learn the winning distributions over the $n$ restaurants in a town, our algorithm only requires $\sim 2^{\sqrt{n} \lg n}$ queries to approximate the full-slate, while the previous best algorithm needs $\sim 2^{n}$ queries.

In general, we view our results as the necessary first steps towards understanding the learnability of RUMs, which has been a long-standing research question.

Since the CFP welcomes “Theory” contributions in “learning theory”, we hope that the theoretical nature of our contribution will not be seen as a limitation.

This paper has developed very strong results for the problem of learning RUMs. The improvement relative to previous work is enormous, improving the order of $n$ in the exponent itself, along with matching lower bounds. The analysis is technically sophisticated and interesting, connecting to boolean function analysis and polynomial approximation. This paper has very strong support from two reviewers and less support from two lower-confidence reviewers. One criticism from several reviewers is the exponential complexity, but the authors have shown that this is unavoidable and hence I do not find that this should be viewed as a weakness. Another criticism that came out during the discussion period with the reviewers is that the paper uses an existing connection with boolean function analysis and polynomial approximation; however, I am not convinced that this is a valid criticism since (as noted by another reviewer) boolean function analysis and polynomial approximation are entire fields of study. It does seem that some heavy lifting is done by the prior work of Sherstov (2008), but finding these connections and the authors' own analysis looks impressive. This work is a welcome addition to the proceedings.