Research Repository

Collision Resolution in Multi-player Bandits Without Observing Collision Information

Nisioti, Eleni and Thomos, Nikolaos and Bellalta, Boris and Jonsson, Anders (2021) Collision Resolution in Multi-player Bandits Without Observing Collision Information. In: International Conference on Machine Learning - Workshop on Reinforcement Learning Theory, 2021-07-24 - 2021-07-24.

[img]
Preview
Text
ICML2021.pdf - Accepted Version

Download (314kB) | Preview

Abstract

The absence of collision information in Multi- player Multi-armed bandits (MMABs) renders arm availabilities partially observable, impeding the design of algorithms with regret guarantees that do not allow inter-player communication. In this work, we propose a collision resolution (CR) mechanism for MMABs inspired from sequential interference mechanisms employed in communication protocols. In the general case, our collision resolution mechanism assumes that players can pull multiple arms during the exploration phase. We, thus, propose a novel MMAB model that captures this while still considering strictly bandit feedback and single-pulls during the exploitation phase. We theoretically analyze the CR mechanism using tools from information theory in order to prove the existence of an upper bound on the probability of its failure that decreases at a rate exponential in the number of players.

Item Type: Conference or Workshop Item (Paper)
Additional Information: Published proceedings: _not provided_
Divisions: Faculty of Science and Health
Faculty of Science and Health > Computer Science and Electronic Engineering, School of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 13 Dec 2021 10:59
Last Modified: 15 Jan 2022 01:39
URI: http://repository.essex.ac.uk/id/eprint/31880

Actions (login required)

View Item View Item