MHNIW: A Formulated Multi-Agent Strategy to Solve High-Dimensional Multi-Arm Bandit Problem

This paper has designed an innovative method to solve the high-dimensional multi-arm bandit problems. Basic overview, this paper combines the Metropolis-Sampling method together with the Thompson Sampling methods and the algorithm is shown to be an anytime algorithm. Moreover, the unit of the size of the agents is the element-wise. In each training process, the agent will firstly communicate about the best result then do the choices after consideration which is indicated by the Metropolis-Hasting Sampling. Practically, the agents will be more willing to migrate to an arm with higher attraction so that all the agents will form a consensus of the best arm after some rounds. As a result, the cumulative regret of the mentioned algorithm is actually bounded by a logarithmic increment with respect to the gap between optimal arm and sub-optimal ones. Worth to mention, the upper bound of the cumulative regret will not present a significant increment relatively, if the aggregate number of the arms increases. As for the implementation, this paper has applied this paper's algorithm to the dataset provided by the Microsoft research which contains different sizes of data. The github source can be found at https://github.com/whyulookingat/MHNIW.