Bandit Learning in Matching: Unknown Preferences On Both Sides

Thank you for your feedback. If you have any further concerns about the justifications and simulations, please let us know, and we are happy to provide further clarification.

W1. We think it is rational for the players to adopt the algorithm we proposed, as it helps them match with their optimal stable pairs with low regret. We further specify the rationale for applying our algorithm from the following aspects.

(1) The choice of the ETC framework. Unlike traditional bandit problems, in matching bandits, players compete for arms and may encounter conflicts resulting in zero rewards. If players opt for UCB-type or TS-type strategies, they are likely to frequently encounter conflicts, making it difficult to obtain useful samples for learning their preferences and updating the UCB estimators. Consequently, converging to the optimal stable matching becomes more challenging, leading to potentially much higher regret. For instance, in [Liu et. al, 2021], they illustrate an example where even the centralized UCB can not achieve sub-linear player optimal regret. Thus, it may not be rational for them to adopt such strategies. While random exploration may not perfectly align with the preferences of practical players, it serves as a useful and efficient method for both players and arms to gather sufficient samples for initially estimating their preferences and avoid conflicts.

(2) The incentive in the communication process. It is worth noting that it is not enough for a single player to learn her own preferences. The approach to player-optimal stable matching requires each participant to learn her own preferences and coordinate with each other. Communication is employed to facilitate this coordination and find a stable matching. Without the communication process, players may encounter conflicts, receive zero rewards, and fail to match with their optimal stable pairs. Therefore, the communication process actually helps the players match with their optimal stable arms effectively and with minimal cost.

(3) The assumptions on strategies. We should emphasize that sample-efficient strategies include many different kinds of policies applicable in various real-world scenarios. Our assumption that arms adopt sample-efficient strategies is easily satisfied in reality. For instance, our assumption covers scenarios where some arms use the empirical mean estimator to choose which invitation to accept, while other players use the UCB estimator to select candidates.

Regarding player-side strategies, it is a common assumption in the literature of decentralized bandit algorithm design that all players apply the same algorithm[Sankararaman et al., 2021][Liu et al., 2021][Kong and Li][Pokharel and Das, 2023][Zhang et al., 2022]. This assumption also captures the decentralized property, wherein all players lack global information before interactions. If we design different algorithms for different players, we would need to specify which set of players should apply which algorithms, and this would require global information or communication beforehand.

W2. More simulations. Due to the time limit in the rebuttal period, we have added two cases of simulations to compare our algorithm's performance with the algorithm proposed in [Pokharel and Das, 2023], and we will incorporate more cases in our revision. Figures and simulation details are shown in the supplementary materials. Moreover, several comments are provided below to compare the two algorithms.

(1) Theoretical comments: The algorithm PCA-UCB is an extension of algorithm CA-UCB while CA-UCB only achieves a $O(\log ^2 T)$ regret bound compared with the player pessimal regret, even in the one-sided setting. Moreover, [Pokharel and Das 2023] make strong but not so realistic assumptions, such as the observation of the winning players (discussed in Section 2).

(2) Simulation performance: From the figures, we can conclude that round-robin ETC outperforms PCA-UCB in both cases. Additionally, the results of round-robin ETC exhibit greater stability than those of PCA-UCB. The reason why PCA-UCB performs unstably and fails to obtain sublinear results may be as follows:

Firstly, in different runs of simulations, PCA-UCB may converge to different stable matchings instead of consistently converging to the player-optimal stable matching. This variability in convergence could be a significant challenge, as the player-optimal stable matching is more desirable for players. Furthermore, as we stated, in [Liu et al., 2021], they illustrate an example where even the centralized UCB cannot achieve sub-linear player-optimal regret.

Secondly, when applying PCA-UCB, players adopt a UCB-type method to choose arms, resulting in insufficient samples for arms to learn their preferences. Consequently, arms may provide inaccurate feedback in the two-sided setting, potentially leading to unstable matching or an extended time to convergence.

Thank you for your feedback. If you have any further concerns, please let us know, and we are happy to provide further clarification.

W1. Known $D$. $D$ is merely an upper bound assumption and only reveals the comparative level between the arm side and player side, rather than providing a detailed value of the minimal gap. In real-world applications, players can estimate $D$ using available information. Moreover, we believe that preference learning is often easier for arms than for players ($D\le 1$), as arms typically have access to more information to help estimate their preferences. For example, companies (arms) often have access to workers' resumes to assist in estimating their preferences. Alternatively, players can simply assume a large value for $D$ when applying our algorithm.

W2. Technical novelty. The main similarity between our algorithm and the proposed algorithms in [Kong and Li, 2023][Zhang et al., 2022] lies in the ETC framework, which is also commonly employed in the design of bandit algorithms. Furthermore, we highlight several key differences from two aspects below, demonstrating our technical novelty in the meantime.

(1) Different settings. The algorithms you mentioned all consider and apply solely to the one-sided setting, whereas ours is designed for the two-sided setting. In our work, we introduce and further specify the two-sided model, considering rational strategies from the arm side. Conditional on the newly proposed setting, we introduce our algorithm to study convergence to stable matching. Additionally, in [Kong and Li, 2023], there is an assumption of observing all winning players, which is a strong but impractical assumption (discussed in Section 2).

(2)Algorithm Designs and Theoretical Analysis. The algorithms in [Kong and Li, 2023][Zhang et al., 2022] focus solely on the exploration and exploitation tradeoff for the player side, while our designed algorithm needs to coordinate players against the unreliable feedback from the arm side simultaneously. The theoretical analysis methods also differ. For instance, when considering the two-sided setting, a new method for analyzing the correctness of arms' feedback is necessary. In our paper, we propose lemmas to demonstrate that as long as players have confidence in the estimations of arm utilities, the arms will provide precise feedback with high probability. Different analyses for the player side, such as the analysis of deliberate conflict, are also presented in our paper.

Lastly, we have summarized the relaxed assumptions compared with [Kong and Li, 2023] and the improved regret bound compared with [Zhang et al., 2022] in Table 1.

W3. The assumption of $N\le K$. Since our paper focuses on the extended setting of two-sided unknown preferences in matching bandits, we adhere to the commonly used assumption of $N \leq K$ in matching bandit literature. Additionally, as you mentioned, previous works assume $N \leq K$ when considering the player-unknown setting to ensure each player has a chance to be matched. In the context of the two-sided unknown setting, the corresponding assumption of $N=K$ is more natural to provide every participant with an opportunity to be matched. Our assumption of $N \leq K$ encompasses this condition.

W4. Rational on the both sides. The reason why we focus on the player-optimal stable matching is as follows: In the two-sided setting, players proactively propose to arms, and arms can only decide whether to accept the players. From our perspective in this scenario, the arms play a role analogous to the agents being proposed to in the Gale-Shapley algorithm, while players serve as the proposer side. The rationale behind considering player-optimal stable matching is to explore whether similar results to the Gale-Shapley algorithm (specifically, the convergence to the optimal stable matching for the proposing side) are applicable in the two-sided unknown setting. We believe that optimality may be influenced more by the proposing dynamics than by the unknown preferences. Furthermore, in our paper, the definition of our proposed sample-efficient strategies encompasses various rational strategies without imposing many restrictions. We have also mentioned the potential strategy competition for optimality between the two sides as a noteworthy direction for future research.

W5. Presentations. we have already polish our presentation in the revision.

[Kong and Li, 2023] Fang Kong and Shuai Li. Player-optimal stable regret for bandit learning in matching markets. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.1512–1522. SIAM, 2023 [Zhang et al., 2022] Yirui Zhang, Siwei Wang, and Zhixuan Fang. Matching in multi-arm bandit with collision. Advances in Neural Information Processing Systems, 35:9552–9563, 2022.

Thank you for your feedback. If you have further concerns about the presentation, please let us know, and we would be delighted to incorporate your additional advice to help us polish our presentation in our revision.

Weaknesses: The structure and the presentation: We have already reorganized the algorithm modules and polished the writing in the revision.

Questions: Thanks for pointing it out, and we have already added it in our revision. We also emphasize that $R$ is usually a constant no larger than $16$, given that commonly used methods such as UCB and empirical mean are both sample-efficient strategies that satisfy $R=16$.

Thank you for your feedback. If you have further concerns about the model and the insights, please let us know, and we would be delighted to incorporate your additional advice to help us add a discussion part in our revision.

W1. Related works. Thank you for pointing it out, and we have already corrected our presentation in our revision. However, we want to emphasize that our paper considers the two-sided setting from a substantially different perspective than the work of Jagadeesan et al. (JACM, 2023), and works addressing two-sided unknown preferences in matching bandits remain scarce.

Jagadeesan et al. investigate matching markets using the stochastic contextual bandit model, where, at each round, the platform selects a market outcome with the goal of minimizing cumulative instability. In brief, Jagadeesan et al. focus on the strategy of the central platform, which can directly determine the matching outcomes.

In our setting, we consider the strategy of the participants. Every participant on both sides acts individually, and the collective actions of all participants jointly determine the matching result. Minor differences, such as the existence of transfers, also vary.

W2&Q1. Model: A practical case as mentioned in the paper of [Sankararaman et al. 2021] is that of scheduling jobs to servers in an online marketplace, e.g., crowd sourcing platforms (Upwork and TaskRabbit), question answering platforms (Quora, Stack Overflow)[Shah et al., 2020]. In these marketplaces, rewards are often stochastic and can only be obtained upon completion. Furthermore, given the frequent and repeated interactions, these platforms aim to optimize cumulative rewards over an extended time horizon, solving thousands of instances every hour.

It is true that those platforms may provide recommendations. However, the workers still act individually and independently, capturing the decentralized setting; that is, there is no central communicator that enable players to coordinate their actions directly with each other. Furthermore, due to privacy concerns, workers may choose not to disclose their received rewards to the centralized platform [Rees-Jones and Skowronek, 2018]. For scalability concern, decentralized solutions are also preferred [Larsson, 2018]. Indeed, most of the related work mentioned in our paper addresses matching bandits from a decentralized perspective.

W3&Q2. Insight: Based on classical results in the matching market, the optimal matching for the proposing side can be obtained using the Gale-Shapley algorithm. The insight arises from our curiosity about whether this result can still hold in a two-sided unknown setting. By designing a specific algorithm and providing rigorous analysis, we find out that the goal is attainable, i.e. the market converges to that optimal stable matching at a logarithmic rate. Furthermore, the algorithm design and theoretical analysis methods themselves may also serve as a preliminary step for future studies in the two-sided matching bandits.

[Sankararaman et al. 2021] Sankararaman, Abishek, Soumya Basu, and Karthik Abinav Sankararaman. "Dominate or delete: Decentralized competing bandits in serial dictatorship." International Conference on Artificial Intelligence and Statistics. PMLR, 2021.

[Shah et al., 2020] Shah, V., Gulikers, L., Massouli´e, L., and Vojnovi´c, M. (2020). Adaptive matching for expert systems with uncertain task types. Opera- tions Research.

[Larsson, 2018] Larsson, S. (2018). Law, society and digital platforms: Normative aspects of large-scale data-driven tech companies. In The RCSL-SDJ Lis- bon Meeting 2018” Law and Citizenship Beyond The States”.

[Rees-Jones and Skowronek, 2018] Rees-Jones, A. and Skowronek, S. (2018). An experimental investigation of preference misrepresentation in the residency match. Proceedings of the National Academy of Sciences, 115(45):11471–11476