# Bandits with Single-Peaked Preferences and Limited Resources

arXiv: https://arxiv.org/abs/2510.09425 · HTML: https://mlsanity.com/paper/2510.09425/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 35 references that are in the map.
- First posted on arXiv 10 Oct 2025.

## Builds on (most cited first, 12 of 12)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Competing Bandits in Matching Markets](https://mlsanity.com/paper/1906.05363/) (2019)
- [Modeling Content Creator Incentives on Algorithm-Curated Platforms](https://mlsanity.com/paper/2206.13102/) (2022)
- [Optimizing Long-term Social Welfare in Recommender Systems: A Constrained Matching Approach](https://mlsanity.com/paper/2008.00104/) (2020)
- [A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback](https://mlsanity.com/paper/2301.13326/) (2023)
- [Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits](https://mlsanity.com/paper/1503.05087/) (2015)
- ["Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack](https://mlsanity.com/paper/1910.05646/) (2019)
- [Clickbait vs. Quality: How Engagement-Based Optimization Shapes the Content Landscape in Online Platforms](https://mlsanity.com/paper/2401.09804/) (2024)
- [Thompson Sampling for Bandit Learning in Matching Markets](https://mlsanity.com/paper/2204.12048/) (2022)
- [Learning with Exposure Constraints in Recommendation Systems](https://mlsanity.com/paper/2302.01377/) (2023)
- [Structure in Dichotomous Preferences](https://mlsanity.com/paper/1505.00341/) (2015)
- [An α-No-Regret Algorithm For Graphical Bilinear Bandits](https://mlsanity.com/paper/2206.00466/) (2022)

## Abstract (arXiv)

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(UKT2/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√TK).