Combinatorial Allocation Bandits with Nonlinear Arm Utility
This work addresses the problem of participant dissatisfaction and churn in matching platforms, which is crucial for platform profitability, by introducing a new objective function and online learning framework.
The paper introduces Combinatorial Allocation Bandits (CAB) to address the issue of concentrated matches on popular participants in matching platforms, which can lead to dissatisfaction and churn. The goal is to maximize "arm satisfaction" rather than just the number of matches. The authors propose UCB and TS algorithms for CAB, achieving approximate regret upper bounds that match existing lower bounds in a special case.
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.