Research map / Learning theory and algorithms / Sample complexity
Tight Bounds for Learning RUMs from Small Slates
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that observing winning distributions on slates of size O(√n) suffices (and Ω(√n) is necessary) to approximately learn all choice probabilities of a random utility model, yielding faster learning algorithms and lower bounds for fractional k-deck and trace reconstruction.
Problem
Learning a random utility model (RUM) over n items from winning distributions observed only on small slates (size at most k), and determining the minimum slate size needed to predict winning distributions on all slates.
Approach
Connects RUM learning to approximating the bitwise AND function by low-degree polynomials: agreement of two RUMs on slates of size O(√n) implies near-agreement on all slates (via Sherstov's theorem), and a matching lower bound uses dual-polynomial distributions for AND to build RUMs that agree on small slates but differ on the full slate.
Key results
- Slates of size O(√n) suffice to predict all winning distributions of a RUM within arbitrarily small constant error, and a matching Ω(√n) lower bound holds with error 1/2 - ε for the full slate.
- Improper learning algorithm answers queries in time 2^{O(√(|T| ln(1/ε)))} after nO(√n) preprocessing; proper learning algorithm runs in time n^{O(n)} (or 2^{O(n)} via ellipsoid).
- Fractional k-deck and fractional trace reconstruction require k = Ω(√n) and e^{o(√n)} samples respectively, respectively, to recover first-bit marginals.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Observe winning distributions for all slates up to O(√n) | RUM learning · All RUMs on [n] | uniform additive prediction error: arbitrarily small, constant error | Helped |
| Restrict observations to slates of size o(√n) | RUM learning · Universal slate | prediction error: 1/2 − ϵ | Hurt |
| Use improper polynomial-approximation reconstruction instead of the previous implicit algorithm | RUM learning · All RUMs on [n] | running time: 2O(n) -> nO(√n) | Helped |
| Use sub-slates of size O(|T|/ln |T|) for a predetermined target slate | RUM learning · Predetermined slate T | running time: polynomial time | Helped |
Surprising findings
- Accessing only slates of size exactly k is insufficient; smaller slates are necessary for reconstruction (Observation 13).
- The query time of the improper learning algorithm does not improve with larger slate size in the first version, motivating a second algorithm whose query time decreases as k increases.
Limitations
- Algorithms run in time exponential in n; polynomial-time learning of full RUM remains open.
- Simulation result requires querying polynomially many sub-slates of size O(n/ln n) and is not polynomial for reducing slate size.
- No experiments; results are purely theoretical.
Experimental setup
Baselines: Chierichetti et al. 2023 LP-based algorithm
Builds on: Sherstov 2008 AND approximation theorem Huang and Viola 2022 polynomial for AND Chierichetti et al. 2021 RUM subsampling k-deck problem
Closest papers by meaning
- Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability (NeurIPS 2024 · similarity 0.85)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.84)
- Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality (NeurIPS 2025 · similarity 0.83)
- Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards (NeurIPS 2025 · similarity 0.83)
- Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret (NeurIPS 2026 · similarity 0.83)
- Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilities (NeurIPS 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.