在未知博弈收益的匹配市场中，通过带索引反馈学习稳定匹配策略。
Learning in Matching Games with Bandit Feedback
- 基于乐观估计的UCB算法，让匹配方自适应选择最优行动。
- 首次证明了匹配不稳定性的后悔上界为次线性且与实例无关。
- 适合研究多智能体博弈与动态匹配机制的学者参考。
我们提出一种广义双侧匹配市场的学习问题，其中参与者选择行动以与匹配对象互动。具体而言，匹配的个体之间进行初始收益矩阵未知的零和博弈，探究中心化机制能否从带索引反馈中学习均衡。采用匹配均衡作为解概念：匹配 $ \mathfrak{m} $ 与策略集 $ X $ 构成均衡，当且仅当无个体有动机偏离 $ (\mathfrak{m}, X) $。为量化候选解 $ (\mathfrak{m}, X) $ 与最优均衡 $ (\mathfrak{m}^\star, X^\star) $ 的偏离程度，引入匹配不稳定性作为学习问题的后悔度量。我们提出一种基于UCB的算法，使参与方根据对收益的乐观估计形成偏好并选择动作。分析表明，该算法具有次线性、与实例无关的后悔上界，并得到实证支持。
原文摘要 · Abstract (English)
We introduce a learning problem in a generalized two-sided matching market, where agents select actions to interact with their match. Specifically, we consider a setting in which matched agents engage in zero-sum games with initially unknown payoff matrices, and we investigate whether a centralized procedure can learn an equilibrium from bandit feedback. We adopt the solution concept of a \emph{matching equilibrium}, where a matching \( \mathfrak{m} \) and a set of agent strategies \( X \) form an equilibrium if no agent has an incentive to deviate from \( (\mathfrak{m}, X) \). To quantify deviations of a candidate solution \( (\mathfrak{m}, X) \) from the equilibrium \( (\mathfrak{m}^\star, X^\star) \), we introduce the notion of \emph{matching instability}, which serves as a regret measure for the learning problem. We propose a UCB-based algorithm in which agents form preferences and select actions according to optimistic estimates of the payoffs. Our analysis establishes a sublinear, instance-independent regret upper bound, further supported by empirical evidence.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。