Thompson Sampling for Bandit Learning in Matching Markets

1 Introduction

The model of matching markets has been studied for several decades [Gale and Shapley, 1962; Roth and Xing, 1997; Haeringer and Wooders, 2011]. It has a wide range of applications including labor employment [Roth, 1984], house allocation [Abdulkadiro˘glu and S¨onmez, 1999], and college admission [Epple et al., 2006; Fu, 2014]. Typically there are two sides of players, such as employers and workers in the labor market, and each player of one side has a preference ranking over players on the other side. Stability is a key concept in matching markets, which ensures market participants have no incentive to abandon the current partner [Gale and Shapley, 1962; Roth and Sotomayor, 1992]. Many researchers study how to find a stable matching in the markets [Gale and Shapley, 1962; Roth and Sotomayor,

∗Corresponding author. The full version is available at http:// arxiv.org/abs/2204.12048.

1992]. However, most of them assume the full preferences of players are known a priori, which is not realistic in many real-world applications. For example, the demand-side players in online matching markets (such as employers in UpWork or Mechanical Turk) are likely to be uncertain about the qualities of supply-side players (such as workers). Many such online platforms usually have matching processes happen iteratively, which allows the participating players to adaptively learn their unknown preferences [Liu et al., 2020; Liu et al., 2021].

Multi-armed bandits (MAB) is a common approach to modeling this type of learning process [Auer et al., 2002; Lattimore and Szepesv´ari, 2020]. The most basic framework considers a single player and K arms, where the player does not have prior knowledge over arms and will learn it through iteratively collected rewards. The objective of the player is to maximize the cumulative reward over a specified horizon, or equivalently minimize the cumulative regret, which is defined as the difference between the cumulative reward of the optimal arm and that of the chosen arms. To achieve this goal, the player needs to make a trade-off between exploration and exploitation: the former tries arms that have not been observed enough times to get potential higher rewards, and the latter focuses on arms with the highest observed rewards so far to maintain high profits.

There are many types of strategies to balance such tradeoffs with theoretical guarantees, among which explore-thencommit (ETC), upper confidence bound (UCB), and Thompson sampling (TS) are widely adopted in the literature [Lattimore and Szepesv´ari, 2020]. The TS algorithm was introduced in the 1930s [Thompson, 1933] but has not been theoretically proven until the 2010s [Kaufmann et al., 2012; Agrawal and Goyal, 2012; Agrawal and Goyal, 2013]. Algorithms of this type form a competitive family in the bandit area because of many advantages such as easier implementations and better practical performances. Though ETC and UCB-type algorithms have solved many bandit problems, there are still accompanying works trying to analyze TS [Cheung et al., 2019; Kong et al., 2021].

Das and Kamenica [2005] first introduce the bandit learning problem in two-sided matching markets and show the empirical performances of algorithms via simulation tests. Liu et al. [2020] later study a refinement of the problem and give the first algorithm with theoretical guarantees. They propose both ETC and UCB-type algorithms with upper bounds on the stable regret, which is defined as the difference between the cumulative reward of a stable matching 1 and the cumulative reward collected. Both algorithms adopt a central platform to collect players' preferences and assign allocations to participants. Since such platforms do not always exist in realworld applications, the following works extend to the decentralized setting [Liu et al., 2021; Sankararaman et al., 2021; Basu et al., 2021]. All these works still focus on ETC and UCB-type algorithms and do not consider TS.

In a standard TS analysis, one needs to bound the inaccurate estimations for the optimal arms due to the randomness caused by the posterior samples, which is easily controlled because eventually the optimal arms can be observed enough times. However, this property may not hold anymore in matching markets since the observations are not simply decided by the number of selections and can be blocked if the selected arm rejects this player. Such a difficulty does not exist in UCB-type algorithms since it mainly needs to bound inaccuracies for sub-optimal arms, and ETC-type algorithms can control the blockings easily in the design.

In this work, we present the first TS-type algorithm for decentralized matching markets. For the stable regret analysis, though the observations might be blocked, we prove that its success probabilities could be bounded by separately analyzing the influence of other players in a fine division of events with a different number of selections on the optimal stable arms. The result guarantees the regret of TS with an order of O(log2 T/∆2 ), where T is the horizon and ∆ is the minimum preference gap. A series of experiments are conducted to show that the practical performances of the TS-type algorithm are better than other baselines.

Related work. The MAB problem has been studied for many decades, which captures the learning process of a single player in an unknown environment. The study on stochastic MAB is an important line of works where the reward of arms are drawn from fixed distributions. ϵ-greedy, ETC, UCB and TS are all classical algorithms for this setting and are widely followed in the literature [Lattimore and Szepesv´ari, 2020].

Motivated by real applications including cognitive radio where multiple players compete and cooperate in the unknown environment, the problem extends to multi-player MAB. These works [Liu and Zhao, 2010; Rosenski et al., 2016; Bistritz and Leshem, 2018] mainly consider the case where a player receives no reward if it conflicts with others by selecting the same arm and measure algorithms performances by the collective cumulative regret of all players.

The model of combinatorial dueling bandits [Chen et al., 2020] can also be regarded as a multi-player problem, where the preferences of players are defined on pairs of arms. They study a pure exploration problem for this model with the objective to find the best matching after a specified period.

The two-sided matching market problem is different from previous multi-player MAB by considering arms' preferences [Gale and Shapley, 1962; Roth and Xing, 1997]. In this problem, not only do players have arbitrary preferences over arms, arms also have arbitrary preferences over players. When multiple players collide at the same arm, the player preferred most by this arm will receive the corresponding reward while others receive no feedback.

1 Different stable matchings give different kinds of stable regrets.

The bandit learning problem in two-sided matching markets was first introduced by Das and Kamenica [2005]. They assume the preferences of both sides are unknown and study the empirical performances of ϵ-greedy in a special market where all participants on one side share the same preferences. Later, Liu et al. [2020] study a variant of the problem by considering one-side unknown preferences. They propose both ETC and UCB-type algorithms and show the convergence analysis of the stable regret. Both algorithms adopt Gale-Shapley (GS) [Gale and Shapley, 1962] to assign allocations for players. However, in real applications, players usually prefer to independently make decisions. Liu et al. [2020] then propose Decentralized ETC in the decentralized setting, which lets players to explore arms for a fixed number of rounds. However, the exploration budget H needs to depend on the preference gap, which is usually not known beforehand. Sankararaman et al. [2021] and Basu et al. [2021] successively study the decentralized setting to remove this assumption but under special assumptions to guarantee a unique stable matching. For general markets, Basu et al. [2021] propose the phasedETC algorithm and Liu et al. [2021] propose a UCB-type algorithm to avoid conflicts among players and minimize the stable regret. Dai and Jordan [2021] also study to learn players' unknown preferences in a decentralized matching market. However, their objective is to estimate the unknown preferences using a statistical model but involves no cumulative regret. To the best of our knowledge, we are the first to study the TS-type algorithm for two-sided matching markets.

2 Setting

There are N players and K arms in the market. The player set is denoted by N = {p1, . . . , pN} and the arm set is denoted by K = {a1, . . . , aK}. To ensure each player can be matched with an arm, we assume N ≤ K as [Liu et al., 2020; Liu et al., 2021; Basu et al., 2021; Sankararaman et al., 2021].

For each player pi, its preference for arm aj is quantified by an unknown value µi,j ∈ [0, 1]. For two different arms aj and aj ′ , µi,j > µi,j ′ implies that player pi truly prefers arm aj to aj ′ . Similarly, each arm aj has preferences over players. Let πj,i to represent the preference value of arm aj for player pi. For two different players pi and pi′ , πj,i > πj,i′ implies that arm aj prefers player pi to pi′ . The ranking for each arm aj's preferences (πj,i)i∈[N] is assumed to be known since it usually can be estimated by some known utilities such as the payments given by employers in the labor market.

At each round t = 1, 2, . . ., each player pi ∈ N attempts to pull an arm Ai(t) ∈ K. Let A(t) = (Ai(t))i∈[N]. When multiple players attempt to pull the same arm, there will be a conflict and only the player preferred most by this arm is accepted. If a player pi wins the conflict, it will receive a random reward Xi,Ai(t)(t) ∈ [0, 1] with expectation µi,Ai(t). Other players pi′ who fail the conflict are unmatched in this round and receive Xi′ ,Ai′ (t)(t) = 0. Following the observations in the scenario of the labor market and college admission where the arm side (e.g., workers or colleges) usually announces the successfully matched players (e.g., employers or students), we assume the successfully matched player for each arm is public at the end of the round as in previous work [Liu et al., 2021].

To measure the status of the market, stable matching [Gale and Shapley, 1962] is introduced to define an equilibria. A stable matching is a one-to-one mapping from players to arms without a pair of player and arm such that they both prefer being matched with each other over the current partner. With the true preference rankings of players and arms, there may be more than one stable matching. Denote mi as player pi's least favorite arm among matched arms from all stable matchings. The objective is to find a stable matching between players and arms and minimize the cumulative stable regret for each player pi [Liu et al., 2020; Liu et al., 2021; Basu et al., 2021; Sankararaman et al., 2021], which is defined as

where the expectation is taken over the randomness in the reward payoffs and the algorithm.

3 Algorithm

In this section, we introduce our TS-type algorithm, referred to as conflict-avoiding TS (CA-TS, Algorithm 1), for twosided matching markets. Some design ideas are motivated by Liu et al. [2021] and the main difference is that CA-TS uses parameters sampled from posterior distributions as estimations for preferences to select arms. However, this raises new analysis difficulties since CA-TS additionally requires accurate estimations for 'optimal arms' to ensure a stable matching, which will be made clearer later in Section 4.

The CA-TS algorithm takes the player set N and arm set K as input (line 1). For each player pi and arm aj, the algorithm maintains a Beta distribution Beta(ai,j, bi,j) for the preference value. In the beginning, this distribution is initialized to Beta(1, 1), the uniform distribution on [0, 1] (line 2). It will be later updated based on observed feedback and tend to concentrate on the real value µi,j . In round t, the algorithm samples an index θi,j(t) from Beta(ai,j , bi,j) to represent the current estimation (line 5).

One may consider letting each player pi follow independent TS strategies, namely choose Ai(t) ∈ argmaxj∈[K] θi,j(t). A simple example shows that frequent conflicts would happen under this strategy. Suppose there are 2 players and 2 arms, and µi,1 = maxj∈[K] µi,j for each pi. Then at each round t, θi,1(t) = maxj∈[K] θi,j(t) holds for each pi with at least constant probability. The reason is that if enough observations are collected, then the sampled indices approach the real preference value and θi,1(t) would be the largest; otherwise, the Beta distributions tend to be uniform and θi,1(t) would still be the largest with constant probability. Thus both players attempt to pull a1 with constant probability at each round. However, a1 only accepts one player and the other one will be rejected and receive no feedback. The stable regret of the latter player is thus of order O(T).

Algorithm 1 Conflict-Avoiding TS (CA-TS)

To avoid frequent conflicts in the above case, we construct a plausible set for each player to exclude arms that may reject it (line 8). Recall that the successfully matched players and the preference rankings of arms are known. If arm aj accepts a player pi′ but prefers pi more, pi will not be rejected by aj when the same set of players attempt to pull aj. Following this observation, the plausible set for pi at time t is constructed to contain arms who accept a player less preferred than pi at t - 1 (line 8). Player pi then selects the arm with the highest index in the plausible set (line 9). Here we use ¯ Ai(t) to represent the arm successfully pulled by pi at t. If pi fails the conflict, then ¯ Ai(t) = -1.

However, players can still simultaneously pull same arms. Consider an example with 2 players and 2 arms. Both players have µi,1 = argmaxj∈[K] µi,j, arm a1 prefers p1 to p2 and arm a2 prefers p2 to p1. It is possible that both players attempt to pull a1 at t = 1. Then p2 is rejected and its plausible set only contains a2 at t = 2. For player p1, its plausible set is still {a1, a2}, and its Beta distribution for arm a2 is still uniform. Thus with constant probability, θ1,2(t) > θ1,1(t) and both players attempt to pull arm a2 at time t = 2. In this case, player p1 will then be rejected. The same analysis shows that both players can always pull the same arm and be rejected in turn. Thus the stable regrets of these two are both of the order O(T).

A random delay mechanism is further introduced to keep the effectiveness of the plausible set and avoid such rejections. The intuition is that if all players except pi follow the last-round choice, then pi will not be rejected by selecting arms in the plausible set. To be specific, each player first draws a Bernoulli random variable Di(t) with expectation λ (line 6), which is a hyper-parameter. If Di(t) = 0, pi still attempts the armwith the largest index in the plausible set (line 7-9); otherwise, it follows the last-round choice (line 11).

When all players decide which arm to pull in this round, arms will determine which player to accept according to their rankings. If player pi wins the conflict and successfully pulls arm Ai(t), the algorithm marks ¯ Ai(t) as Ai(t) and updates the corresponding Beta distribution (line 13-19).

4 Theoretical Results

In this section, we provide the theoretical result of CA-TS. The corresponding gaps are defined to measure the performance of the algorithm.

Definition 1. (Gaps) For each player pi ∈ N, denote ∆i,max = µi,mi as the maximum stable regret that player pi needs to pay in unstable matchings. For any pair of arms aj and aj ′ , define

as the reward difference between arm aj and aj ′ for player pi. Let ∆=mini,j,j ′ :µi,j̸=µi,j′ |µi,j -µi,j ′ |.

Theorem 1. Let ρ = λN-1 (1 - λ). Following Algorithm 1, the stable regret of each player pi satisfies

for any ε such that ∆ - 2ε > 0, where C is a universal constant.

Due to the space limit, we provide the proof sketch as well as the full proof in the Appendix. In addition to Beta priors shown in Algorithm 1, we also analyze the CA-TS algorithm with Gaussian priors for 1-subgaussian rewards, which achieves the same order of regret upper bound as Theorem 1. For completeness, we provide the full algorithm and analysis in the Appendix.

4.1 Discussions

Hardness. The TS-type algorithm faces new challenge for analysis in the setting of matching markets. Note in this setting, once a player wrongly estimate arms, both this player and others in the market could suffer non-negative stable regret. In the following, we take a player pi and two arms aj, aj ′ with µi,j ′ > µi,j for further analysis. Specifically, we need to bound the number of times when pi incorrectly attempts aj instead of aj ′ . If the attempt is due to inaccurate estimations of µi,j , then it can be easily guaranteed since with more selections, µi,j would be finally observed enough times and estimated well. However, if µi,j has already been estimated accurately, the analysis gets more complicated.

For this important part, we first investigate what properties of θi,j ′ are implied by the event. We show that the sample θi,j ′ must be inaccurate and once an accurate sample of it is drawn, pi will select aj ′ . In standard analysis of MAB, such cases can be guaranteed since when θi,j ′ is not accurate, the variance of the posterior distribution would push it to generate a larger sample in some round and the observations can thus be obtained. But in matching markets, even when an accurate sample for µi,j ′ is drawn, the observation may still be unavailable. To deal with this case, at each time with a good sample of µi,j ′ , we analyze the influence of all other players and compute the exact probability of obtaining an observation. Based on this probability, we construct a new counter to estimate the number of observations on µi,j ′ . The total horizon can then have a fine division of slices based on this counter and within each slice, the posterior distribution of µi,j ′ has some common properties and we are able to bound the number of rounds to wait for a good event of being matched with arm aj ′ .

Note this difficulty does not need to be dealt with by UCB and ETC. In UCB, due to the monotonicity between UCB index and real parameter, inaccurate estimations of µi,j ′ would not contribute to the regret, while ETC forces players to collect enough observations on every arm without considering other participants' influence.

Regret bound. Our CA-TS is the first TS-type algorithm for general decentralized matching markets. Two comparable algorithms in the same setting with regret guarantees are CAUCB [Liu et al., 2021] and PhasedETC [Basu et al., 2021]. The former has the same main order of regret upper bound as ours. The latter, though its upper bound has better dependence on T (of order O(log1+ε T + 2(1/∆2 )1/ε ), ε > 0 is a hyper-parameter), suffers from the problem of cold-start and only works for a huge horizon T = Ω (exp (N/∆2 )). Compared with CA-UCB, our regret upper bound has an additional constant term 1/ε6 . This term comes from the special nature of TS as discussed above and also appears in many other TS-based works [Agrawal and Goyal, 2013; Wang and Chen, 2018; Perrault et al., 2020; Kong et al., 2021]. As stated in the theorem, if we let ε take value of ∆/3, then this term would become 729/∆6 , which is a constant relative to logT. It is not known whether such a term is unavoidable and we would leave this as future work. It is worth noting that the additional constant term does not imply bad practical performances. As shown in following Section 5, our TS-type algorithm performs better than these baselines.

Player-pessimal stable regret. In this paper, we study the player-pessimal stable regret which is defined with respect to players' least favorite stable matching. Except for basic ETC, the analyses of all existing works also focus on this type of stable regret [Liu et al., 2020; Liu et al., 2021; Sankararaman et al., 2021; Basu et al., 2021]. In the market shown in [Liu et al., 2020, Example 6], both UCB and TS cannot achieve sublinear player-optimal stable regret, compared with players' favorite stable matching. This is because once a player mistakenly ranks two arms, other players' behavior can force it to have no chance for more observations and learn a correct preference ranking for optimal stable matching. How to minimize the player-optimal stable regret in general matching markets is still an open problem.

5 Experiments

In this section, we compare the performances of our CA-TS with other related baselines in different environments 2 where all players and arms share the same preferences (Section 5.1), the minimum reward gap ∆ is varied (Section 5.2), and the market size is varied (Please see the full version for experiments in this setting). The baselines include CA-UCB [Liu et al., 2021], PhasedETC (P-ETC) [Basu et al., 2021], Decentralized ETC (D-ETC) [Liu et al., 2020] and UCB-D4 [Basu et al., 2021]. Since UCB-D4 requires the market to satisfy uniqueness consistency, we only test it in global-preference case where only unique stable matching exists (Section 5.1). The hyper-parameters of all baselines are set as their original paper with details in the Appendix.

We first report the cumulative stable regrets for all experiments. Also since the goal is to learn stable matchings and is not well reflected from cumulative regrets, we also report the cumulative market unstability, which is defined as the number of unstable matchings over T rounds, as in Liu et al. [2021]. In each market, we run all algorithms for T = 100k rounds and all results are averaged over 50 independent runs. The error bars correspond to standard errors, which are computed as standard deviations divided by √50.

2 The code is available at https://github.com/fangkongx/ TSforMatchingMarkets.

5.1 Global Preferences

In this section, we construct a market of N = 5 players and K = 5 arms with global preferences, where all players share the same preference over arms and all arms share the same preference over players. Specifically, we set µi,1 > µi,2 > µi,3 > µi,4 > µi,5 for each player pi and πj,1 > πj,2 > πj,3 > πj,4 > πj,5 for each arm aj. The preference towards the least favorite arm is set as µi,5 = 0.1 for any pi and the reward gap between any two consecutively ranked arms is set as ∆ = 0.2. In this market, the unique stable matching is {(p1, a1), (p2, a2), (p3, a3), (p4, a4), (p5, a5)}, thus the assumption of uniqueness consistency required by UCB-D4 is satisfied. The feedback Xi,j(t) for player pi on arm aj at time t is drawn independently from Bernoulli(µi,j).

We report the cumulative stable regret of each player in Figure 1 (a-e) and the cumulative market unstability for each algorithm in Figure 1 (f).

Our CA-TS pays the least stable regret on player p1, p2, p3, and p4 among all algorithms, while only pays higher regret than P-ETC on player p5. However, under P-ETC, both the market unstability and the stable regrets of other players still do not converge, which phenomenon also coincides with the theoretical result that P-ETC suffers from cold-start and only works when T is huge [Basu et al., 2021]. The reason for lower stable regret of p5 is that P-ETC avoids rejections by following allocations of the GS algorithm and p5 would suffer zero regret in this process since all other arms are better than its partner a5 in the stable matching. For other algorithms, the stable regrets are not consistent among different players since they explore differently to find a stable matching. So we look into market unstability for further analysis. As shown in Figure 1 (f), our CA-TS shows the least market unstability. By carefully choosing an appropriate hyper-parameter H representing the exploration budget, D-ETC performs slightly worse than ours. CA-UCB and UCB-D4 converge much slower and explore more to find a stable matching.

5.2 Varying Gaps for RandomPreferences

In this experiment, we test the effect of the minimum reward gap ∆ on the stable regret and market unstability. The market size is fixed with N = 5 players and K = 5 arms. The preference rankings of all players (arms) are generated as random permutations of arms (players, respectively). We set the preference value towards the least favorite arm as 0.1 for all players and test four different choices of reward gap between any two consecutively ranked arms ∆ ∈ {0.2, 0.15, 0.1, 0.05}.

Figure 2 shows the maximum cumulative stable regret among all players and the cumulative market unstability for each algorithm under different values of ∆.

Our CA-TS pays the least stable regret among algorithms under each value of ∆ and performs the most robust when ∆ is changed. The D-ETC performs second to ours when ∆ ∈ {0.2, 0.15, 0.1}. However, its regret does not converge when ∆ = 0.05, which illustrates its high dependence on the selection of H and confirms the theoretical result that H needs to depend on ∆ to guarantee good performances [Liu et al., 2020]. The CA-UCB algorithm pays higher stable regret than our CA-TS and its performances also change more drastically with different ∆. The P-ETC algorithm still suffers from cold-start and does not converge in given periods.

Similar observations can also be found from the perspective of the market unstability. As shown in Figure 2 (right), the cumulative market unstability of algorithms gets higher when ∆ is small. This is as expected since algorithms need to explore more to get accurate estimations on preference rankings and thus find the true stable matching.

One may also concern that the performances of algorithms could be worse when the preferences of all players tend to be the same since players may always attempt same arms thus leading to more conflicts. In the Appendix, we test the performances of algorithms in markets with different heterogeneity of players' preferences and find our CA-TS still shows the best and the most robust performances.

6 Conclusion

In this paper, we show the first TS-type algorithm, CA-TS, for the two-sided decentralized matching markets. Compared with previous UCB and ETC-type algorithms, the special nature of TS and the setting of matching markets bring additional analysis difficulties, since TS requires enough observations on arms in stable matchings but market participants may force a player to observe no feedback. We overcome the difficulty by bounding the success probability of observing these arms with a fine division of the horizon based on the number of previous attempts and the analysis of other players' influence. Our stable regret upper bound achieves the same order as previous UCB-type algorithms. Extensive experiments on markets with different properties are conducted to verify the practical performances of the TS-type algorithm. Compared with all baselines, our CA-TS learns stable matchings much faster and shows more robust performances.

We study a decentralized setting where players independently choose arms. An interesting future direction is to design TS-type algorithms for scenarios with more communication such as the centralized setting in Liu et al.[2020] where players can communicate with a central platform. New design ideas are needed as the requirement of TS is more restrictive than UCB. An example in the Appendix shows that if we only replace the UCB index in Liu et al. [2020] with the sampled parameters from posterior distributions as TS, players can suffer a stable regret of order O(T). This example further illustrates the difference between TS and UCB and the challenge of TS analysis in matching markets.

Acknowledgements

The corresponding author Shuai Li is supported by National Natural Science Foundation of China (62006151, 62076161). This work is sponsored by Shanghai Sailing Program.