Search papers, labs, and topics across Lattice.
This paper extends the Dependent Click Model (DCM) Bandits framework to a multiplayer context, addressing the complexities of asymmetric information where agents can observe multiple clicks on a shared ranked list. The authors establish sublinear regret guarantees in scenarios characterized by action and reward asymmetries, while also demonstrating that the termination ranking can remain unknown without compromising performance. Experimental results underscore the importance of feedback structure, revealing that full versus first-click feedback significantly influences exploration strategies and regret minimization.
Asymmetric feedback structures can dramatically enhance performance in multiplayer bandit settings, challenging conventional wisdom about click models.
In this work, we extend the Dependent Click Model (DCM) Bandits to a multiplayer information-asymmetric setting, where multiple agents interact with a shared ranked list and may observe multiple clicks per session, introducing new challenges for selection strategies. We study asymmetry in (1) actions and (2) rewards, providing sublinear regret guarantees for three settings where at least one asymmetry is present. Establishing matching information-theoretic lower bounds for these settings is left as an open problem. We further show that for small termination probabilities, the termination ranking need not be known, improving on prior single-agent results. Experiments confirm that our algorithms perform well across asymmetric environments and highlight the critical role of feedback structure, specifically the distinction between full versus first-click feedback, in coordinating exploration and minimizing regret.
