Thompson Sampling for Bandit Learning in Matching Markets
The problem of two-sided matching markets has a wide range of real-world applications and has been extensively studied in the literature. A line of recent works have focused on the problem setting where the preferences of one-side market participants are unknown \emph{a priori} and are learned by iteratively interacting with the other side of participants. All these works are based on explore-then-commit (ETC) and upper confidence bound (UCB) algorithms, two common strategies in multi-armed bandits (MAB). Thompson sampling (TS) is another popular approach, which attracts lots of attention due to its easier implementation and better empirical performances. In many problems, even when UCB and ETC-type algorithms have already been analyzed, researchers are still trying to study TS for its benefits. However, the convergence analysis of TS is much more challenging and remains open in many problem settings. In this paper, we provide the first regret analysis for TS in the new setting of iterative matching markets. Extensive experiments demonstrate the practical advantages of the TS-type algorithm over the ETC and UCB-type baselines.
Code (1)
Tasks
Multi-Armed BanditsThompson SamplingMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Two-sided Competing Matching Recommendation Markets With Quota and Complementary Preferences Constraints
In this paper, we propose a new recommendation algorithm for addressing the problem of two-sided online matching markets with complementary preferences and quota constraints, where agents' preferences are unknown a prior…
Thompson SamplingThompson sampling with the online bootstrap
Thompson sampling provides a solution to bandit problems in which new observations are allocated to arms with the posterior probability that an arm is optimal. While sometimes easy to implement and asymptotically optimal…
Thompson SamplingThe End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits
Stochastic linear bandits are a natural and simple generalisation of finite-armed bandits with numerous practical applications. Current approaches focus on generalising existing techniques for finite-armed bandits, notab…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Thompson SamplingOptimal Thompson Sampling strategies for support-aware CVaR bandits
In this paper we study a multi-arm bandit problem in which the quality of each arm is measured by the Conditional Value at Risk (CVaR) at some level alpha of the reward distribution. While existing works in this setting …
Thompson SamplingFeel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning
Thompson Sampling has been widely used for contextual bandit problems due to the flexibility of its modeling power. However, a general theory for this class of methods in the frequentist setting is still lacking. In this…
Multi-Armed Banditsregressionreinforcement-learningReinforcement Learning+2