Bandits with Single-Peaked Preferences and Limited Resources
Authors: Omer Ben-Porat
Gur Keinan
Rotem Torkan
Venue: ICLR 2026 Poster (2026)
Keywords: social choice
single-peaked
preferences
bandits
matching
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: We study constrained bandit matching with single peaked preferences, and devise algorithms with sublinear regret

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})$.

Published as a conference paper at ICLR 2026
BANDITS WITH SINGLE-PEAKED PREFERENCES AND LIMITED RESOURCES
Omer Ben-Porat, Gur Keinan & Rotem Torkan
Technion- Institute of Technology Haifa, Israel
amerrb@ttechnion.ecc on..chhiioonn.....m..omm..e (gur.keinan, torkan. corkan..otee/eccampus ten ac
ABSTRACT
We study an online stochastic matching problem in which an algorithm sequen- tially 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 in- feasible. To overcome this barrier, we focus on single-peaked preferences well-established structure in social choice theory, where users' preferences are unimodal with respect to a common order over arms. We devise an efficient al- gorithm for the offline budgeted matching problem, and leverage it into an effi- cient online algorithm with regret of O(UKT2/3). Our approach relies novel PQ tree-based order approximation method. If the single-peaked structure is known, we develop efficient UCB-like algorithm that achieves regret bound of Ō(UTKK)
INTRODUCTION
Modern recommendation systems often face the challenge of personalization at scale scule-learning individual user preferences while simultaneously satisfying global resource allocation constraints. To illustrate, consider a content platform that must decide which content creators to commission daily, where each creator has a different cost and produces ephemeral content on specific topics. Each user has preferences over all creators' content styles and topics. After commissioning subset of creators that fit the platform's 's budget, it matches each user content from one of these creators, where the same creator's content can be recommended to multiple users. The challenge lies in learning individual user preferences for each creator's s content while selecting which creators to commission and how to assign their content to maximize user satisfaction.
This problem fits the combinatorial aunti-armed bandit framework, where the decision-maker must choose structured action (Chen al. 2013), such as assigning each user item. The goal to maximize cumulative reward, or equivalently, minimize regret by balancing exploration and exploitation. Unfortunately, combinatorial problems like the one the example above are NP- complete even for offline settings. Therefore, traditional approaches settle for weaker notions of a-regret (Chen al. 2013), competing against the best efficient computable solution rather than the optimal one. This compromise can be unsatisfying, especially when the solution space is highly structured the stakes of poor decisions are high.
In this paper, we circumvent this computational barrier by focusing on single-peaked (hereinafter SP) preferences- structure that has been extensively studied in social choice theory since the sem- inal work of Black (1948). Specifically, it implies that there is an order of the arms such that each user's utility is unimodal. SP preferences appear naturally in numerous domains: voters' prefer- ences over political candidates along ideological spectrum, consumers' preferences for products varying a single attribute, and users' preferences for content recommendations based on genre similarity. The single-peaked property has proven helpful in circumventing impossibility results in voting theory (Arrow 1950) and transforming NP-hard problems into polynomial solvable ones (Faliszewski et al.] 2009 Elkind & Lackner 2016).

---

Published as a conference paper at ICLR 2026
1.1 OUR CONTRIBUTIONS
We study a stochastic combinatorial bandit problem over T rounds with K arms and U users. Each arm k has a cost Ck2 and the learner may select any subset of arms within a budget B, then assign users to the selected arms. Each user derives a stochastic satisfaction from each arm, and the goal is to maximize total user satisfaction. As the general case is NP-complete, we focus on SP preferences (see Definition 2 which enable efficient solutions. Our main contributions are as follows.
SP instances are statistically challenging To demonstrate that SP preferences do not trivialize the learning problem, we show that the worst-case regret remains unchanged compared to general preferences. Specifically, we prove that even when the SP order is known, regret of QU (TKK, which matches the lower bound for general preferences, is unavoidable. Furthermore, even the user peaks are known as well, every algorithm incurs a regret of (UVna
Efficient offiine algorithm. We develop SP-MATCHING, an efficient algorithm that optimally solves the budget-constrained matching problem O K²U) time when preferences are SP.
Learning with known SP structure We consider the case of known SP order and user peaks (but the cardinal preferences). Such an assumption justified if, for example, preferences rely on a known ideological spectrum where user peaks correspond to stated or inferred inclinations. We design an efficient (CB-based algorithm, termed MvM, that achieves ÕUV regret. The key property used in our approach is the existence of a maximal preferences matrix the confidence set of all plausible SP matrices matric. nnmelyy matrix that element-wise dominates all others in the set. We use this maximal matrix as the basis for optimistic matching using our offline algorithm.
Learning with unknown SP structure We also consider the more challenging case, where the SP structure unknown. We introduce an explore-then-comiee an initial exploration phase to collecting reward estimates. Then, a novel PQ tree-based procedure (Booth Lueker 1976), which we refer to as EXTRACT-ORDER, recovers an approximate SP order from these estimates. Given this order, the reward estimates are projected onto nearby SP matrix, and the corresponding offline matching is solved using SP-MATCHING; the resulting matching is committed to for the remainder of the rounds. A careful approximation and concentration analysis yields regret bound of ÖU (UK3))) while all computational steps run in poly(U, K, B) time.
algorithm, named EMC, that devotes
Additionally, due to space constraints, we defer two extensions of our main results to Appendix A an extension of MvM for separated instances, and extension of EMC to non-SP instances.
1.2 RELATED WORK
Our research intersects the combinatorial and matching threads of the multi-armed bandits literature, as well single-peaked preferences from social choice theory.
Multi-armed bandits. The multi-armed bandit framework provides the foundation for sequential decision-making under uncertainty (Bubeck et al., 2012 Slivkins 2019 Lattimore & Szepesvári, 2020). This setting has been extended to the combinatorial domain, where actions are solutions of a combinatorial optimization problem (Combes et al. 2015 Kveton al.] 2015b). While ef- ficient learning algorithms exist for certain combinatorial structures (Neu & Bartók 2016), many practical instances involve computationally intractable optimization problems. To address this com- putational barrier, prior work introduced the notion of a-regret (Chen et al. 2013). which compares the learner's 's performance against the best efficiently computable solution rather than the true op- timum. This approach has led to the development of general frameworks for achieving a-regret guarantees in computationally hard settings (Rizk et al. 2022; Nie et al., 2023). Notably, the single- peaked structure we impose enables us to circumvent computational intractability entirely, allowing us to achieve standard regret bounds rather than settle for a-regret. Our setting further incorporates per-round budget constraints, which align with the cardinality and knapsack-type restrictions stud- ied in prior works (Nie et al. 2022 2023). A closely related line of work considers bandit learning for matching problems (Das & Kamenica 2005
Liu et al.) 2020 Kong et al. 2022 2024). Another
2

---

Published as a conference paper at ICLR 2026
perspective arises in content recommendation, which can be naturally viewed as matching prob- lem between users and creators. This has motivated a line of research on strategic content providers (Mladenov al.) 2020 Hron et al. 2023 Immorlica et al. 2024). Particularly, Ben-Porat & Torkan (023) study a variant where arms become unavailable if they are not selected sufficiently often, and their proposed algorithm has runtime exponential in K. In contrast, in our setting, arms remain continuously available (subject to budget constraints), and we devise efficient algorithms.
Single-peaked preferences. The study of single-peaked preferences dates back seminal work in social choice theory (Black) 1948; [Arow 1950). From a computational perspective, several problems have been investigated, including recognizing whether given preferences profile admits single-peaked order and constructing such order when it exists (Bartholdi III & Trick 1986] Escoffier et al., 2008). While recognition and construction of single-peaked orders can solved efficiently, the problem becomes computationally intractable when preferences are nearly but not perfectly single-peaked. Specifically, finding an order that minimizes various distance measures from single-peakenness has been shown to be NP-hard (Faliszewski et al. 2011 Ellind & Lackner 2014 Escoffier et al. (022). In Section 6 we contribute to this literature by developing a technique extract single-peaked orders from approximately kngle-peaked cardinal preferences.
The single-peaked assumption has profound implications across different domains. social choice theory, it circumvents classical impossibility results and enables positive outcomes that fail under general preferences. Most notably, Black's median voter theorem (Black) 1948) guarantees the existence of a Condoreet winner under single-peaked preferences, resolving a fundamental challenge in voting theory. From an algorithmic perspective, paglle-pakeedness has been shown to simplify computational challenges: numerous voting problems that are NP-hard under general preferences become polynomial-time solvable when restricted to 2009 Elkind & Lackner (016). Our work reveals a similar phenomenon in an entirely distinct setting. We demonstrate that in our cardinal matching model with budget constraints, the single- peaked structure enables efficient optimization for problems that are computationally intractable under general preferences.
structures (Faliszewski et al.)
2 PROBLEM DEFINITION
In this section, we formally introduce our model and notation (Section 2.1 address the case of general preferences (Section) 2.2 and focus on single-peaked preferences (Section 2.3
2.1 MODEL
We formalize the Constrained Bandit Recommendation problem (CBR for brevity) follows. An instance of CBR consists of the tuple (T, U, K, (u,,,) (c.)). B), whose components are de- scribed below. The problem involves U users indexed by [U] = {1, .l...., U} and K items (arms) indexed by [K] = {I....,K] K}. The satisfaction of each user u with an item & is stochastic and stationary over time, drawn from distribution Du,k supported on [0, 1] with expected value 0,,k- We denote the expected reward matrix O E [0, 1|U*K by setting its (u, k-)-th entry to O,, The distributions are assumed to be independent across users and arms.
The goal of the learner is recommend arms to users as maximize their overall satisfaction. Interaction proceeds over T rounds. In each round E [T]. the learner chooses a matching T, : [U] - [K] namely a function assigning each user a single item. The expected value of the matching is the total expected satisfaction of the users with their assigned arms, V(Te; θ) = Eneju (
However, not all matchings are feasible. The algorithm has a budget constraint on the selected arms: each selected arm (i.e., there is at least user such that n. (u) = k) has cost of Ck. and the total cost of the selected arms in every round should remain below known budget B E N. Formally, for a matching म. let Im(m)
{k E [K] Bu e [U] s.t. π (u) k}. Hence, matching is feasible only if E C& < B. We denote the set of all feasible matchings as 11. Without loss of generality, assume that C B for all k [K]. since otherwise such arms could never be selected. As in the motivating example of Section [ the platform pays the content creators (arms) per creation, so multiple users be matched the same arm without incurring additional cost.
3

---

Published as a conference paper at ICLR 2026
At the beginning of each round t, the learner has access to the history of past actions and observed rewards, denoted by H,. Upon selecting a matching H,, a random reward r' (u) Du, (v) is generated for each pair (u, (u)).. We assume semi-bandit feedback, meaning the learner observes r (u. for every matched pair (u, (u)). The performance of the learner A on a CBR instance is measured using the standard notion of regret,
T
(A,, = T max VTT; ) well
E
Σ
r
(u)
[=1 ME
where the expectation is over the algorithm's randomness and the realized rewards. As standard in bandit settings, assume T K, U. As a useful intermediate step, we also consider the offline version of the problem, where the algorithm is given the expected reward matrix & and must compute the optimal feasible matching, i.e., arg m ((T; +).
2.2 WARM UP: GENERAL PREFERENCES
Without structural assumptions on θ, achieving low regret with polynomial time algorithms is hope- less. In particular, we establish the following hardness result based a reduction from the maxi- mum coverage problem (Feige 1998):
Theorem 1.
is NP-hard to approximate arg max V(T; θ) within any factor better than (1 - 1/e).
mEll
Consequently, since an efficient online algorithm with sublinear regret would imply an efficient approximation algorithm for the offline problem, such online algorithm cannot exist. We defer the full analysis to Appendix B If we disregard computational constraints, optimal regret bounds can be attained by, e.g., applying the CUCB algorithm (Chen al. 2013). assuming access to an exact optimization oracle. Formally,
Corollary 2. There exists a UCB-based algorithm that achieves regret OUU VKT log T), which optimal up logarithmic factors.
While this algorithm is statistically optimal, it assumes optimization oracle that must solve an NP-hard problem at every time step, rendering it computationally impractical.
The literature typically addresses a-regret (Chen et al. 2013 Nie et al., 2022] 2023). This metric uses the best efficiently computable approximation as the baseline, rather than the true optimum. Although it is computationally feasible to achieve sublinear a-regret in our setting (e.g., with a = 0.5 using greedy oracle), this is weaker guarantee compared to the standard regret. This limitation motivates our assumption of structural properties for θ, which enables efficient optimization without sacrificing regret guarantees.
where the offline benchmark is intractable using the notion of
2.3 SINGLE-PEAKED PREFERENCES
Single-peaked preferences arise naturally in numerous applications and, as show, this structure enables polynomial citommil--imeeaee algorithms to achieve sublinear regret. We define it formally as follows.
Definition (PSP matrix). We say that a matrix θ is perfectly single-peaked (PSP for brevity) for every user [U]. there exists an index p(u: Q) E [K] such that
u
(u.p(me)) 2 Au.K.
In other words, the entries of every row are unimodal. The index p(u: Q) is called the peak of user simply p(u) when è is clear from context; if multiple indices attain the maximum, we fix an arbitrary choice More generally,
Definition 2 (SP matrix and SP order). We say that a matrix is single-peaked (or SP) if there exists (total) order - on the arms such that the matrix obtained by permuting the columns of θ according to x is PSP. In such a case, we say that x is an SP order of θ
See Appendix Gorrr discussion of how our algorithms and analyses handle such ties.
4

---

Published as a conference paper at ICLR 2026
reward
reward
02
03
01
3
4
5
arm
1
2
4
3
arm
(a) An SP instance
(b) A PSP instance
Figure 1: Illustration of PSP and SP instances. Each subfigure consists of curves representing the expected rewards of user-arm pairs. The instance in Figure ia is SP, since if we reorder the arms, we get the PSP instance in Figure lb.
Note that any PSP matrix is also SP, with the identity order serving as its SP order. In contexts where the relevant order matters, we shall write that θ is SP w.r.t. x. Furthermore, we say that CBR instance is (P)SP if its expected reward matrix @ is (P)SP. The SP order need not be unique; for example, the reverse order of any SP order is also an SP order.
To illustrate the PSP and SP properties, consider Figure The instance comprises three and five arms, and each subfigure illustrates the expected rewards for each user. The instance Figure Ta PSP, since there are "valleys" that contradict Inequality (1) If we reorder the arms according to the order - such that 1 < 2 < 5 - 4 < 3, we obtain Figure Ib Indeed, we observe unimodal preference shape for each user, indicating that the matrix is PSP. Thus, the instance in Figure la SP and < is its SP order.
3 STATISTICAL HARDNESS OF SINGLE-PEAKED INSTANCES
While SP instances highly structured, they remain statistically challenging learn. To demon- strate this, we establish regret lower bound for SP instances of (TK). which matches the guarantee of Corollary for general preferences. Moreover, we provide a comparable lower bound for more lenient case, where both the SP order and the users' peaks known the learner in advance. We do so by constructing families hard instances where the known structural properties fixed, and only the cardinal values differ. Since the structural information is identical across stances, the learner cannot leverage it to distinguish between them. We present these lower bounds in Theorem 3
Theorem 3. For any algorithm, the worst-case regret over SP instances is Q(UVTK) and (U VT, VTK)) when the SP order and user peaks are known.
Theorem 3 indicates that the SP assumption does not simplify the statistical aspect of the learning problem. However, as we demonstrate in the subsequent sections, does affect the computational aspect-it it enables efficient learning algorithms that achieve sublinear regret, standing in sharp con- trast to the intractability the general case discussed in Section 2.2
OFFLINE ALGORITHM FOR SP INSTANCES
In this section, we present an efficient and optimal algorithm for computing arg wag.ax,nn (i;; θ) for SP instances. W.L.og., shall assume that the SP order is the identity order, i.e., the instance is PSP. Indeed, an SP order can be extracted using our EXTRACT- OCT-RRRDRRRR algorithm (see Algorithm with 0 in (U K2) time, after which the columns be reordered accordingly.
5

---

Published as a conference paper at ICLR 2026
The main observation used by our algorithm relates to the optimal matching conditioned given subset of arms. Namely, we show that if the set of selected arms is S. the optimal matching assigns each user to the arm in S that is closest to their peak. We formalize this in Lemma
Lemma 4. Fix any PSP matrix θ with peaks p(-), and any arm subset S = {(k...... kmt S K
with hn <... < lim- Let n² E arg max n, Im(()]s ((;;)) 0). For any user u, if S p(u) S Kzt1 for some j with 1 S j < ro, then xt (u) [Kg ki+1}; otherwise, xt (u) E (K1, k.
Lemma 4 guides the design of dynamic programming-based approach for finding the optimal matching for a given PSP matrix P, costs c(-), and budget B. We call this algorithm SP-MATCHING and explain its essence here, deferring full details to Appendix D The algorithm maintains table F(k, b) representing the maximum achievable reward when arm k is the rightmost selected arm, the total budget is at most b, and we consider only users u such that p(u) I k. We add an auxiliary degenerate arm O such that co = 0 and Pa.o 0 for every user u, and initialize F(0, b) 0 for every b E [0] (B].
The recurrence relation for F(k: b) follows from Lemma When h is the arm with the highest index among the selected arms and the second highest, users with peaks before are unaffected by the inclusion of arm k, while those with peaks between and & are assigned to whichever of the two arms offers a higher reward. Consequently, F(k; b) is given by
F(i,b-ck) +
Σ SK
max Pu..: Pu,k
BOStCk 62
This maximum is always well-defined since arm 0 always satisfies its constraint. The optimal value is then V* = [ F(k: B) + +u Pa,k where users with peaks beyond all selected arms assigned the last selected arm k. To enable efficient computation, we precompute for all pairs (i, k) the sums Eus<p(u)ss max(Pu Pu, Pa,k] in O(K²U) time. This allows each entry in F to be filled in O(K) time, and since F has KB entries, the total runtime O(K" + K²B).
Theorem 5. For any PSP matrix, SP-MATCHING finds an optimal matching in time (UK(()+
5 ONLINE ALGORITHM FOR THE KNOWN SP STRUCTURE REGIME
We now turn to the more challenging online setup. Although the underlying expected reward matrix SP, our reward estimates are generally not guaranteed preserve this structure. For motivation, suppose the true reward matrix is O, but we only have access to noisy estimate O If θ is itself SP. we could apply known methods to extract its SP order (Bartholdi III & Trick 1986, Escoffier al.) 2008) and use the SP-MATCHING algorithm to obtain approximately optimal matching w.r.t. O. However, since only approximates θ, θ may not be SP. Moreover, the SP order of e, which is crucial for offline algorithm, remains unknown and may not be recoverable directly from é. Therefore, leveraging the fact that the instance is SP non-trivial.
In this section, take first step towards resolving this challenge by leveraging additional struc- tural information of the problem. Specifically, we assume that both the SP order and user peaks are known in advance the learner. Recall from Section 3 that despite this knowledge, the learning problem remains statistically non-trivial. These structural assumptions, however, enable an effi- cient, optimistic UCB-style algorithm that achieves ŌUU regret. Our approach involves the construction of optimistic reward estimates using confidence sety (Slivkins) 2019, Chapter 8.4), as detailed in Section 5.1 while preserving the single-peaked structure. Then, we use those estimates design the algorithm described in Section
5.2 5.2
5.1 CONFIDENCE SETS AND MAXIMAL MATRIX
Given the known SP order < and user peaks p(-), we construct confidence sets for the expected reward matrix that contain the true parameters with high probability. Intuitively, these sets capture all matrices that statistically plausible given the data observed far, and naturally shrink as more data is collected. We begin by establishing notation for standard confidence bounds. Given a history H, round we denote by 0,, (L) and &e (1) the empirical mean reward and the number of

---

Published as a conference paper at ICLR 2026
Algorithm 1 Match-via-Maximal (MvM)
Require: Order <, peaks p" (-)
1: for = 1 to T do
2: Construct the maximal matrix pa
3: Select गH SP-MATCHING((P)
4: Observe rewards and update history H;
pulls of the pair (u, k) observed up to round t, respectively. The upper confidence bound is defined as UCB,,, (t) 0., (t) + /2inT//n., with the lower confidence bound LCB,,,((t) defined analogously using subtraction. We formally define the confidence set as follows.
Definition 3 (Confidence set). The confidence set Cº =c'(< p, H₂) contains matrix P and only if it is consistent with X and p(.), and for any u, k it holds that LCB.,,(l) v Pa,k S (C)...(t).
The standard UCB approach requires picking the optimistic matching at every time t, namely
Te E arg max max V(T; P).
(2)
TEll PEC
This discrete optimization problem over a convex set may be tricky, as different matrices yield dif- ferent optimal matchings. However, a structural property of C' simplifies this optimization problem. As we demonstrate shortly in Lemma 6 Ct includes a unique maximal matrix P an element- wise sense; thus, to find the solution of Equation ② we should only find the optimal matching w.r.t. Pt.
Lemma 6. For any non non-empty confidence set C* p. H1), there exists unique srement-wise max- imal matrix pt E C³ such that P 2 Pu,k for all P E C and all u E [U], k [K]. Furthermore,
m (C),,;()), k 3 p(u) mine (C),,
this matrix is given by P.,k
p(u) k
We refer to the above matrix as the maximal matrix Ct, and note that its structure relies on knowledge of both the order x and the peaks p(-).
5.2 THE MATCH- -AXIMAL ALGORITHM
Next, we present a combinatorial UCB-based algorithm, which we refer to as MvM (Algorithm MvM acts optimistically-in each round, it selects the optimal matching w.r.t. the corresponding maximal matrix. The regret analysis of MvM involves standard UCB-like arguments. By the con- struction of the confidence sets and applying Hoeffding's 's inequality with a union bound over all (u, k) pairs and time steps, the actual expected reward matrix θ is in Ct for all f E [T'] with proba- bility at least 1 2KU Th. Employing the clean event technique, we ignore the complementary (bad) event, which occurs with low probability. In every round t, we have
max V(T; 0) (mT +) S Vmme; P*) ((T θ) S Σ 2/ 2 T/ /u TENT
Summing Inequality 33 over all rounds, we obtain the following theorem: Theorem 7. For any SP instance with known SP order - and peaks p(-), MvM achieves regret of at most QU (UUTKITT) with per-round runtime of OKKS + B).
Extension to partial structural knowledge The MvM algorithm naturally extends to settings where the SP order and user peaks are not known exactly, but are known to belong to a polynomial- sized set S of candidate structures. For each candidate (2,p) S, one can construct the cor- responding maximal matrix P(x,p) via Lemma 6 and compute its optimal matching T(=.p) using SP-MATCHING. The algorithm then selects the matching achieving the highest optimistic value: Te E arg p) (=) P(<xp)) Since the true structure belongs to S, the selected match- ing is at least as optimistic as the one corresponding to the true parameters, and the same regret analysis yields ÖUUTTK regret. The per-round runtime becomes O([S)- -KKU + K2B),, which remains polynomial when [S] = pOly(U, K, B).
7

---

Published as a conference paper at ICLR 2026
Algorithm 2 Extract-Order
Algorithm 3 EMC
Require: E RUXK .=>
Require: Exploration rounds N
Ensure: An order s.t. P is 2KE-ASP, such exists.
Ensure: A sequence of feasible matchings
(Tt (Ti)E=
1: Initialize PQ tree T on [K]
2: for u [U] do
1: Define EN 2n
3: Let ,....,,, . be s.t Pu,Nę 2. ... Pu.u
2: Pull each arm E [K] for rounds,
let θ be the empirical mean matrix
4: for [K - s.t. Pu,A. Pu.ky 28 do
3: <t- EXTRACT- ORRRRCCC-ORDE((O... EN)
5: Add the constraint (eff........ k.j
4: Construct an SP matrix from (0,-) via Lemma with 8 2K
6: if' There exists some feasible order in I" then
7: return some feasible order-
5: क + SP-MATCHING(())
8: else, return fail
6: Play f for the remaining rounds
6 ONLINE ALGORITHM FOR THE UNKNOWN SP STRUCTURE REGIME
We now turn to the more general setting, where the learner knows only that O is SP, but lacks knowledge of the specific underlying order or user peaks. When the order is unknown, the confi- dence set must include all matrices consistent with any valid SP order, and the optimistic approach from Section can no longer be applied efficiently; we discuss this barrier formally in Section 66.4
To tackle this challenge, we take a three-step approach. First, we define the concept of approximate single-peaked matrices that relaxes the strict SP condition while remaining amenable to analysis. Second, we present an efficient procedure to extract a plausible SP order from empirical data. Fi- nally, we combine these tools in an explore-then-commee key insight underlying our approach is that due to estimation noise, we cannot hope to recover the exact SP order of the true matrix O; instead, we aim to find some order under which the empirical estimates are approximately single-peaked, which suffices for near-optimal matching.
algorithm that achieves sublinear regret. A
6.1 APPROXIMATE SINGLE-PEAKER MATRICES
We begin our analysis by defining the concept of approximately dingle-peaked (ASP) matrices.
Definition 4. We say matrix P is d-approximately single-peaked (or 6-ASP) w.r.f. order if for every i.3.1 E [K] such that =j j < and user u E U. holds that Pu.j 2 min Pa, ] 6.
If P is 8-ASP w.r.t. 2, say < is its 8-ASP order, analogously to SP order. The parameter quantifies the tolerable violation of the single-peaked property. When = 0, this condition is equivalent to the matrix being SP w.r.. x, we prove in the following proposition.
Proposition 8. A matrix is SP w.r.t an order - if and only if it O-ASP w.r.t. x.
The 6-ASP condition proves useful beyond the strict 8 0 case. In fact, it follows directly from Definition that if P is SP w.r.t X and P satisfies ||P Pl < 8, then P is 28-ASP w.r.t. <. This implies that a noisy estimate of an SP matrix remains ASP. Conversely, given any 6-ASP matrix and its ASP order, can construct matrix that is (exact) SP with respect the same order, with each entry differing from the original by at most ö.
Lemma 9. Let P be a 8-ASP matrix w.rlt X. There exists a matrix P which is SP w.E.. 2, and satisfies ||P -- Ploc < 8.
We prove Lemma 9 by construction, which can implemented in OUUK) time. Lemma enables us to work with SP matrices even when the estimate matrix is not SP, while not sacriticing the approximation quality. However,
the ASP order <, which we do not have.
6.2 EXTRACT-ORDER PROCEDURE
Relating to the previous subsection, even if we know that the estimate matrix θ is ASP w.r.t. the SP order e, this order still unknown. In what follows, we develop the OXTRACT-ORDER algorithm, which extracts ASP order from θ (not necessarily the SP order of θ).
8

---

Published as a conference paper at ICLR 2026
We start with some intuition. Finding order boils down to solving set of contiguity constraints subsets of arms that must be contiguous in any valid order. To illustrate, fix an SP matrix and suppose there exists user u and a partition of [K] into two sets A and Ag. Let 3 minke A, Pa, and y = ma Pu.k- If [ 7 > 0, then every arm in A₁ is preferred by user u over every arm in A2. In this case, any order that places arm j E A2 between two arms i, E A violates the O-ASP condition (Definition 4 Hence, according to Proposition 8 < cannot be an SP order of P. Thus, any SP order of P places the arms in A₁ in a contiguous block. As result, any order that satisfies all such contiguity constraints is an SP order of P.
Next, assume we have a matrix P such that || Pllco S for the SP matrix P. Since every entry in P only approximates P. we cannot hope to discover all the contiguity constraints of P. For instance, if minseA, Pu,k = 3 - E and ma Pa,* = 7 + for the user u and partition A1, A2, then minkEA; Pu,& ma Pu,k 3 - - is negative, we would not discover the contiguity constraint of A1. Similarly, we might enforce incorrect constraints. Thus, should aim to discover many contiguity constraints possible from P. while remaining consistent with the contiguity constraints of P. To that end, if triplet u, A and A2 satisfies
In the case that this expression
min Pu, max PU, 23, REA1
(4)
READ
we can safely add contiguity constraint on A1 since the proximity between P and P guarantees minkeA, Pu,s - m, Pu,, > 0; hence, this constraint also applies to the matrix P.
formalizes this approach using PQ tree (Booth Lueker 1976), an efficient data structure that specializes in encoding and resolving contiguity constraints. PQ trees maintain sets of items that must appear consecutively in any valid order, and can be used both to determine whether a consistent order exists and to efficiently construct such an order. EXTRACT-ORDER initializes PQ tree (Line DT. and for each user u, it sorts the arms by preference values (Lines 3 Whenever there is a significant gap (exceeding 2e) between consecutive preference values, which exactly corresponds to the case described in Inequality (4) it adds a contiguity constraint requiring all higher-valued arms to appear consecutively (Line Finally, the algorithm returns an order on the columns of P that satisfies all the imposed contiguity constraints, if such an order exists (Line 7 Otherwise, it fails and returns nothing (Line g
The EXTRACT-ORDER algorithm, described in Algorithm 2
Notably, the constraints enforced by this procedure are not only consistent with the SP order of P, but also ensure bounded valley depth (in the sense of Definition 4.. Formally,
Lemma 10. Let P be matrix such that |P- Plloo S for some SP matrix P. EXTRACT- ORDER(P, e) returns order x such that P (2KE)-ASP w.E.t.
The runtime complexity of EXTRACT-ORDEE operations. Sorting preferences for all users requires OU K log K)) time. Subsequently, for each user, we may add up K contiguity constraints to the PQ tree, where each addition takes O (K) time, yielding ( time for all constraints. The final feasibility check and order extraction from the PQ tree requires OKK time. Thus, the overall runtime OUK?).
dominated by sorting user preferences and PQ tree
6.3 EXPL.ORE-
ALGORITHM
We now present the Explore-then Mawaaaaadd-Comaaaeea algorithm (EMC), described in Algorithm 3 which combines the tools developed in the previous subsections to achieve sublinear regret. It op- erates in five phases. First, given an input parameter N, the algorithm explores by pulling each arm k [K] for N rounds and collects empirical means Ô. Second, it applies EXTRACT-ORDSS
and extracts an order < from O The parameter s is chosen so that ||0 O| < & holds with high probability. In the third phase, it uses θ and the order < construct the matrix Ô, which is SP w.r.t. < and is element-wise close to O. Fourth, it executes STCMINGIING on Ô to find an optimal matching स. And in the fifth and last phase, exploits-it plays के for the remaining T-NK rounds. Importantly, the computational effort in Lines 3 5 is only P
U + K2 B), ensuring that the algo- rithm is computationally efficient. This is in sharp contrast to the exponential runtime we obtain for general instances in Section 2.2

---

Published as a conference paper at ICLR 2026
The regret analysis for the commitment phase hinges the approximation quality between the matrix θ used for the matching and the true expected reward matrix e. Since θ is constructed to be close to the empirical estimates θ and é concentrates around θ with sufficient exploration, the value gap V (T; 6) - ( θ) is bounded by the estimation errors and the approximation errors from Lemma 2 and EXTRACT- ORDER. By optimizing the choice of exploration rounds N, we balance the exploration cost against the quality of the resulting approximation.
Theorem 11. EMC(N- = [T2/// TT3/s) yields an expected regret of at most ŌUUKT)/))
6.4 HARDNESS OF OPTIMISTIC MATCHING WITH UNKNOWN ORDER
In the known SP structure regime (Section 5). the MvM algorithm achieves Ō(UVTK) regret by solving the optimistic matching problem in each round. A natural question is whether a similar approach yield improved regret guarantees when the SP structure is unknown. Recall that the optimistic approach requires solving Equation (2). where C' is now the confidence set of statistically plausible SP matrices. When the order and peaks are known, Lemma 6 shows that C admits unique element-wise maximal matrix, reducing the optimization to a single call to SP-MATCHING, However, when the order is unknown, C must include all SP matrices consistent with any valid order, and no such maximal element exists in general.
We note that if the optimistic matching could be solved efficiently in this regime, the same analysis in Theorem 7 would yield the same ÓU /TK) regret guarantee. One might hope that more sophisticated algorithm could achieve this. We show that this is unlikely by proving that even simpler peprroblem-finddigg the best matrix in C' for a fixed matching-is NP-hard to approximate.
Theorem 12. Consider the following optimization problem, termed MAX-SP-WCS. given sets of users U and arms K, matching π U - K, and confidence intervals [LCBu.,k UCBu,k) for each (u, k) E U x K, find pax V(T: P). where C contains all SP matrices respecting the confidence intervals. Then, approximating MAX-SP-WCS within a factor of 3
4 + +8 is NP-hard for any ö > 0.
7 DISCUSSION
We studied a budgeted matching problem under single-peaked preferences. While the general of- fline problem NP-hard to approximate within a constant factor, imposing a single-peaked structure enables polynomial-time optimization. Nevertheless, trivialize the statistical aspect of the learning problem, which remains as challenging as the gen- eral preferences case. When the SP structure is unknown, we introduce explore-then-commi approach that first extracts an approximate order, then commits to a near-optimal policy, yielding (UK3)/3) regret. For the more lenient case of known SP order and user peaks, we developed an optimistic algorithm based on maximal matrices that achieves (UV regret. We also con- ducted an experimental validation, which is deferred to Appendix H due space constraints.
demonstrated that this structure does not
We identify several interesting directions for future work. First, comparing our algorithmic results with the lower bounds, we observe room for improvement. For the unknown SP structure regime, EMC achieves OUKK2) regret, while the OU /TK) lower bound is statistically tight (achiev- able by inefficient algorithms). It remains open whether the VT rate can be achieved efficiently, or if our T2/3 rate is tight for polynomial-time algorithms. Theorem 12 provides evidence toward the latter: exponentially many SP structures may remain consistent with observations, and we show that even evaluating the optimistic value for fixed matching is NP-hard to approximate. For known order and peaks, MvM achieves Ō (UU) regret (Theorem 7). exceeding the lower bound by VIn 7 max VK,U), Future work could resolve this gap.
Second, our results suggest that single-peaked preferences could potentially simplify other computa- tionally challenging problems in online learning, suggesting an alternative route to a solution rather than o-regret. Finally, extending our results to more complex preference structures (Sliwinski &
Elkind 2019: Peters & Lackner 2020) presents an intriguing challenge.
ACKNOWLEDGMENTS
This research was supported by the Israel Science Foundation (ISF; Grant No. 3079/24).
10

---

Published as a conference paper at ICLR 2026
REPRODUCIBILITY STATEMENT
All theoretical results are supported by complete proofs provided in the appendices. Algorithms fully specified in the main text and appendices, including pseudocode and complexity analyses. The assumptions required for our results are explicitly stated and discussed in the problem defi- nition and algorithmic sections. Our experimental evaluation is based synthetic single-peaked preference matrices generated according to a well-defined random procedure, with details given in The source code implementing all algorithms and experiments, along with instructions for reproducing the figures, is attached to the submission and will be released upon publication. The experiments rely only on standard Python libraries and require modest computational resources (a single CPU).
Appendix H
ETHICS STATEMENT
Our work is theoretical, and the experimental evaluation relies only on synthetic data, involving no human subjects or sensitive information. The results may inform the design of recommendation and matching systems under budget constraints. Applying such methods in sensitive domains (e.g., political content hiring) requires careful consideration of fairness and user autonomy.
REFERENCES
Kenneth Arrow. A difficulty in the concept of social welfare. Journal of political economy, 58(4): 328-346, 1950.
Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic mul- tiarmed bandit problem. SIAM Journal on Computing. 32(1):48 77, 2002. doi: 10.1137/ 00097539701998777
httltttps://do.osse
Per Austrin, Rajsekar Manokaran, and Cenny Wenner. On the np-hardness of approximating ordering--oossrrait satisfaction problems. Theory of Computing, 11(1):257-283, 2015.
John Bartholdi III and Michael A Trick. Stable matching with preferences derived from psycho- logical model. Operations Research Letters, 5(4):165-169) 1986.
Omer Ben-Porat and Rotem Torkan. Learning with exposure constraints in recommendation sys- tems. In Proceedings of the ACM Web Conference 2023, WWW '23, pp. 1456-3466 New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9781450394161. doi:
10.1145//5435073388333 URL hRRL::ts:: /tt.pp://do.... org/10. 1145/ 3583320
Duncan Black. On the rationale of group decision-making. Journal of political economy, 56(1): 23-34, 1948.
Kellogg S. Booth and George S. Lueker. Testing for the consecutive ones property, in- terval graphs, and graph planarity using pq-tree algorithms. Journal of Computer and System Sciences, 13(3):335-377 1976. ISSN 0022-0000. doi: https://oii.rg///
1016/950222-000076)88445551 URL battps://wwy http://wwwciicniiieeeee.e. www. www.scienceee.eeeeeeccocmcc brricle//s1/50220007660000
Sébastien Bubeck, Nicolo Cesa- et al. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):11122, 2012.
Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General frame- work and applications. In Sanjoy Dasgupta and David McAllester (eds.), Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pp. 151-159, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR. URL ml https::/proceediin http:essww..p...e.eeeemmmmmmmeee wptpss///2//chenaa.a...
Richard Combes, Mohammad Sadegh Talebi Mazraeh Shahi, Alexandre Proutiere, and mare lelarge. Combinatorial bandits revisited. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett (eds.). Advances in Neural Information Processing Systems, volume 28. Cur- files/
ran Associates, Inc., 2015. htt.://cc..i..ioo.aaa.ooo.oaaaar

---

Published as a conference paper at ICLR 2026
Sanmay Das and Emir Kamenica. Two-sided bandits and the dating market. In IJCAI, volume 5, PP. 19, 2005.
Edith Elkind and Martin Lackner. On detecting nearly structured preference profiles. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014.
Edith Elkind and Martin Lackner. Structure in dichotomous preferences, 2016. URL https:
7/ /arrxiv.com wwwp.ii.rrg/bb///55000
Bruno Escoffier, Jérôme Lang, and Meltem Özüürk. Single-peaked consistency and its complexity. In ECAI, volume pp. 366-370, 2008.
Bruno Escoffier. Olivier Spanjaard. and Magdaléna Tydrichová. Mcasuring nearly single- peakedness of an electorate: Some new insights. In International Conference on Algorithmic Decision Theory, pp. 19-34. Springer, 2021.
Piotr Faliszewski, Edith Hemaspaandra, Lane Hemaspaandra, and Jörg Rothe. The shield that never was: Societies with kingl-peaked preferences are more open to manipulation and control. In Proceedings of the 12th Conference on Theoretical Aspects of Rationality and Knowledge, pp- 118-127, 2009.
Piotr Faliszewski, Edith Hemaspaandra, and Lane A Hemaspaandra. The complexity of manip- ulative attacks in nearly single-peaked electorates. Proceedings of the 13th conference on theoretical aspects of rulionality and knowledge, pp. 228-237 2011.
Uriel Feige. A threshold of In n for approximating set cover. J. ACM, 45(4):634 July 1998. ISSN 0004-5411. doi: 10. 03552/28555..885055 URL https:://cc..rg///// /ttp:/000....0110.1141111/ 2B5055 285059
Jiri Hron, Karl Krauth, Michael Jordan, Niki Kilbertus, and Sarah Dean. Modeling content creator incentives on algorithm-curated platforms. In The Eleventh International Conference on Learning Representations, 2023.
Nicole Immorlica, Meena Jagadeesan, and Brendan Lucier. Clickbait quality: How engagement- based optimization shapes the content landscape in online platforms. In Proceedings of the
ACM Web Conference 2024, wWW '24, pp. 36-45, New York, NY. USA, 2024, Association for Computing Machinery. ISBN 9798400701719. doi: 10. 10.1455758933446655553 URL
https:///oi..oo htt.//o..orgg/// /111111155333.36666
Fang Kong, Junming Yin, and Shuai Li. Thompson sampling for bandit learning in matching mar- 12048
kets, 2022. URL httpp:://aaxii..rrgg//////
Fang Kong, Zilong Wang, and Shuai Li. Improved analysis for bandit learning in matching markets. In The eiihth- Annual Conference on Neural Information Processing Systems, 2024. URL
https: hatp:://operreviee. net Forum?ion ii=00 0=77700077277
Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Tight regret bounds for stochas- tic combinatorial semi-bandits. Artificial Intelligence and Statistics, pp. 535-543, PMLR, 2015a.
Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Tight Regret Bounds for In Guy Lebanon and S. V. N. Vishwanathan (eds.), Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, volume 38 of Proceedings of Machine Learning Research, pp. 535-543, San Diego, Califor- nia, USA, 09-12 May 2015b. PMLR. URL httthhtp:://// http://prroeeeen............ /
Stochastic Combinatorial
kvetoni5. html
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Lydia Liu, Horia Mania, and Michael Jordan. Competing bandits in matching markets. In Inter- national Conference Artificial Intelligence and Statistics, pp. 1618-1628. PMLR, 2020.
12

---

Published as a conference paper at ICLR 2026
Martin Mladenov, Elliot Creager, Omer Ben-Porat, Kevin Swersky, Richard Zemel, and Craig Boutilier. Optimizing long-term social welfare in recommender systems: A constrained matching approach. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Con- ference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp- 6987-6998. PMLR, 13-18 Jul 2020. URL httph::t////..........tt htttps://proceent ngs. mm..mmlr.. mladenov20a.html
Gergely Neu and Gábor Bartók. Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits. Journal of Machine Learning Research, 17(154):1-21, 2016.
Guanyu Nie, Mridul Agarwal, Abhishek Kumar Umrawal, Vaneet Aggarwal, and Christopher John Quinn. An explorethhen-commii commit algorithm for submodular maximization under full-bandit feed- back. In Uncertainty in Artificial Intelligence, pp. 1541-1551. PMLR, 2022.
Guanyu Nie, Yididiya Nadew, Yanhui Zhu, Vaneet Aggarwal, and Christopher John Quinn. A framework for adapting offline algorithms to solve combinatorial multi-armed bandit problems with bandit feedback. In International Conference on Machine Learning, pp. 26166-26198. PMLR, 2023.
J. Opatrny. Total ordering problem. SIAM Journal Computing, 80)::11-114, 1979, doi: 10. 1137/0208008. URL http:::::: wttp:/..../..11111/222111.0
Dominik Peters and Martin Lackner. Preferences single-peaked on a circle. Journal of Artificial Intelligence Research, 68:463-502, 2020.
Geovani Rizk, Igor Colin, Albert Thomas, Rida Laraki, and Yann Chevaleyre. An S SlpphaSS-no- regret algorithm for graphical bilinear bandits. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https: http::s///ppeeeeieeee net wwt.:/rreeteeetee////// forum? 2=tpiiddddxxxxxxxx=xx
Aleksandrs Slivkins. Introduction to multi-armed bandits. Foundations and Trends@ in Machine Learning, 12(1-2):1-286, 2019.
Jakub Sliwinski and Edith Elkind. Preferences single-peaked on a tree: Sampling and tree recog- nition. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelli- gence. Association for the Advancement of Artificial Intelligence, 2019.
The Sage Developers. SageMath, the Sage Mathematics Software System (Version 10.6.0), 2025. https: http://wwwww.....ttttt/tttttttat org.
Grigory Yaroslavtsev, Samson Zhou, and Dmitrii Avdiukhin. "bring your own greedy"+ max: near- optimal 1/2 approxxximass for submodular knapsack. In International Conference Artificial Intelligence and Statistics, pp. 3263-3274. PMLR, 2020.
13

---

Published as a conference paper at ICLR 2026
Algorithm 4 Sep-MvM
Initialize nk O, 6v.k & for all u.
2: // Phase 1: Exploration with Monitoring
3: for 1.1,..,,,, KT2/3 do
4: Select arm K (t (mod K)) + 1 for all users (Round-Robsl Robin).
5: Observe rewards, update empirical means 0u and counts Tuu
6: Update Confidence Intervals: Iu,x(t) = 10n.
21n
Da,k +
nu,
nl.kk
7: SEP <- Vu, Vi J. (t) n Iu. (t)
8: if SEP is True then Break Phase I., proceed to Phase 2.
9:
10: // Phase 2:
Structure Exploitation if SEP is True (Structure Recovered) then Recover SP Order < using EXTRACT-ORD (RRARCT, 0) and the peaks. Run MVM using recovered order and inferred peaks.
12:
14:
else
15:
Timeout Reached fallback to EMC Strategy
16:
Solve से + SP-MATCHING(()) (using the commitment phase of EMC).
17:
Commit to for rounds t..
A EXTENSIONS
In this appendix, we present two extensions of our main results. First, we extend the MvM algo- rithm to handle instances with unknown structure statistically simpler learning due to distinct preference values (Section A.1. Second, we generalize the EMC algorithm accommodate non- single-peaken instances (Section
A.1 SEPARATED INSTANCES
We improve guarantees for instances that statistically simpler to learn due distinct pref- erence values. Specifically, we consider separated instances, where we quantify separation by Aglohal min, mineyy]0u., On.jl-
Algorithm overview. The SEP-MvM algorithm, presented in Algorithm follows a hybrid exploration-exploitaiion strategy. It begins by exploring all arms in round-robin manner, maintain- ing confidence intervals (t) = [LCB,,, (t), UCB seeks a separation event before a timeout v KTT2/3, Separation occurs when, for each user, the confidence intervals of all arms are pairwise disjoint. A direct concentration analysis reveals that such separation must occur after at most O K 7/A) rounds. After separation, the algorithm constructs the SP order using EXTRACT-ORDER and switches to MvM with the estimated order and peaks. If separation is not achieved by т, the algorithm infers that the instance is not well-separated and reverts to EMC.
for each user-arm pair. The algorithm
Aglobal = min, mingzy [ G. with per-step computational complexity of OKK3U + K2B). mmmin Proposition 13. SEP-MvM yields regret of at most Ô (U min KT2/3 VTK + k/D for }),
)
Proof. We analyze the regret conditioned on the standard clean event & = (Vu, k, (0,,((1)
8u,k 2lnT (t) which holds with probability at least 1 2UK/13. Under E, the true mean is
always contained within the confidence intervals I,, (t).
We consider two cases based on the magnitude of the instance gap Aglobal-
First, notice that if separation does occur before the timeout KT2/3, then the regret will be at most (TK/33) it comprises of the exploration gret (which will be less that 2/3 rounds) and the regret of the MvM algorithm, which is
Case 1: A Aglobal
32 In
14

---

Published as a conference paper at ICLR 2026
most OU (TK) when run with the correct parameters. Next, suppose the separation condition not met by the timeout. The algorithm switches to the EMC commitment strategy, after per- forming its exact exploration phase with the same exploration parameter in Theorem [T] Thus, the same regret bound applies, and get R(T) Ō(UKT2/3). And indeed, when the condi- 32 holds, this is the smallest of the two expressions in the minimum (up to T2/3
tion A global
poly-logarithmic factors).
Case 2: Aglobul
In this case, separation occurs before the timeout. To see this, notice that under the clean event, separation must occur if round-robin, (t, xe K. The condition requires:
32
T2/3
2ln
I A glohaal / /4. Since samples are collected
2K In
A Aglobal
32K In T
4
A global
Thus, the separation event occurs lsep
O
KIn
<T
Bitel
After the separation, the structure can be recovered perfectly (again, conditioning the clean event)-pairwise disjointness implies the sorted order of empirical means is identical the sorted order of true means. Thus, EXTRACT-ORDER will recover true SP order and peaks.
After tep, we switch to MVM. The total regret the sum the exploration regret (up to tecp) and the MVM regret (from seep to T):
R(T) S U tsep
RMVM (T tsepp)
Exploration
MVM Regret
Substituting tsep = ((K/() global) and the MVM bound Ō(UVTK):
UK +UVTK A global
R(T) 5
Conclusion. Taking the minimum of the two cases (since the algorithm automatically executes the better strategy via the timeout mechanism), we obtain the bound:
ò ò ((r
(Uminn/ min KT VTK
K
A
global
A.2 BEYOND SINGLE-PEAKER INSTANCES
We extend EMC work on siigln--naaeee instances. The key idea is that even when the true preference matrix θ is not SP, we can still apply our algorithmic framework and obtain meaningful guarantees that degrade gracefully with the distance from the nearest instance.
Algorithm overview. The NSP-EMC algorithm, presented in Algorithm maintains the same explore-then-commit structure as EMC but adds binary search procedure find minimal tolerance parameter for which EXTRACT-ORDE succeeds. This adaptive approach allows the al- gorithm to handle instances that are approximately single-peaked without requiring prior knowledge of the approximation quality.
Proposition 14. Fix an instance (possibly not SP), and let be its expectation matrix. Then, NSP-EMC achieves regret of most O (TK333m T) -UKTT KT), where inf iissrl Pllso, with a computational complexity of OUU K2 log(T') K2B).
Proof. Let p E S an SP matrix such that ||@ P* = 7. and let Aest
T/N.
We condition on the clean event & { - 01 < A which holds with probability at least 1 20 K K/T* by Hoeffding's inequality and union bound.
15

---

Published as a conference paper at ICLR 2026
Algorithm 5 NSP-EMC
Require: Exploration rounds N
1: Match each user a to each arm E [K] for rounds; let be empirical mean matrix.
2: Binary Search for
3: Set Slow <- 0, Ehigh f- 1,6 4- 1, - Identity
4: while Shigh - ELow > 7 do
5: Emid (Elow + Ehigh)
6: Stempt
CRRRACCT-ORDERRAAA
7:
if Stempp fail then
8:
Emid
9:
+t Stemp
Ehigh t Emid
11: else
Elow f- Emid
Construct SP matrix Ô from (G.x) via Lemma with d 2K Ehigh-
14: ग + SSP-MATCINN((E)
15: Play म for the remaining T NK rounds.
Step 1: Feasibility of the Binary Search.
By the triangle inequality and the definition of
1 - lo S + Oll + ||0 1' S Dest +
Let 5*
Since P is an SP matrix (and thus valid with respect to some SP order <pp=) ) Lemma 10 guarantees that EXTRACT-ORDER (OODER((,e")) (0,**) will succeed and return valid order. Because the binary search finds the minimal feasible (up to precision 1/T) for which EXTRACT-ON EXTRACC-ORDER returns a valid order (note that this condition monotone E), the found parameter é satisfies:
Ehigh I E" + T
= Dest + 1 T
We omit the & term in the remainder of the analysis, as negligible in the final bound.
Step 2: Bounding the Approximation Error. The algorithm produces order using Ehigh- According to Lemma 10 the empirical matrix is the algorithm constructs ê using Lemma with 5 Khiggh Lemma guarantees that Ô is SP with respect to < and satisfies:
-AAPP with respect <. Subsequently,
| 01 2Kgnihh
Substituting the bound for Ehigh from Step 1:
| - Ø1 S 2K (Aestt + +)).
Step Total Value Gap and Regret. We bound the difference between the true optimal matching .t and our committed matching स. Since is optimal for θ:
V(=*; ( θ) = v - V( θ) + ((=*; - V θ)
< V(<': 9) - V(r";0) V(;; - V(#; θ) (optimality of a on i)
2 @1
Using the triangle inequality:
||0 - 01. 0x 5 ||0 O1100 + +1 1lo
- Aest + 2K(A + 7)
= =2K + 1) + 2K7
Thus, the per-round regret during the commitment phase is bounded by:
V(=);0) V +) < 2U( 1)Aest 4U Kg.
16

---

Published as a conference paper at ICLR 2026
Step 4: Total Regret.
Substituting N [ (In 1/3 and Dest V2nT/NN:
2 I R S NKU +T 2U( + 11
+ AUKK)
O(UKTT/((1 (In *UKT).
N
Computational Complexity. The exploration phase requires O(NK) O ( rounds. The binary search performs Ollog 7') calls to EXTRACT-ORDER, each taking O(U time, for a total of OUUKU K2 log T). The final SP-MATCHING call takes (U + B)) time. Thus, the total computational complexity is O(U K" log T + K*B).
B GENERAL PREFERENCES ANALYSIS
In this appendix, we provide a comprehensive analysis of the computational complexity of achieving sublinear regret under general preferences. We first establish the fundamental hardness the offline problem, then derive its implications for online learning, and finally discuss the a-regret framework as tractable alternative.
B. HARDNESS OF THE OFFLINE PROBLEM
We begin by proving that the offline budgeted matching problem is NP-hard to approximate within any factor better than (1 - 1/e).
Theorem 1. It is NP-hard to approximate arg max (IT; Q) within any factor better than (1 - 1/e).
#ell
We proceed via reduction from the MAX (-COVER problem. In this problem, one is given a universe ll elements, a collection of subsets = {S Sm), and an integer f. The objective is to select at most l subsets whose union covers the maximum number of elements in U. This problem is known to be NP-hard to approximate better than (1 1/e)
Proof of Theorem [
Feige 1998).
Given instance of the Max f-Cover problem, construct CBR instance with U [M|] users (representing elements) and K = m arms (representing subsets). We set unit costs с₁ = 1, budget B L, and define preferences such that O,, k 1 element E S₃ and otherwise.
In this constructed instance, each matching induces a set of selected arms K. = {k: 3u E U (u) k). A user contributes where u E St- Accordingly, given a fixed K., the optimal matching allocates each user to a covering item if one exists: otherwise, the user yields zero reward. This implies that maximizing total reward is equivalent to maximizing coverage using at most E items. It follows that any algorithm approxi- mating the offline matching problem better than 1/e) would violate the inapproximability result for Max Ł-Cover.
the total reward only if assigned
selected arm
B.2 COMPUTATIONAL BARRIER FOR EFFICIENT ONLINE LEARNING
The NP-hardness of approximating the offline problem beyond (1 - 1/e) directly implics that effi- cient online learning with sublinear regret is impossible under standard complexity assumptions.
Corollary 15. For any U, K, B and = poly(U, K, B), any poly-time online algorithm achieves regret (T)), unless P= NP.
Assume towards contradiction that there exists an algorithm A running in per round that achieves regret Ry < CT for some constants p [0, 1) and C 0. for horizons T that are polynomial in U, K, B. For ease of presentation, we assume T = U RBB7 for some a; 3,,,7 1.
Proof of Corollary
15
time (Ul K,
Restriction to hard instances. By Theorem 1 the inapproximability result holds already for in- stances produced by the reduction from Max-E-Coue Feige (1998). These instances have e e (0, 1)7K with unit costs, budget B l, and at least instances we always have max+el((e) V(T; θ) 2 1. Since the hardness persists on this restricted subclass, it suffices to prove the corollary under the additional assumption max,,k Ou. 1.
entry equal to 1. Consequently, for such
17

---

Published as a conference paper at ICLR 2026
Construction of the online instance. Given such an offline instance with expected reward matrix O, we construct a deterministic online instance where the realized reward each (u, k) pair is fixed to k. Additionally, pick an arbitrary arm and duplicate it so that there are
e(p-1) z(e-1) D max { I (100) U 1 311 -)
copies of it. Let O' denote the resulting matrix. Duplicating an am cannot increase the optimal offline value, since multiple users can already be assigned to the same arm at no additional per- round cost. Therefore,
max V(T; (t); max V(T; θ OPT 2 1.
(EIT(G)
Simulating A. Run for U D rounds on the expanded instance, obtaining matchings π and return
hest arg max ; TE[T)
The regret guarantee yields
T
T OPT Σ V(T+:0)) S CT
Since bes 0¹)
DD 1= T
1
V(x": 6'), it follows that
OPT (iT best, 0¹) S CT
Approximation guarantee.
By construction of D, we ensured that CT < 0.1. Hence
OPT be O') s 0.1 S 0.1OPT.
Since any matching on the duplicated instance is equivalent one, without loss generality, we assume that best E [T()). Thus:
matching the non-duplicated
Ven Z 009V(=*;;))
The algorithm above runs in poly(U, K, B) time and produces a 0.9- approximation the offline optimum, contradicting the (1 1/ee))-aarddnsss result from Theorem unless P = NP.
Contradiction.
B.3 OPTIMAL REGRET WITHOUT COMPUTATIONAL CONSTRAINTS
we disregard computational constraints, optimal regret bounds can be attained by applying the standard CUCB algorithm (Chen al. (203)), assuming access exact optimization oracle.
Corollary 2. There exists UCB-bused algorithm that achieves regret of O(U VKT which optimal up to logarithmic factors.
Proof of Corollary 2 The CUCB algorithm (Cen al. 2013) maintains averages a.. (t) and counts & (t) for each user-arm pair. In each round f, it computes UCB estimates (t, = (t) 22 (t)), (or if (t) 0) and selects n, arg max V(T; P(t)) using optimization oracle. We note that we slightly changed the exact specification of the constants of CUCB, but it is of the same spirit.
By Hoeffding's inequality and a union bound over all (u, k) pairs and time steps, the clean event
E (0..k E [LCB k (t), UCB for all u, k,t)
holds with probability at least 2 We condition on E; its complement contributes negli- gible regret.
18

---

Published as a conference paper at ICLR 2026
Under ε, since P(t) is element- wise maximal over all matrices respecting the confidence bounds, optimistic selection ensures that for any round t:
max (T;; θ) (Tes Q) s V(TT; P(I) - V( () HEll
21n T
Σ wE[U]
2
(5)
nu, (w) (t)
V(=; P(t) V(T"; where n' is the optimal matching. The second inequality bounds the gap by the sum of confidence widths.
The first inequality uses optimism: V(T P(t))
Summing Inequality over all rounds and regrouping by arm pulls:
(T)
R 00
VInT E
E
wE|U]
KE[K]
j=1
vIn Σ Σ =0
V /e
DEJU] KE[K]
where used the standard bound Ej=1 1/v5 2/n. Applying Jensen's inequality the inner
sum yields Ex (u. (T) S VKΣR (T) VKT. Summing over all U users gives Ri OUUVTK InT).
The matching lower bound (UUVTK) follows from Theorem as SP instances form subclass of general instances.
While this algorithm is statistically optimal, assumes an optimization oracle that must solve an NP-hard problem at every time step, rendering it computationally impractical for general instances.
B.4 EFFICIENT APPROXIMATION VIA ALPHIA-REGRES
To bridge the gap between computational efficiency and performance guarantees, we consider the a-regret framework, which compares against the best efficiently computable solution rather than the true optimum.
Definition 5 (Alpha Regret), For approximation factor (0, the expected cumulative regret over rounds is defined as:
T
(T) = a max (T 9) - E
rt (u)
#ell
By reformulating our problem as submodular maximization subject to knapsack constraints, we can leverage existing approximation algorithms to achieve efficient learning with meaningful guarantees. Lemma 16. The reformulated reward function
f(5)
Σ LE[U]
max Ou,k
RES
is submodular and monotone.
Proof of Lemma 16
prove both properties separately.
Submodularity For M S N S [K] and & E [K] \ N, we need
f(M U (k}) f(M) 2 JNN (NU) f(N).
Let BM = maxjeM Ou, and AN = maxjEN Ou.j- Since M S N, we have BM s oN. The
marginal gains are:
J(MU (b)) - S(M) = Σ
max (0, Ou.k 0.4)
NE
19

---

Published as a conference paper at ICLR 2026
Table 1: Reward structure for the base case (Case 1). Costs are shown in parentheses.
Arm (c1 = 1)
Arm 2 (02 3)
Arm 3 (eg = =1 Arm 4 (ca 1)
User
User 2
0
0
User 3
J(N (k}) ((N)
Σ
max Ou,k -N
LE(U]
For each user u, since BM - S
max (0, Ou, 024 max 0u, 0.01
Summing over all users gives the desired inequality.
Monotonicity. For M S N, since ma Ou,k S maXKEN Qu,k for each user u, we have:
f(M) = Σ
max Ou S
Σ
max Ou, = f(N).
REM
REN
uE(U]
uElU
Proposition 17. There exists an algorithm running in O(K3U) time per-round achieving expected cumulative reegeet of:
[[R)
S ( +3)4312213
where B = B/mine is the budget-to poddee-toominnimum-comm ratio.
Proof of Proposition 17
Regret analysis. We reformulate our problem submodular maximiza- tion over subsets, where we select S C [K] subject to the budget constraint Σ C S B and each receives their most preferred item from the selected subset. The reformulated reward func-
tion f(S) = Eme maxkes Ou,k is submodular and monotone by Lemma 16 Under knapsack constraints, the MMxx algorithm of Yaroslavtsev
(0000) achieves } -aapproximation and 1 + K + 228 -robust in the sense of Nie et al. (2023). where K min K, B/Cmin) 2'
(0023 with normalized rewards and B B/ Cmin- Applying the C-ETC framework of Nie et al.
(ogg(T log(T)(/3) To obtain our clean bound, we use ( + K + 2/)2/3 < (K + 3)2/3 and (KK) < K2/3, then apply (K 3/2/3/ K2/3
f(S) f(S) yields the bound O(U ( + K + 2/3) (KK) 1/3T2/3
(K 4/3 to get the stated bound.
The runtime analysis stems directly from the algorithm Nie et al. (003)
C PROOF OF THEOREM 3
Theorem 3. For any algorithm, the worst-case regret over SP instances is Q(UVTK) and (Unxx(U VT, vTK)) when the SP order and user peaks are known.
Proof of Theorem regime.
We prove the lower bounds by constructing specific hard instances for each
Case 1: Known Order and Peaks (Rr ((UTT). We construct a family of hard instances parameterized by w = (()) E [1/4,3/4]2 To illustrate the construction, consider a "base case" consisting of three users and four arms with budget B = 3 and costs = (1, 3, 1, 1). The reward structure for this case shown in Table
20

---

Published as a conference paper at ICLR 2026
The full instance comprises U copies of User 1 (indexed 1....,U) U) and 20 copies of Users 2 and 3 (indexed U + 1..... "."). The instance is PSP with order 1 < 2 3 4. Users 1... U peak at Arm 2, while the others peak at Arm 4. Due to the budget B 3, any feasible matching must either select Arm alone (cost 3), or a subset of (1,3, 4). The optimal matching selects (1, 3, 4), assigning users 1 U arg max( 144 and the rest to Arm 4. The optimal expected reward is (*(w) = Σ max v1 + 2U.
Consider an algorithm A generating matchings n². Let 72 {1 [T]
Im(=') = (2)) be the rounds where Arm is selected, and Ti = [T T2. In rounds E T2. the reward is exactly U. In rounds E Ti, users U ++1...33 3U contribute at most 2U (if they are being matched to Arm 4), while user E [V] contributes based on their assignment to 1,3,4. Decomposing the cumulative reward, upper- bound the reward by
similar to the classical bandit analysis,
T Σ
V(=t:er)
S E
U 20 + Σ (NNNi + +
1==
where Nj is the number of times user matched arm j. The regret is then bounded by:
Ry 2 EA UT221 + Ti Σ max (oxx
Σ (n.N1 + +.
If [2]) 2 VT the first term yields ((UVT). If [[ < VT, then [[[ = 2(7),, and the remaining terms correspond the regret of U independent 2-armed bandit problems played for ((T) rounds. By the standard minimax lower bound (Auer al. 2002 this scales as ((UVT)
Case 2: Known Order and Peaks (Ry = Q(VTK). To capture the dependency on K, assume = 2, budget B (forcing a choice of exactly one arm per round), and costs C = 1. We construct family of hard PSP instances parameterized by i* E [K]. For each i the reward structure is defined as follows: User has preferences 1/2 + A for arms k S i* and 1/2 for arms k > i", while User 2 has preferences 1/2 for arms k < i and 1/2 + A for arms k 2 i
Each instance PSP: User I's preferences are non-increasing with a peak at arm 1, and User 2's preferences non-decreasing with peak arm K. For any choice of it, arm i* is the unique optimal arm with total reward 1 + 2A, while all other arms yield 1+ A. Identifying the optimal arm among K possibilities reduces to the classical K-armed bandit problem. Following the standard change-of-measure argument via Bretagnolle- ter 15)) with A x VK/T, we obtain a lower bound of ((VTK)) Note that although each round yields reward observations rather than one, this only affects the KL-divergence by a constant
(e.g.. Lattimore & Szepesvári (2020) Chap-
factor and does not change the order of the lower bound. Combining this with Case 1, we have a regret lower bound of [(max U VT, VTK)).
Case 3: Unknown Peaks (HT = Q(UVKK) If the peaks are unknown, we rely on the classic construction of the multi-armed bandit lower bound C.g..(SSivkin (2019 Chapter 2)). Specifically, we construct an instance where each user u has unique, unknown peak p(u) with reward 1/2 + A, while all other arms offer reward 1/2. Observe that such preference profiles are trivially PSP regardless of the underlying order arms, as they are constant everywhere except at a single point (the peak). Since the distributions are independent across users, learning the peak for user provides no information about the others. This reduces to U independent K Karmed bandit instances.
By the standard minimax lower bound, each user contributes ((VTK) to the regret, resulting in total regret of Q(U /TK).
D DEFERRED PROOFS FROM SECTION
Lemma 4. Fix any PSP matrix O with peaks p(-), and any arm subset {ki...., kmm) C K with by <... < km- Let nt" E arg max,, Im(x] V( O). For any user u, if kf S p(u) 1 kjt1 for some j with 1 & m. then x² (u) (ky, kit1 otherwise, x² (u() E kmn):
21

---

Published as a conference paper at ICLR 2026
Algorithm 6 SP-MATCIING
Require: PSP matrix P with peaks p(-), budget B, costs c(.)
Ensure: π = arg =a (TT; P)
1: Add arm 0 with cost co = 0 and Pu, = 0 for all E [0]
2: Vi,j E {0} U [K]:
Gij +
Σ
max(Pa.s: Pu.j
uits(()))
3: 4b ,..., B F(U. 5-
4: for k = -..... K do
5: for = Ck. B do
6: F(k, b) + max
[F(i, b - ct) Ga
kosickk
7: V* max kE[K]
B), +
E
Pu,k
scp(u)>*k
8: Backtrack to find selected arms 5*
9: return x²* (u) arg max Pu,k
Proof of Lemma 4
Recall that under single-peaked preferences, the preferences of each are unimodal with a peak at p(u)-the reward function 6u, is non-decreasing for I p(u) and non-increasing for p(u) I k.
For the first case, assume that k; I p(u) I ki+1 for some 1 J < m. For any < j. since ke < ki < p(u). the non-decreasing property gives Ou, &r S Ou.k.. Similarly, for any 8> j+1,, since p(u) 3 kit+1 z kiz, the non-increasing property yields Ou. 11 2 Ou,k. Therefore, any arm outside (ky, ky+1} is dominated by at least one arm in this pair, establishing that x x*(x)= {ky, kzt1].
For the second case, start with the case of p(u) I K1, which implies p(u) I k1 I .... - km- By the non-inereasing property after the peak, we have 0u,k 2 Ou,k2 xt (u) k1. The case of km I p(u) is similar, and yields x'" (u) kmm
kakkm. which implies
Theorem 5. For any PSP matrix, SP-MATCHING finds an optimal matching in time O(K3(U+B))
Proof of Theorem 5 Define OPT(k, b) as the maximum reward achievable when arm k is the right- most selected arm, the total budget at most b. and we consider only users whose peaks lie in (0, 1....... k... Note that the fictive arm O contributes zero reward and zero cost. We prove by induc- tion that F(k b) OPT(k; b) for all k 2 and b 2 0.
Base case: For the fictive arm, OPT(O, b) = 0 for all b < B since users have peaks at arm 0 and the arm contributes zero reward. The algorithm correctly assigns F(0, b) = 0 in Line (3.
Inductive step: Assume F(i
OPT(i, (i) for all 0 < i < k and all budgets Cs < V/ < b. For
any k 2 and budget b 2 Ck2 the optimal solution must select some arm with < i < h as the second-rightmont selected arm (where i 0 corresponds to selecting only arm k)).
By Lemma 4. users with peaks in the interval (i, k] are optimally assigned to either arm i or arm k contributing exactly Gi k to the total reward. Users with peaks in {0. l,..,,... i} contribute optimally according to OPT(i,
cx) by definition. Since the fictive arm 0 has zero cost, the constraint b 2 c Cj is always satisfiable with i 0. Therefore,
OPT(k, b) = max [OPT(i, cx) + G.,a).
aoSick. 620
The inductive hypothesis ensures that OPT(i, b cc) = F(i, ck), so:
OPT(k,6)
max BOSisk
[F(i, b b- ct) + G.,k] F(k, b).
t2
After computing F(k b) for all relevant values, Line computes
max
[kk, B) +
Pu,k]:
kE[K]
22

---

Published as a conference paper at ICLR 2026
which accounts for users whose peaks exceed the rightmost selected arm due to the second case in Lemma [ This ensures that the algorithm correctly computes the maximum reward for the given budget B. The backtracking reconstructs the optimal matching. from which we can exclude arm 0 it was somehow included by picking any other arm for that user.
Runtime Analysis: Computing the matrix requires UKK time. The dynamic programming fills O(K B) entries, with each entry requiring O(K) operations, yielding O(K²B) time. The remaining steps take O(KU) time. Therefore, the total complexity O(K"U + K²B). 0
E DEFERRED PROOFS AND DETAILS FROM SECTION 5
Lemma 6. For any non-emye non-empty confidence set (-. Hi), there exists a unique element-wise max- imal matrix pt E C such that Pt a.k Pu,k for all P E Ct and all [U], [K]. Furthermore,
min (t), k k3 p(u) this matrix is given by u.k min UCB,,,()),
p(u) k
Proof of Lemma First, observe that P SP by construction (as the values are defined via running minimum moving away from the peak) and satisfies ps < UCB by definition.
Next, assume towards contradiction that there exists matrix P E and a pair (u, k)) such that Pa,k > pf a,k- By the definition of Pt, there exists an index k with either k 3 k' I p(u) or p(u) < k' k such that Pú, UCB.,, (4). From our assumption,
have Pu,a UCB.,
Since P C, Definition 3 ensures that Pu,K S UCB (t). Combining these inequalities yields Pa.k > UCB.,NY (t) 2 Park However, the SP property of P with peak at p(u) implies Pu,k S P..k (since both arms lie on the same side of the peak), contradicting Pa,k Pa,k'
Finally, if C' is non-empty, then for any P C², we have P 2 P LCB, ensuring P E C and completing the proof.
Theorem 7. For any SP instance with known SP order & and peaks p(-), MvM achieves regret of al most OU ((UVTKIn') with per-round runtime of OKKUU B)
Proof of Theorem 7 The analysis follows the same structure the UCB- based algorithm in Corol- lary 2 with the maximal matrix P playing the role of the UCB matrix. We condition on the clean event {O C for all t). which holds with probability least 2/rr by Hoeffding's inequality and union bound.
Under E, since pt element-wise maximal in C² (Lemma 6). the per-round regret satisfies Inequal- ity 3 Summing over rounds and applying the same regrouping and Jensen's inequality arguments as in the proof of Corollary 2 yields Rt DUUTTKln InT)
For the runtime, each round involves updating statistics (O(U)), constructing p' via Lemma (O(UK) and running SP-MATCHING (O(K²(U + B)) by Theorem 5). The complexity is domi- nated by the matching step.
F DEFERRED PROOFS FROM SECTION
6
Proposition 8. A matrix is SP w.n.t an order x if and only if is 0-ASP w.r.t. X.
Proof Proposition g First, assume P is SP w.r.t. <. By definition, for any user u, the values Pa,k non-decreasing up to peak p(u (u) and non-increasing thereafter. Consequently, for any triplet < j < E, the middle element j must satisfy Pu,; 2 Pa, (if 3 p(u)) or Pajj 2 Pu. (if j p(u)). In either case, Pu.j j 2 min (P,i, Pu.e), satisfying the O-ASP condition.
Conversely, suppose For any i < p(u), the O-ASP condition implies Pu, 2 min Pu.s. Pu,p(r)) Pu,i- ensuring non-decreasing values to the left of the peak. By symmetry, values are non-incnee con-increasing to the right of the peak, implying that P is SP.
O-ASP w.r.t. x. For any user u, let p(u) be an index maximizing Pu..
23

---

Published as a conference paper at ICLR 2026
Lemma 9. Let P be 6-ASP matrix w.E..
There exists matrix P which is SP w.E.. x, and
satisfies ||P Plac S
Proof of Lemma and define P as follows:
9 The proof is via construction. For every set = arg m [k] Pu,k
max Pu,is k 1 p(u) max Pa,i, p(u) 3
Pu,e
The matrix P is SP w.r.t. < by construction: for each user u, the row P.,() is defined as a running maximum from the endpoints toward p(u), ensuring non-decreasing values for 3 p(u) and non- increasing values for & ž p(u).
It remains to show that || Pl S Consider an entry (u, k) with k 2 p(u). By construction, Pa.A = max Pa,s. If the maximum is achieved at A: itself, then Pa,k Pu,k Otherwise, the maximum is achieved at some k, and we have Pa, Pa. I Pu,k 5, where the inequality follows from applying Definition Io the triplet i < < p(u). A symmetric argument applies when p(u) < k. Since Pu,k 2 Pu,k by construction (as the maximum includes Pu,k itself), we conclude |Pu, Pa,xl S 6 for all (u,k).
Lemma 10. Let P be a matrix such that || Plox I E for some SP matrix P. EXTRACT- ORDER( P,,) returns an order - such that P (2KE)-ASP w.r.t A.
Proof of Lemma 10 We first establish the existence of order that satisfies all the constraints; we do so via the SP order of P. which we denote as <p. Fix some u E for which a contiguity constraint on the set of arms S :.f:...; km) was imposed. Due to Lines 3- we must have minkes Pa,k
maxwes Pu,k' > 2c. Since ||P Pllce S E, this implies minkes Pu,k max Pu,kr > O. Thus, because P is O-ASP w.r.t. <P, <p must satisfy this constraint well; otherwise, as was previously discussed, we could have found a triplet of arms that contradicts Definition 4
Next, let be a returned order (one must exist, as our first step suggests). Fix u and arms < l. We must show Pu.y 2 min(Pu.: Pa.e] 2Ke. Assume w.l.o.g. that Pu, S Pu,e- Consider the arms sorted by preference ki ....... ki. If there were any index m such that {K4 (Ai...., km.) includes i and & but excludes and the gap PuAA= Pu, > 2s, the algorithm would constrain this set to be contiguous. This would force outside the interval between i and f, contradicting < x l. Therefore, no gap exceeding 2s exists in the sorted sequence between the values Pu,i and Pu.j- Summing these gaps (at most K) yields Pa,s - Pu.j 2Ke.
Theorem 11. EMC(N = 2 2 yields an expected regret of at most ŌUUKT2
T/n By Hoeffding's inequality and a union bound, the clean event = {|| Nox S E} holds with probability least 1 2K0/T= complement, go, occurs with low probability and contributes at most TU to the overall regret; thus, we condition the rest the proof on E. Under E, the approximation guarantees from Lemmas / and I0 combined imply that the constructed matrix Ô satisfies || O11 & 2Ks. By the triangle inequality, the total estimation error is bounded by
Proof Theorem 11 Let
| -
S (2K 1) 2
Now, let स be the matching computed in Line (5) and let nt" be the optimal matching w.r.t. θ. Using Inequality (6) we can bound the regret of a single commitment round (t > K.N as follows:
V(T*; (a; θ) < V(=" () V(#; () + 2UK + 22/2n/// < 2UK +1)
where the last inequality follows the optimality of ã with respect é. Thus, by dividing into exploration and commitment rounds, we can bound the total regret by
Ri < 0 (KNU +T T PU + ( 22nTT/
24

---

Published as a conference paper at ICLR 2026
Substituting N T1/ //// yields Ry & OUUKT (In (InKT) () O(UKT which completes the proof.
Theorem 12. Consider the following optimization problem, termed MAX-SP-WCS. given sets of users U and arms K, matching π :U - K, and confidence intervals [LCB k for each (u,k) E U K, find max (T;; P), where C contains all matrices respecting the confidence intervals. Then, approximating MAX-SP-WCO within factor of 3 + 5 is NP-hard for any 5 > O.
1
Proof of Theorem 12 We reduce from MAX BETWEENNESS (Opatrny 1979. Austrin et al. 2015), which involves, given set of elements S and collection of ordered triplets G C S finding a linear order of S that maximizes the number of triplets (a, b, c) E G for which element lies between and in the order. [Austrin et al. (2013) show that for any n > 0, it is NP-hard to distinguish between instances where at least (1 7) fraction of triplets can be satisfied versus at most (1/2 + 7)) fraction.
Reduction. Given a BETWEENNESS instance (S, G), construct a MAX-SP-WCS instance as fol- lows. Create arm for each element 8 E S, so K = S. For each triplet g (ag. Cg) G, create two users Ug and Eg. so U = {Ug, fy E G}. Define the matching by T(U)) = 0g and (Vg) = Cy. Fix (0, and set confidence intervals as:
8, 11,
k= bg k= Cg otherwise
[LC u k, UCB uy
[0,c],
[0,1];
[],
k == bg k og otherwise
[LCB,, UCB
[0,
[0, 1],
This construction is polynomial in the size of the BETWEENNESS instance.
Key observation. Fix any arm order < and triplet g = (ag. by. Cgy) If by lies between ag and cg in x, we can complete both rows Ug and 1gg unimodally with peaks at by that respect the confidence intervals and achieve Prgiag P Pr..r 1: set Pa,, = for all arms k on the same side of b, as dg (including by), and Pa,, = 0 otherwise; similarly for V/g-
Conversely, b, does not lie between ag and cy. then either Cg lies between ag and by. or ag lies between b, and Cg. In the former case, single-peakedness requires Pag,og Pugie or &a s Pa since the confidence intervals enforce Puçe,, I ε and Pu,.,, 2 1 - E, we must have Pag.ag I e. By symmetry, in the latter case, Puy.e, I These bounds be achieved with equality.
Therefore, the contribution from users Ug V/ is exactly 2 if triplet t is satisfied by and 1+ otherwise. Hence, if s triplets are satisfied:
(iT; P) 2s + (IG) s) + +) [G](1 + + s(1 E)).
Hardness of approximation. Consider MAX BETWEENNESS instance I that is hard to distin- guish. Denote the corresponding MAX-SP-We. -CCS instance by i, and let OPT({) denote the optimal value of i. If at least (1 11) G| triplets of / can be satisfied, which we refer as case H. we would have:
OPT(Ín) 2 [G + e) + (1((1)))( (1 =) = [2 - 7 + an))
On the other hand, at most (1/2 + G) triplets can be satisfied, which we refer to as case L:
OPT(Ír) < [G](1 + + (1/(1/2 + (1 s) |G] (3/2 + +/2 en)
Suppose there exists a-approximation algorithm ALG for MAX-SP- WCS, i.e., ALG(Î) N OPT(T) for all MAX-SP-WCC instances f. Then, in case H, we would have ALG( a (fT( while in case L ALG(Í,) s OPT(ÍL) will hold trivially. Notice that if ALG(IH) (PT(Ír), we could distinguish the two cases. This holds whenever:
OPT(İ))
3 + en ne-+0
3/2
2
OPT(In)
2 - 2 +
2
25

---

Published as a conference paper at ICLR 2026
Thus, for any 8 0, 3 + a)aappooximaaionn algorithm would distinguish between hard instances for sufficiently small 17, E, contradicting the NP-hardness of MAX BETWEENNESS.
G HANDLING TIES IN PEAK INDICES
In the classical study of single-pakked preferences in social choice theory, preferences are ordinal- each user provides a ranking over alternatives rather than cardinal utility values. In this ordinal setting, ties at the peak do not arise: the peak is simply the top-ranked alternative, which is unique by definition. However, in our cardinal framework, a user u may have multiple indices & that achieve the same maximal expected reward max Ou When this occurs, the peak p(u) defined in Definition is not unique, and we must verify that our algorithms and analyses are robust to arbitrary tie-breaking choices.
Robustness of the Offline Algorithm. We begin by establishing that Lemma 4 is robust to the arbitrary choice of peak when a user has several maximizers. Suppose user u has two peak indices < y with w, ou.y maX x) Ou,k. and fix selected set S {ki < k2 .... km }. We claim that the value of the optimal matching of u against S is independent of whether we set p(u) x or p(u)= = y. To see this, observe that exactly one of the following cases holds:
There exists {L...., m - 13 with ky S. S y S kj+1 and no ke (x,y). By uni- modality, any arm outside (k,, k is dominated by one of them, so T (u) E ky1, regardless of the tie-break.
y I ks. Values are non-increasing to the right of the peaks, hence x (u) = 1 regardless of the tie-break.
km S x. Values are non-decreasing to the left of the peaks, hence '- (u) = km regardless of the tie-break.
There exist indices i S with x S hi S .... < kig S y. Since all k E [2. y) attain the peak value by the single-peaked property, any k (ki,...,h ,.)k))))))) is optimal. The lemma asserts x (u) E (k;-1, } the peak is set to v, and x ="(n) E (ky, kjt1) } if the peak is set to y- In either case, the attained value maxies 0a, remains unchanged.
In every case, u's contribution the matching value is invariant to the choice of peak.
This invariance extends to SP-MATCHING (Algorithm 6). Observe that every choice of the right- most arm k in Line corresponds subset of selected according to Lemma 4 By the argument above, the attained value of each user in this subset is inde- pendent of how we resolve peak ties. The choice of peak only affects when account for user's contribution during the dynamic programming computation, not the contribution itself. Therefore, running SP-MATCHING with different valid peak indices yields the same optimal value V*.
and matching that assigns each user
Robustness of the Online Algorithm with Known Structure. For the MvM algorithm (Algo- rithm [ we must verify that the maximal matrix construction in Lemma remains valid when users have multiple peak indices. Suppose user u has peak indices p, + 1, .......7.. . P m for some m 2 O, and this information is known to the algorithm. The maximal matrix consistent with this structure should assign the same value to all peak indices, equal to the minimum of their upper confidence bounds. Formally, one could define:
minge m UCB (t) miinkksisp UCB (D),
E {p, + I,.....7. . m}
pf u.k
k < p
miniipziee (t),.:(t),
p x k.
However, for any choice peak index p + i with i E {O...., m). using the original definition from Lemma 6 yields matrix that element-wise upper bounds this modified construction. Thus, the regret analysis of Theorem 7 remains valid even if we use a slightly loose upper bound that may technically fall outside the confidence set. The key properties used in the analysis ttat P' upper bounds any matrix in the confidence set and that p is mingle-peaker with respect to <<-onninue to hold.
26

---

Published as a conference paper at ICLR 2026
Unknown Structure Regime. For the algorithms in Section 6 peak ties do not require special treatment. In this regime, peaks are not explicitly computed or used by the algorithm; they only appear implicitly through the call to SP-MATCHING in Line 5 of Algorithm [ Since have already established that SP-MATCHING is invariant to the choice of peak indices, the analysis of EMC and its extensions remains valid regardless of how ties resolved.
H EXPERIMENTAL VALIDATION
In this section, we present computational experiments to demonstrate the practicality of our algo- rithms and provide empirical validation of the theoretical regret bounds.
H.1 SIMULATION DETAILS
We now describe the synthetic setup used to evaluate our algorithms, including instance generation, implementation details, and experimental protocol.
Instance generation. We constructed single-peaked expected reward matrices θ using the follow- ing procedure: for each user u, we first sampled K preference values independently from uniform distribution over [0.2, 0.9]. We then selected a random peak location p(u) E [K] and arranged the values to create a unimodal preference profile-The largest sampled value was assigned to the peak, while the remaining values were sorted and distributed to create an increasing sequence up to the peak and a decreasing sequence afterward.
The actual rewards observed during algorithm execution were drawn from Bernoulli distributions, where uu ~ Ber() for each user-arm pair. We set unit costs for all arms (Cx = 1 for all k) and used budget constraint of B K/2], allowing selection of approximately half the available arms in each round.
Algorithmic implementation. The implementation of EMC and MvM uses standard Python sci- entific computing libraries (NumPy, Pandas) without GPU acceleration, as the algorithms are pri- marily CPU-bound. The SP-MATCHING algorithm, used by both algorithms, was implemented using the dynamic programming approach described in Algorithm 6 Additionally, for the PQ tree implementation, used the SageMath library (The Sage Developers 2025), standard Python package for advanced mathematical computations.
Experimental setup. We tested both algorithms 10 random instances with U 100 users and K 20 arms. We estimated the expected regret using 10 independent runs for each instance. For the EMC algorithm, we tested time horizons ranging from T 10a T 10th rounds. To simulate the unknown order setting, we randomly permuted the columns of each generated single- peaked matrix before running the algorithm. For the MyM algorithm, we executed single run up to T = 10's rounds, recording the cumulative regret at each time step to observe the full regret trajectory. This method naturally serves as an upper bound on the regret that would be incurred if the algorithm were run separately for smaller values of T. However, we still observe the same predicted asymptotic behavior. Since this algorithm assumes a known order and peaks, we provided the true peaked structure directly without column permutation.
The difference in the number of rounds T' for the two algorithms stems from the fact that EMC necessitates larger time horizons to ensure sufficient number of commitment rounds relative the exploration rounds.
Used hardware. The complete simulation suite was executed standard MacBook Pro with 18 GB of RAM and 8 CPU cores. We utilized parallel processing across five cores to accelerate computation. The complete of experiments required approximately 6 hours of computation time.
27

---

Published as a conference paper at ICLR 2026
14.55
21 Itd
growth
Plar 901155 10 ind.anoos
logecumaaatto sagreed
16.00
1925
krgit
legiround
(a) EMC Algorithm
(b) MvM Algorithm
Figure 2: Log-log plots cumulative regret versus time for both algorithms. Each plot shows the mean regret over all 10 instances (with 10 runs each) and shaded regions indicating standard devia- tion. The EMC algorithm (left) achieves a slope of approximately 0.69, approaching the theoretical guarantee of 2/3 z 0.67. The MvM algorithm (right) demonstrates slopes below 0.5, consistent with the theoretical bound.
H.2 RESULTS
Figure presents log-log plots of cumulative regret versus time for both algorithms. Each plot dis- plays the mean regret computed over all 10 instances (with 10 runs each), along with shaded regions representing the standard deviation. The narrow confidence bands demonstrate the consistency of our results across different problem instances and random seeds. Note that the two plots use dif- ferent x-axis representations: the EMC plot (Figure 2ab shows log(T) where each point represents the total regret after 7 rounds of interaction, while the MvM plot (Figure 2b) shows log(t) with the cumulative regret trajectory at each round t.
The EMC algorithm. As shown in Figure 2a the algorithm exhibits consistent behavior, as evi- denced by the nearly indistinguishable standard deviation bands. The fitted slope is approximately 0.694, approaching but not quite reaching the theoretical prediction of 2/3 0.667 from our Ō(U KT2/3) regret bound. When tested for larger time horizons, the empirical slope approaches the theoretical value of 2/3, confirming the asymptotic prediction of our analysis.
The MvM algorithm. As shown in Figure 2b the algorithm demonstrates excellent empirical performance with slopes ranging from 0.388 to 0.434 across different instances. All observed slopes fall strictly below the theoretical upper bound 0.5, corresponding to our ÖUUVKT) regret bound. The variation in slopes across instances reflects the algorithm's 's adaptive nature: instances with more challenging preference structures result steeper regret growth, which corresponds to slower learning. The small standard deviation bands indicate that the algorithm's performance is stable across multiple runs of the same instance. This gap between empirical performance and theoretical bounds suggests that our analysis may be conservative for typical problem instances.
Comparison. The empirical slopes-0.694 for EMC versus 0.388-0.434 for MvM-bighlight the cost of unknown order. While both algorithms achieve sublinear regret, the MvM algorithm's knowledge of the single-peaked structure enables significantly better asymptotic performance. The EMC algorithm's 's performance is hindered by the finite-hories horizeh effects discussed above, but still achieves sublinear regret that would approach the thcoretical rate with larger time horizons.
BIPARTITE BUDGETED MATCHING VARIANT
In this appendix, we address recommendation setting where each arm may serve at most one user.
Our
code is
available
code for- Ban di ts Baawwithe wew.
papper
28

---

Published as a conference paper at ICLR 2026
1.1 PROBLEM FORMULATION
We consider the same stochastic setting as in our main model (T,U, (Du,))u, (cx) B), but with different notion of valid matching.
In our main model, multiple users may be assigned to the same arm in a round, and the budget constraint applies to the set of distinct arms used. In the bipartite variant considered here, each user can be matched to at most one arm, and each arm can be matched to at most one user (one-to-one matching). For simplicity, we focus on the case of unit costs; the case of general costs remains an interesting problem for future work. In each round, the learner chooses matrix X E {0, 1) satisfying
Σ Fa,k S Vu,
Σ sun S1VK,
Lukb S B, Σ u.K
and receives an expected reward V(T; En. Ou Similarly to before, we denote by 87 the set of feasible matchings, where each matching corresponds to a matrix that satisfies these constraints. The only change from our main model the feasible set of matchings; the stochastic structure and regret definition remain unchanged.
1.2 POLYNOMIAL- TIME ALGORITHM FOR THE OFFLINE PROBLEM
We start our analysis by showing that the offline budgeted bipartite matching problem can be solved in polynomial time using reduction to either the Hungarian algorithm or a min-cost flow formula- tion.
Proposition 18. We can solve arg max VTT;; θ) in polynomial time.
Proof of Proposition 18 We divide our proof into two cases based on the relation between the budget and the number of users and arms.
Case 2 min(U, K). this case, the budget constraint is non-binding, and we can simply find the maximum weight matching in the bipartite graph formed by users and arms. Formally, we first pad the smaller side the bipartite graph with dummy nodes to make it square. W.l.o.g., assume U s K; add K U dummy users with @u.A 0 for all arms k. We then apply the Hungarian algorithm to find the maximum weight matching in this square bipartite graph, which runs in (K33) time. Since the padded users do contribute the reward, the resulting matching is optimal for our original problem.
Case B min(U, K). In this case, the budget constraint binding, so we formulate the problem as min-cost flow problem. We construct a flow network as follows:
Create a source node and sink node t.
Create a node Ag for each user u and a node B3 for each arm
Add edges from s to each user node A, and from each arm node B₁ to t with capacity and cost O.
For each user-arm pair (u, k), add an edge from A, Ba with capacity and cost -O,..
Node has a supply of B, and node has a demand of B.
Since the total supply at is and the total demand at B, any valid flow of value B corresponds to selecting exactly B edges between users and arms.
By the Integrality Theorem of minimum cost flow, since are capacities and node sup- plies/demands are integers, there exists integer-valued optimal flow f". In our network, since capacities are 1, this implies the flow on any edge (Ag, Bt) is either or 1. We construct the matching X by setting Fui 1 if and only if the flow edge (Au, B&) is 1. The capacity straints on edges (s, A,) ensure Ex Ln,k I 1, and the capacity constraints on edges (Bg, t) ensure Σ,, Fu.k < 1. Finally, the total flow value of B ensures Σn,k Lu,k B.
29

---

Published as a conference paper at ICLR 2026
The total cost of the flow is En.k Fu,k(--u,tt - Tu.k Therefore, minimizing the cost is equivalent maximizing the total reward V(==; Q). Since min-cost flow can be solved in polynomial time, the offline bipartite budgeted matching problem is efficiently solvable.
1.3 ONLINE ALGORITHM
Since the offline optimization problem can be solved efficiently, we can employ standard Combina- torial MABs algorithms without relying the single-peaks structure. Although algorithm from Corollary to this setting, we prefer to use the COMBUCB/ algorithm from Kveton et al. (2015a) and its guarantees with our efficient offline solver as the oracle.
adapt the
Corollary 19. There exists an efficient online algorithm for the bipartite budgeted matching problem that achieves Ö ((VT) regret.
We can apply COMBUCBI I using the offline solver from Proposition 18 as the offline oracle. Since the reward function (T;; θ) is linear in the matchings and the offline oracle exact, the analysis of Kveton et al. (2015a) applies directly. The worst-case regret is bounded by O(
Proof of Corollary 19
where L UK is the number of total items (where item in this setting corresponds to choosing to match user and item), and Ktot = B the maximum number chosen items in a valid matching. Thus, the regret scales as O(VUKBT), and the per-round computational complexity is polynomial in U, K, and B.
1.4 LOWER BOUND
We complement algorithmic result with matching lower bound, showing that the dependency on U, K, and I is unavoidable.
Theorem 20. For the bipartite budgeted matching problem with K 2 U, any online algorithm incurs an expected regret of ((VUKT)
Construct hard instance where the set of arms [K] is partitioned into U disjoint subsets Si...., Sy. each of size |Sa] 2 2. User receives rewards only from arms in S., Specifically, for each u, arm in S., yields Bernoulli rewards with mean 1/2++, c, while others S, have mean 1/2. Arms outside S, yield Since the subsets are disjoint and users are only compatible with their specific subsets, the global problem decomposes into U independent multi- armed bandit instances. The constraints Σx Fn,k < 1 and >,, Tu.k S are satisfied independently within each subset. Assuming sufficient global budget B > U, the total regret is the sum of regrets from U independent bandits, each with K/ K/U arms over T rounds. Using the standard minimax lower bound of ((v ( for K" arms:
Proof of Theorem 20
R(T) Σ Ω
K (VOT))
KT UV
=Ω -Q(UKT))
(VT)
30


Reviews:
[{"review_id": "cuXqiLpOj5", "reviewer": "Reviewer_hCLu", "summary": "This paper studies a budget-constrained matching problem. The authors first point out that, under general preference structures, the problem is NP-hard even in the offline setting. To overcome this computational barrier, the paper introduces the assumption of single-peaked (SP) preferences, which theoretically ensures tractability. For the offline case, the authors propose a dynamic programming algorithm, SP-MATCHING, which computes the optimal matching in polynomial time under a known SP order. This algorithm provides the theoretical and computational foundation for the subsequent online methods. In the online setting, the paper considers two cases:\n\n1.\tWhen the SP structure is known, the authors propose an optimistic algorithm MvM (Match-via-Maximal) based on maximal matrices, which uses SP-MATCHING each round to compute the optimal matching and achieves sublinear regret $O(\\sqrt{T})$.\n2. When the SP structure is unknown, the authors propose an explore-then-commit (EMC) method that first learns an approximate preference order from data collected in a round-robin manner via an EXTRACT-ORDER process based on PQ trees, and then executes this policy based on the approximate preference order, achieving regret $O(T^{2/3})$.\nThe paper further establishes corresponding regret lower bounds for the known and unknown peak settings. Experiments on synthetic data validate the theoretical results.", "questions": "1. For the UCB-based algorithm, the authors claim that solving the optimization problem requires a known SP order. How about using the estimated order from the estimated means and UCB/LCBs? Specifically, though the total order is initially unknown,  the algorithm can construct a partial ordering based on estimations. Can the algorithms solve some optimization problem corresponding to partial ordering to avoid the strong assumption and get an $O(\\sqrt{T})$ regret? The authors can discuss this point. \n2. Writing suggestion (optional): When two algorithms are available, usually the paper first presents an algorithm that requires strong assumptions to convey some intuition and then presents a more general one.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces the single-peaked (SP) structural assumption for budget-constrained matching, turning an otherwise NP-hard problem into one solvable in polynomial time. This may offer a principled blueprint for simplifying other computationally hard online learning settings.\n2. The algorithmic design is well structured: SP-MATCHING yields a polynomial-time optimal solution offline; the online setting presents MvM (known SP) and EMC (unknown SP), both built on SP-MATCHING. The theory is tight and carefully argued, with detailed proofs of regret bounds and supporting lemmas in the appendix. The results are complete with both upper bounds and lower bounds provided.", "weaknesses": "1.\tStrong assumptions.\nThe paper relies on the single-peaked (SP) preference assumption, which may be overly idealized in complex real-world environments. Although the paper states that this preference structure is common in various domains, such as recommendation systems (Line 049-052), no reference is provided for justification. The additional requirement of known SP order and user peaks for the MvM algorithm is unrealistic, which limits its applicability. \n\n2. Insufficient experiments.\n\nThis paper introduces a new matching setting with a budget constraint, which appears to have not been studied before. The experiments are also restricted to synthetic data. No real-world applications/datasets have been tested. Moreover, the paper lacks comparisons with general combinatorial bandit baselines, particularly those without SP assumptions but with α-regret guarantees, which would better contextualize the claimed advantages.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5qvtO96Rw8", "reviewer": "Reviewer_486h", "summary": "This paper addresses an online stochastic matching problem where a learner sequentially matches users to arms under budget constraints, aiming to maximize cumulative reward over $T$ rounds. The key innovation is leveraging single-peaked (SP) preferences to overcome computational intractability, where user preferences are unimodal with respect to a common arm order. This paper studies 1) offline setting, 2) online setting with known preference structure, and 3) online setting with unknown structure.", "questions": "1. Could the SP assumption be relaxed to more general structures while retaining computational efficiency?\n2. What is the hardness in designing algorithm attaining $O(\\sqrt{T})$ regret for online setting with unknown structure? Is it possible to improve the lower bound by constructing instance with this hardness?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. ​​The paper bridges combinatorial bandits and social choice theory by incorporating SP preferences, transforming an NP-hard problem into a tractable one while maintaining standard regret bounds instead of approximate regret.\n2. ​​Both offline and online algorithms are designed with theoretical guarantees. The maximal matrix construction for MvM and PQ-tree-based order recovery in EMC demonstrate creative problem-solving.\n3. ​​Experimental results demonstrate theoretical regret rates.\n4. The budget constraint modeling and SP assumption aligns well with real-world applications like content recommendation.", "weaknesses": "My major concern is the gaps in bounds​​ of online setting with unknown structure. The gap between EMC's $O(UKT^{2/3})$ regret and the $\\Omega{\\sqrt{KT}}$ lower bound suggests potential for improved algorithms or tighter analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BYzPbOabiE", "reviewer": "Reviewer_6YQV", "summary": "This paper studies an online stochastic matching problem where a learner must sequentially match users to arms under a budget constraint, with the goal of maximizing cumulative reward. The general problem is NP-hard, but the authors circumvent this computational barrier by imposing a single-peaked preference structure, a well-known concept from social choice theory where each user's utility is unimodal with respect to a common ordering of the arms. For the offline problem, they develop SP-Matching, an efficient dynamic programming algorithm that finds the optimal budgeted matching. Leveraging this, they propose two online algorithms: EMC, an explore-then-commit algorithm for the challenging case of unknown preference structure, which achieves a regret of $\\tilde{O}(UKT^{2/3})$ by extracting an approximate order using PQ trees; and MVM, an efficient UCB-like algorithm for the case of known structure, which achieves a tighter regret of $\\tilde{O}(U\\sqrt{TK})$ by leveraging a novel maximal matrix within its confidence sets. This paper also gives a regret lower bound analysis for both known and unknown peaks cases.", "questions": "See weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The single-peaked preference assumption is grounded in social choice theory and circumvents NP-hardness, enabling efficient algorithms with standard regret bounds instead of weaker α-regret.\n2. It provides a complete landscape by offering efficient algorithms for both unknown (EMC) and known (MvM) structure settings, while rigid theoretical analysis are given on both algorithms.\n3. The PQ-tree-based order extraction method and the concept of a maximal matrix, which enables optimistic planning while preserving structural constraints, are novel.", "weaknesses": "1. While lower bounds are provided, gaps remain between upper and lower bounds in some settings (e.g., for EMC). The paper does not conclusively determine if the attained rates are optimal for polynomial-time algorithms in the unknown structure case. To my knowledge, the ETC-based algorithm is not an order-optimal algorithm in the classical stochastic MAB problem, so it is not surprising that there exists a gap between the upper and lower bounds. Even though the proposed EXTRACT-ORDER algorithm used in EMC provides insight into the construction of an ASP order.\n2. The setting that different users can be matched to the same arm simplifies this problem, while a more common setting is the bipartite matching between users and arms.  \n\n\nMinor\n1. Title of Section 4.3: written as ETC instead of EMC.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tzQUJNHf9A", "reviewer": "Reviewer_jqPn", "summary": "This work studies an online stochastic matching problem involving $U$ users and $K$ arms, aiming to maximize the cumulative reward over $T$ rounds under budget constraints. Without assuming any structural property of user preferences, the problem is NP-hard, rendering online learning computationally infeasible. To address this, the authors focus on the case of single-peaked preferences. They first propose an efficient algorithm that achieves a regret of $\\tilde{O}(UKT^{2/3})$. When the single-peaked structure is known in advance, they further develop an algorithm that attains a regret of $\\tilde{O}(U\\sqrt{TK})$.", "questions": "Is there a specific reason for using the term ``preference'' here? To me, preference suggests a Bradley--Terry--Luce--type model, where the reward of each arm is defined relatively, depending on the assigned counterpart.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This is the first work to study the matching bandit setting under single-peaked preferences, where an efficient algorithm can be designed. The proposed method achieves a tight regret bound when the preference structure is known.", "weaknesses": "The main concern lies in the tightness of the regret bound under the unknown structure. The authors propose an ETC-based algorithm that achieves a regret of order $T^{2/3}$, which appears to be suboptimal. Establishing a tight regret bound for the unknown-structure case would be a meaningful goal, as the current result seems incomplete. If achieving a tighter bound is not possible, the authors should at least provide a corresponding lower bound to justify that the $T^{2/3}$ rate is optimal. Moreover, the ETC and UCB algorithms themselves do not appear to be novel.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)