Learning in a changing world: Restless multiarmed bandit with unknown dynamics

Haoyang Liu*, Keqin Liu, Qing Zhao

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

104 Citations (Scopus)

Abstract

We consider the restless multiarmed bandit problem with unknown dynamics in which a player chooses one 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 arm is the most rewarding and always plays the best arm. We construct a policy with an interleaving exploration and exploitation epoch structure that achieves a regret with 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.

Original languageEnglish
Article number6362216
Pages (from-to)1902-1916
Number of pages15
JournalIEEE Transactions on Information Theory
Volume59
Issue number3
DOIs
Publication statusPublished - 2013

Keywords

  • Distributed learning
  • online learning
  • regret
  • restless multiarmed bandit (RMAB)

Fingerprint

Dive into the research topics of 'Learning in a changing world: Restless multiarmed bandit with unknown dynamics'. Together they form a unique fingerprint.

Cite this