Learning in A Changing World: Restless Multi-Armed Bandit with Unknown Dynamics

Details Learning in A Changing World: Restless Multi-Armed Bandit with Unknown Dynamics Learning in A Changing World: Restless Multi-Armed Bandit with Unknown Dynamics

2010-11-22

arxiv.org/abs/1011.4969v2

Mathematics

Optimization and Control

33 pages, 5 figures, submitted to IEEE Transactions on Information Theory, 2011

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Learning in A Changing World: Restless Multi-Armed Bandit with Unknown Dynamics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Learning in A Changing World: Restless Multi-Armed Bandit with Unknown Dynamics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Learning in A Changing World: Restless Multi-Armed Bandit with Unknown Dynamics will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-586598