Combinatorial Allocation Bandits with Nonlinear Arm Utility

• URL: http://arxiv.org/abs/2603.07005v1
• Date: Sat, 07 Mar 2026 02:57:27 GMT
• Title: Combinatorial Allocation Bandits with Nonlinear Arm Utility
• Abstract summary: We propose a novel online learning problem, Combinatorial Allocation Bandits (CAB), which incorporates the notion of *arm satisfaction*.<n>Unlike prior work, the learner's objective is not to maximize the number of positive feedback, but rather to maximize the arm satisfaction.<n>We provide an upper confidence bound algorithm that achieves an approximate regret upper bound, which matches the existing lower bound for the special case.
• Score: 37.64693919880475
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A matching platform is a system that matches different types of participants, such as companies and job-seekers. In such a platform, merely maximizing the number of matches can result in matches being concentrated on highly popular participants, which may increase dissatisfaction among other participants, such as companies, and ultimately lead to their churn, reducing the platform's profit opportunities. To address this issue, we propose a novel online learning problem, Combinatorial Allocation Bandits (CAB), which incorporates the notion of *arm satisfaction*. In CAB, at each round $t=1,\dots,T$, the learner observes $K$ feature vectors corresponding to $K$ arms for each of $N$ users, assigns each user to an arm, and then observes feedback following a generalized linear model (GLM). Unlike prior work, the learner's objective is not to maximize the number of positive feedback, but rather to maximize the arm satisfaction. For CAB, we provide an upper confidence bound algorithm that achieves an approximate regret upper bound, which matches the existing lower bound for the special case. Furthermore, we propose a TS algorithm and provide an approximate regret upper bound. Finally, we conduct experiments on synthetic data to demonstrate the effectiveness of the proposed algorithms compared to other methods.

Related papers

• Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation [17.2911371867411]
  We show that SquareCB.Comb achieves a minimax optimal regret bound of $O(sqrtm A T log |mathcalF|)$, where $A$ is the number of arms, $m$ is the maximum number of arms in an action, and $T$ is the time horizon.<n>In the realizable setting, this bound matches the state-of-the-art regret guarantees achieved by policy search-based algorithms.
  arXiv  Detail & Related papers  (2026-07-15T10:28:05Z)
• Batched Stochastic Matching Bandits [43.651070266360954]
  We introduce a novel bandit framework for matching based on the Multi-nomial Logit (MNL) choice model.<n>In our setting, $N$ agents on one side are assigned to $K$ arms on the other side, where each armally selects an agent from its assigned pool according to an unknown preference.<n>The objective is to minimize regret by maximizing the cumulative revenue from successful matches across all agents.
  arXiv  Detail & Related papers  (2025-09-04T13:16:32Z)
• Continuous K-Max Bandits [54.21533414838677]
  We study the $K$-Max multi-armed bandits problem with continuous outcome distributions and weak value-index feedback.<n>This setting captures critical applications in recommendation systems, distributed computing, server scheduling, etc.<n>Our key contribution is the computationally efficient algorithm DCK-UCB, which combines adaptive discretization with bias-corrected confidence bounds.
  arXiv  Detail & Related papers  (2025-02-19T06:37:37Z)
• Adaptively Learning to Select-Rank in Online Platforms [34.258659206323664]
  This research addresses the challenge of adaptively ranking items from a candidate pool for heterogeneous users. We develop a user response model that considers diverse user preferences and the varying effects of item positions. Experiments conducted on both simulated and real-world datasets demonstrate our algorithm outperforms the baseline.
  arXiv  Detail & Related papers  (2024-06-07T15:33:48Z)
• Cost Aware Best Arm Identification [13.380383930882784]
  We call it emphCost Aware Best Arm Identification (CABAI) We propose a simple algorithm called emphChernoff Overlap (CO), based on a square-root rule. Our results show that (i.e. ignoring the heterogeneous action cost results in sub-optimality in practice, and (ii.) simple algorithms can deliver near-optimal performance over a wide range of problems.
  arXiv  Detail & Related papers  (2024-02-26T16:27:08Z)
• Misalignment, Learning, and Ranking: Harnessing Users Limited Attention [16.74322664734553]
  We study the design of online algorithms that obtain vanishing regret against optimal benchmarks. We show how standard algorithms for adversarial online linear optimization can be used to obtain a payoff-time algorithm with $O(sqrtT)$ regret.
  arXiv  Detail & Related papers  (2024-02-21T18:52:20Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• Incentivizing Combinatorial Bandit Exploration [87.08827496301839]
  Consider a bandit algorithm that recommends actions to self-interested users in a recommendation system. Users are free to choose other actions and need to be incentivized to follow the algorithm's recommendations. While the users prefer to exploit, the algorithm can incentivize them to explore by leveraging the information collected from the previous users.
  arXiv  Detail & Related papers  (2022-06-01T13:46:25Z)
• Contextual Combinatorial Bandits with Changing Action Sets via Gaussian Processes [8.919345630832366]
  We consider a contextual bandit problem with a action set and time-varying base arm availability.<n>We propose an algorithm called Optimistic Combinatorial Learning and Optimization with Kernel Upper Confidence Bounds (O'CLOK-UCB)<n>To dramatically speed up the algorithm, we also propose a variant of O'CLOK-UCB that uses sparse GPs.
  arXiv  Detail & Related papers  (2021-10-05T18:02:10Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
  arXiv  Detail & Related papers  (2021-01-20T04:29:18Z)
• SetRank: A Setwise Bayesian Approach for Collaborative Ranking from Implicit Feedback [50.13745601531148]
  We propose a novel setwise Bayesian approach for collaborative ranking, namely SetRank, to accommodate the characteristics of implicit feedback in recommender system. Specifically, SetRank aims at maximizing the posterior probability of novel setwise preference comparisons. We also present the theoretical analysis of SetRank to show that the bound of excess risk can be proportional to $sqrtM/N$.
  arXiv  Detail & Related papers  (2020-02-23T06:40:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.