Learning in a Changing World: Restless Multiarmed Bandit With Unknown Dynamics

DOI10.1109/TIT.2012.2230215zbMATH Open1364.91036arXiv1011.4969MaRDI QIDQ2989388FDOQ2989388

Authors: Haoyang Liu, Keqin Liu, Qing Zhao 

Publication date: 8 June 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We consider the restless multi-armed bandit (RMAB) problem with unknown dynamics in which a player chooses M out of N arms to play at each time. The reward state of each arm transits according to an unknown Markovian rule when it is played and evolves according to an arbitrary unknown random process when it is passive. The performance of an arm selection policy is measured by regret, defined as the reward loss with respect to the case where the player knows which M arms are the most rewarding and always plays the M best arms. We construct a policy with an interleaving exploration and exploitation epoch structure that achieves a regret with logarithmic order when arbitrary (but nontrivial) bounds on certain system parameters are known. When no knowledge about the system is available, we show that the proposed policy achieves a regret arbitrarily close to the logarithmic order. We further extend the problem to a decentralized setting where multiple distributed players share the arms without information exchange. Under both an exogenous restless model and an endogenous restless model, we show that a decentralized extension of the proposed policy preserves the logarithmic regret order as in the centralized setting. The results apply to adaptive learning in various dynamic systems and communication networks, as well as financial investment.

Full work available at URL: https://arxiv.org/abs/1011.4969

Mathematics Subject Classification ID

Applications of game theory (91A80) Rationality and learning in game theory (91A26) Probabilistic games; gambling (91A60)

Cited In (5)

• Game of Thrones: Fully Distributed Learning for Multiplayer Bandits
• On the value of learning for Bernoulli bandits with unknown parameters
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Restless Bandit Model for Resource Allocation, Competition, and Reservation

This page was built for publication: Learning in a Changing World: Restless Multiarmed Bandit With Unknown Dynamics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989388)