Bandits with Single-Peaked Preferences and Limited Resources

AI summary

Overview

• Research area: Online stochastic matching / combinatorial multi-armed bandits, intersecting with single-peaked preferences from social choice theory.
• Technical level: Advanced. The paper assumes familiarity with regret analysis, UCB confidence sets, NP-hardness reductions, dynamic programming, and PQ trees.
• Scope: The paper defines a budget-constrained online matching problem, proves a computational hardness barrier, and shows that assuming single-peaked preferences enables efficient offline and online algorithms with sublinear regret.

What This Paper Is About

The paper studies a sequential decision problem in which an algorithm repeatedly matches a fixed set of U users to K arms over T rounds, where each arm has a cost and the total cost of the arms selected in each round must stay within a known budget B. Without structural assumptions on user preferences, computing the best matching is NP-hard, which makes learning it online infeasible. The authors therefore assume that preferences are single-peaked: there exists an ordering of the arms such that every user's expected reward rises to a peak and then falls, and they ask whether this structure can be exploited to build efficient algorithms with standard (non-approximate) regret guarantees.

Key Contributions

1. Statistical hardness of single-peaked instances. The authors show that even with structural knowledge, the learning problem does not become easier statistically. With known user peaks, the worst-case regret over PSP instances is Ω(max{U√T, √(TK)}); with unknown peaks it is Ω(U√(TK)), matching the lower bound for general preferences.

2. An efficient optimal offline algorithm, SP-Matching. For a known single-peaked matrix, SP-Matching computes the optimal budget-feasible matching in O(K²(U+B)) time (stated as O(K²B + K²U) in the introduction), using a dynamic program built on a structural lemma about "closest arm to the peak" assignments.

3. An optimistic online algorithm, MvM, for known SP structure. When both the SP order and user peaks are known, MvM builds a "maximal matrix" inside the confidence set (Lemma 6) and solves the offline problem on it each round, achieving regret O(U√(TK ln T)) with per-round runtime O(K²U + K²B).

4. An explore-then-commit algorithm, EMC, for unknown SP structure. EMC uses a novel PQ tree-based procedure called Extract-Order to recover an approximately single-peaked order from empirical estimates, projects onto a nearby SP matrix, and commits to a matching. The abstract reports regret Õ(UKT^{2/3}), with all steps running in poly(U, K, B) time.

Main Findings

• The general case is intractable. Theorem 1 shows it is NP-hard to approximate argmax over feasible matchings within any factor better than (1 − 1/e), via a reduction from the maximum coverage problem. Consequently, an efficient online algorithm with sublinear regret cannot exist without structural assumptions.

• An oracle-based UCB algorithm is statistically optimal but impractical. Corollary 2 states there exists a UCB-based algorithm achieving O(U√(KT log T)) regret, optimal up to logarithmic factors, but it requires an optimization oracle that solves an NP-hard problem every round.

• Approximate regret is a weaker fallback. The paper notes that sublinear α-regret is computationally feasible in this setting (e.g., α = 0.5 using a greedy oracle), but this compares against the best efficiently computable solution rather than the true optimum.

• Single-peakedness simplifies computation, not statistics. Theorem 3's lower bounds match the general-preference bound, so the SP assumption alone does not reduce the statistical difficulty — it removes the computational barrier.

• A structural lemma drives the offline algorithm. Lemma 4: for a PSP matrix and a selected arm subset S = {k₁ < … < k_m}, each user whose peak lies between k_j and k_{j+1} is optimally assigned to k_j or k_{j+1}; users outside the range go to the extreme arms. This yields the DP recurrence for F(k, b).

• The confidence set has a unique element-wise maximal matrix. Lemma 6 gives a closed form for P^t as a minimum of upper confidence bounds along the interval between arm k and the user's peak. This lets MvM avoid maximizing over a convex set of matrices.

• MvM's guarantee and runtime. Theorem 7: regret at most O(U√(TK ln T)) with per-round runtime O(K²U + K²B).

• Partial structural knowledge extends cleanly. If the true (order, peaks) pair belongs to a polynomial-sized candidate set S, the algorithm picks the most optimistic matching across candidates, keeping Õ(U√(TK)) regret and runtime O(|S|·(K²U + K²B)).

• Approximate single-peakedness is defined and characterized. Definition 4 introduces δ-ASP: for i ≺ j ≺ l, P_{u,j} ≥ min{P_{u,i}, P_{u,l}} − δ. Proposition 8 proves a matrix is SP w.r.t. ≺ if and only if it is 0-ASP w.r.t. ≺. An estimate within δ in ℓ∞ of an SP matrix is 2δ-ASP, and Lemma 9 shows any δ-ASP matrix can be replaced by an SP matrix within δ in ℓ∞, constructible in O(UK) time.

• Extract-Order recovers an approximate order. Lemma 10: given an estimate within ε in ℓ∞ of an SP matrix, Extract-Order returns an order under which the estimate is (2Kε)-ASP. Its runtime is O(UK²), dominated by sorting (O(UK log K)) and up to K−1 contiguity constraints per user added to the PQ tree in O(K) each.

• EMC's operational flow. Explore for N rounds per arm, extract an order with ε = √(2 ln T / N), build an SP matrix with δ = 2K√(2 ln T / N), run SP-Matching, and play the resulting matching for the remaining T − NK rounds. Lines 3–5 cost only O(K²U + K²B).

• The EMC regret proof is truncated in the provided text. The content ends mid-sentence in Section 6.3 while starting the approximation-quality argument; the regret bound Õ(UKT^{2/3}) is stated in the abstract and introduction. Section 6.4, referenced as discussing the barrier to the optimistic approach with unknown order, is not included in the provided content.

Methodology in Plain English

The authors attack the NP-hardness of budgeted matching by changing the assumption, not the algorithm class. They assume preferences are unimodal along some common ordering of arms.

For the offline problem, they first prove that once you fix which arms are selected, the best thing to do is to send each user to the selected arm nearest to their peak. That observation converts the problem into a dynamic program over arms in sorted order, tracking budget. Sums of the form "for all users with peaks between i and k, take the better of arms i and k" are precomputed, giving quadratic runtime.

For the online problem with known structure, they build confidence intervals around observed rewards and construct the most optimistic matrix consistent with (a) the intervals and (b) the known single-peaked structure and peaks. Because this "maximal matrix" dominates every other matrix in the confidence set entry-by-entry, the optimistic matching decision reduces to one call of the offline solver. Standard UCB-style regret analysis then applies.

For the online problem with unknown structure, exact structure recovery is impossible due to noise. Instead, the authors define a relaxed notion of near-single-peakedness, and design a procedure that sorts each user's arms by empirical value and, whenever there is a large gap between consecutive values, imposes the constraint that the better group must appear contiguously in the true order. These contiguity constraints are accumulated in a PQ tree, a classic data structure for exactly this kind of "must be consecutive" ordering problem. If a consistent order exists, the tree returns it; the authors prove the resulting order makes the estimate approximately unimodal. They then snap the estimate onto an exactly unimodal matrix within a bounded distance and solve the offline problem once, committing to that matching for the rest of the horizon. Exploration is confined to a short initial phase, so the regret trades off estimation error against the length of the commitment phase.

Why This Matters

Impact on research. The paper adds to a known pattern in social choice theory — that single-peakedness turns intractable problems into tractable ones (the authors cite Black's median voter theorem and prior work on voting problems that become polynomial under single-peakedness) — but demonstrates the analogous phenomenon in a cardinal, budget-constrained online matching setting. It also contributes a new technique for extracting single-peaked orders from approximately single-peaked cardinal preferences, which the authors present as a contribution to the literature on order extraction (where exact recognition is efficient but finding orders minimizing distance from single-peakedness is NP-hard).

Real-world applications (as described in the paper):

• Content platforms that must decide which creators to commission daily under a budget, then match each user to content from one of those creators, since the same creator's content can serve multiple users without extra cost.
• Voters' preferences over political candidates positioned along an ideological spectrum.
• Consumers' preferences over products that vary along a single attribute.
• Recommendation based on genre similarity, where user preferences are unimodal over an ordered space of content styles.

Industry relevance. Recommendation and content-commissioning systems routinely face exactly this structure: a global budget or cardinality constraint on which items to offer, plus per-user assignment. The paper argues that traditional combinatorial bandit approaches settle for α-regret against the best efficiently computable solution, which is unsatisfying when decisions are high-stakes; the single-peaked assumption lets practitioners aim at the true optimum with provably sublinear regret and polynomial runtime.

Future Directions

• Closing the gap between EMC and the lower bound. The abstract's Õ(UKT^{2/3}) for unknown structure is looser than the Ω(U√(TK)) lower bound for unknown peaks; tightening this gap remains open.
• Weakening the structural assumptions. MvM requires the SP order and user peaks to be known (or to come from a polynomial-sized candidate set); extending efficient optimistic learning beyond these regimes is an open direction.
• Handling ties and degeneracies. The paper defers the treatment of ties in peak selection to Appendix G, and the provided content does not report the details — a natural place for further refinement.
• Beyond single-peakedness. Other unimodality or structural families from social choice theory could be tested for the same "hard statistically, easy computationally" behavior.

Target Audience

Researchers in machine learning theory, online learning, and combinatorial bandits, particularly those working on matching, resource-constrained recommendation, and regret analysis. Also relevant to algorithmic game theorists and computational social choice researchers interested in how preference structures (single-peakedness in particular) translate into computational tractability in learning settings. Practitioners designing budget-constrained recommendation or content-commissioning systems may benefit from the offline SP-Matching algorithm and the practical assumption of unimodal user preference orderings, though the paper's treatment is theoretical and the provided content reports no empirical experiments.

Authors’ abstract

We study an online stochastic matching problem in which an algorithm sequentially matches $U$ users to $K$ arms, aiming to maximize cumulative reward over $T$ rounds under budget constraints. Without structural assumptions, computing the optimal matching is NP-hard, making online learning computationally infeasible. To overcome this barrier, we focus on single-peaked preferences -- a well-established structure in social choice theory, where users' preferences are unimodal with respect to a common order over arms. We devise an efficient algorithm for the offline budgeted matching problem, and leverage it into an efficient online algorithm with a regret of $\tilde O(UKT^{2/3})$. Our approach relies on a novel PQ tree-based order approximation method. If the single-peaked structure is known, we develop an efficient UCB-like algorithm that achieves a regret bound of $\tilde O(U\sqrt{TK})$.