研究提出异构异步多玩家老虎机问题近似算法

发生了什么

据arXiv cs.LG论文，针对异构异步多玩家老虎机（MMAB）问题，现有研究多集中于同质玩家，而异构设置下最优分配计算仍为开放问题。该研究首先证明异构异步MMAB的最优分配计算是NP-hard的。随后提出贪婪算法，证明其能在多项式时间内实现最优分配的1/e近似；若按激活概率降序处理玩家，近似保证提升至1/sqrt(e)。结果为设计在线算法提供了实用的预言机基线。