Competing Bandits in Time Varying Matching Markets
Competing Bandits in Time Varying Matching Markets
复制标题
DOI：
10.48550/arxiv.2210.11692
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Deepan Muthirayan;C. Maheshwari;P. Khargonekar;S. Sastry
中科院分区：
文献类型：
--
作者：
Deepan Muthirayan;C. Maheshwari;P. Khargonekar;S. Sastry
研究双边非平稳匹配市场中的在线学习问题，目标是收敛到一个稳定的匹配。特别是，我们考虑了市场的一方，即武器，相对于另一方，即玩家，具有固定的一套已知偏好的设置。虽然这个问题已经被研究了当玩家有固定的但未知的偏好时，在本工作中我们研究了当玩家的偏好是时变的和未知的时如何学习的问题。我们的贡献是一种可以处理任何类型的偏好结构和变化情景的方法。我们证明了，在所提出的算法下，直到代理人的基本偏好的改变次数$L_T$为止，每个玩家都得到了一致的次线性遗憾{$\宽{\数学{O}}(L^{1/2}_TT^{1/2})$}。因此，我们证明了无论竞争如何，单代理学习的最优速率都可以达到一个恒定因子的差值。我们还讨论了该算法在变化次数不需要先验已知的情况下的扩展。
We study the problem of online learning in two-sided non-stationary matching markets, where the objective is to converge to a stable match. In particular, we consider the setting where one side of the market, the arms, has fixed known set of preferences over the other side, the players. While this problem has been studied when the players have fixed but unknown preferences, in this work we study the problem of how to learn when the preferences of the players are time varying and unknown. Our contribution is a methodology that can handle any type of preference structure and variation scenario. We show that, with the proposed algorithm, each player receives a uniform sub-linear regret of {$\widetilde{\mathcal{O}}(L^{1/2}_TT^{1/2})$} up to the number of changes in the underlying preferences of the agents, $L_T$. Therefore, we show that the optimal rates for single-agent learning can be achieved in spite of the competition up to a difference of a constant factor. We also discuss extensions of this algorithm to the case where the number of changes need not be known a priori.