PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Haoyang Liu, Keqin Liu, Qing Zhao

arXiv:1011.4969v2math.OCcs.LGmath.PR

TL;DR

The paper studies restless multi-armed bandits with unknown dynamics and develops a policy that sequences exploration and exploitation. The policy achieves logarithmic-order regret in centralized and decentralized settings, including exogenous and endogenous restless models.

  • Problem

    The paper studies the Restless Multi-Armed Bandit problem with unknown dynamics, a setting associated with computational difficulty for Markovian dynamics.

  • Method

    The policy uses a deterministic sequencing of exploration and exploitation with geometrically growing epochs.

  • Results

    The proposed policy achieves logarithmic-order regret in centralized and decentralized settings, with complete decentralization under both exogenous and endogenous restless models.

  • Takeaways & Limitations

    The decentralized extension preserves logarithmic regret while allowing multiple distributed players to share arms without centralized coordination.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper studies RMABs whose arms continue evolving while passive, creating learning and switching challenges beyond classic and rested Markovian bandits. It proposes an epoch-based exploration–exploitation policy that attains logarithmic-order regret under partial parameter knowledge and arbitrarily near-logarithmic regret without system knowledge, while using a weaker, tractable regret benchmark.

  • Problem setting: RMAB arms follow unknown Markovian dynamics when played and arbitrary unknown random processes when passive, unlike rested models where passive arms remain frozen.The setting includes both centralized and decentralized multiple-player variants.
  • Problem setting: Restless evolution requires consecutive plays to learn arm statistics, while switching creates transients and potential reward loss, so play segments and switching frequency must be controlled.These constraints create a tension between learning bad arms and limiting switching-related losses.
  • Centralized Setting: The proposed DSEE policy interleaves exploration and exploitation epochs whose lengths grow geometrically, samples every arm during exploration, and plays the largest-sample-mean arm during exploitation.The construction balances exploration with exploitation while controlling the number of arm switches.
  • Centralized Setting: With O(log t) exploration epochs and nontrivial bounds on system parameters, DSEE learns arm ranks accurately and achieves logarithmic-order regret.The policy also achieves the maximum average reward offered by the M best arms.
  • Centralized Setting: Without system knowledge, increasing exploration by an arbitrarily small order yields regret of order f(t) log t for any increasing divergent function f(t).This is arbitrarily close to logarithmic order.
  • Regret definition and scope: The paper uses weak regret against a partially informed genie because optimizing known general RMAB dynamics is P-SPACE hard, leaving stronger unknown-model guarantees open.This benchmark compares performance with knowledge of the best arm means rather than complete system dynamics.

2) Decentralized Setting:

The decentralized extension applies DSEE to multiple players that independently learn unknown restless arms without communication or synchronized global timing. Under both exogenous and endogenous restless models, it preserves logarithmic regret, with the exogenous guarantee using a stronger centralized benchmark.

  • Multiple players select arms from local observations without information exchange, and collisions occur when they choose the same arm.
  • The framework covers exogenous systems whose arms are rested when passive and endogenous systems whose passive states evolve through arbitrary unknown processes.
  • The decentralized DSEE extension achieves the same logarithmic regret order as centralized scheduling under complete decentralization.
  • Under the exogenous restless model, regret is measured against the optimal known-model policy with centralized scheduling because the system is inherently rested.
  • Unlike regenerative-cycle methods, DSEE uses a deterministic epoch structure and all observations for learning, avoiding discarded observations that can impair competing methods.

D. Applications

The paper frames unknown restless-bandit learning around selecting rewarding arms whose states evolve differently when played or passive. It identifies applications in opportunistic communication and financial investment, while establishing the proposed DSEE policy's logarithmic-regret result.

  • Applications: Opportunistic communication uses unknown fading channels, where channel selection affects energy efficiency or throughput.
  • Applications: Financial investment fits the model when a venture capitalist selects companies whose profits evolve according to investment-dependent Markov dynamics.
  • Paper scope: The paper proposes DSEE for the single-player setting and establishes logarithmic regret before extending the study to distributed players.
  • Problem formulation: Restless bandits model arms whose states follow unknown Markovian dynamics when played and arbitrary unknown processes when passive.
  • Problem formulation: Regret measures reward loss relative to knowing the best arms, and the objective is to minimize its growth rate over time.

B. DSEE with An Epoch Structure

DSEE balances learning and reward collection by interleaving exploration and exploitation epochs whose lengths grow geometrically. Under suitable parameter bounds it achieves logarithmic regret, and without system knowledge its order can approach logarithmic arbitrarily closely.

  • Consecutive play segments must be long enough to reduce transient effects but short enough to limit time spent on bad arms.
  • DSEE partitions time into interleaving exploration and exploitation epochs with geometrically growing lengths.
  • Exploration plays arms equally to learn reward statistics, while exploitation selects the arm with the largest sample mean.
  • Only logarithmically many plays are spent in exploration epochs, which is necessary for logarithmic regret order.
  • With appropriate bounds on rmax, ǫmin, and the best-arm mean gap, DSEE achieves logarithmic regret order.
  • When system knowledge is unavailable, allowing D to increase with time yields regret arbitrarily close to logarithmic order.

D. Extension to M > 1

For M > 1, DSEE keeps its exploration–exploitation structure while selecting the M arms with the largest sample means. The extension retains logarithmic-order regret under the stated model assumptions and supports decentralized multi-player analysis.

  • Centralized extension: For M > 1, DSEE preserves its basic structure while exploitation selects the M arms with the largest sample means.
  • Centralized extension: The multi-arm regret has a logarithmic-order upper bound under finite-state, irreducible, aperiodic, reversible Markov dynamics and distinct means at the Mth-best boundary.
  • Centralized extension: Choosing D for logarithmic regret requires bounds involving rmax, ǫmin, and the gap between the Mth and (M+1)th arm means.
  • Centralized extension: Without parameter knowledge, a time-increasing D achieves a regret order arbitrarily close to logarithmic.
  • Decentralized setting: The decentralized formulation includes M players, local observations, unobservable actions by other players, and collision-dependent rewards.

B. Decentralized DSEE Policy

The decentralized DSEE policy uses synchronized exploration and exploitation epochs with pre-agreed offsets, then removes these coordination requirements through collision-based sharing. Under the stated models and assumptions, it preserves logarithmic regret order, including without global timing and pre-agreement.

  • Synchronized decentralized policy: Global timing synchronizes players’ deterministic epochs, while pre-agreed offsets coordinate arm sharing during exploitation.The offsets can be determined using information such as player IDs.
  • Synchronized decentralized policy: Players explore all N arms in round-robin epochs and exploit their M highest-sample-mean arms using pre-agreed offsets.Exploration epochs have length N × 4^n−1, while exploitation assigns arms in a round-robin fashion.
  • Synchronized decentralized policy: Collisions can occur during exploitation because players’ locally estimated arm rankings may differ.Players may select different arm sets and ranks despite using different time-sharing offsets.
  • Regret guarantees: The decentralized DSEE policy achieves the same logarithmic regret order as the centralized setting under the restless models considered.The result is stated for the exogenous and endogenous restless settings under the theorem assumptions.
  • Complete decentralization: A collision-based adjustment eliminates global synchronization and pre-agreement while maintaining logarithmic regret order.During exploration, collisions affect immediate reward but not observed reward states, and exploitation collisions are bounded to enable efficient sharing.
  • Complete decentralization: When collisions are unobservable, corrupted measurements can misidentify arm ranks, and achieving logarithmic regret without coordination remains open.This limitation arises because players then observe only local rewards rather than the chosen arms’ reward states.

IV. SIMULATION RESULTS

Simulations compare DSEE with RCA in restless bandit settings and report stronger long-run performance for DSEE. The reported advantage is linked to DSEE learning from all observations, whereas RCA discards observations outside regenerative cycles.

  • DSEE versus RCA: RCA initially outperforms DSEE briefly, but DSEE provides significantly better performance as time increases.The comparison is reported for the regret curves in Fig. 4.
  • DSEE versus RCA: DSEE converges to logarithmic regret order for a small policy parameter D, yielding better finite-time performance.The sufficient condition on D is reported as not necessary.
  • Large reward state space: In a five-arm, 20-state experiment, arm 1 is made better than the others by scaling its state rewards by 1.5.The transition probabilities are generated randomly for this large-state-space example.
  • Large reward state space: The simulations again show better performance for DSEE than RCA in the large reward state-space example.The parameter choices were selected so regret divided by log t converges to a constant over a reasonable horizon.
  • Interpretation: DSEE’s advantage may result from using all observations, while RCA learns only from observations inside regenerative cycles.RCA may discard many observations when the state space is large or the pilot state has small stationary probability.

APPENDIX A. PROOF OF THEOREM 1 AND THEOREM 3

The proof decomposes regret into switching, exploration, and exploitation components, then bounds each through epoch counts, Markov-chain concentration, and transient effects. The resulting regret upper bound has logarithmic order.

  • A constant bounds the reward deviation from Tµ for a continuously played arm, so logarithmically many switches yield logarithmic switching regret.
  • The regret from bad arms in exploration epochs is bounded, while exploitation-epoch regret is controlled using Chernoff bounds for finite-state reversible Markov chains.
  • Combining the component bounds gives the regret upper bound stated in the theorem.
  • Growing exploration and exploitation epochs control sample-mean errors formed from noncontiguous Markov segments.

APPENDIX B. PROOF OF THEOREM 2 AND THEOREM 4

This proof allows the epoch parameters to grow with time when system information is unavailable. It shows that switching and exploration costs are lower order, while total regret remains on the order of f(t) log t.

  • The proof replaces fixed epoch parameters with L(t) tending to infinity as t grows.
  • Arm-switching regret is lower order than f(t) log t under the logarithmic switching bound.
  • Exploration regret is either lower order than f(t) log t or, with D(t) = f(t), on the same order.
  • The time spent on a bad arm during exploitation can be bounded by a constant independent of t.
  • Because all regret components are no larger than the target order, total regret is on the same order of f(t) log t.

APPENDIX C. PROOF OF THEOREM 3

For multiple played arms, the proof separates transient and bad-arm regret and bounds both components logarithmically. Combining these bounds yields the theorem’s regret upper bound.

  • For M > 1, regret is rewritten into terms representing transient effects and engagement of bad arms.
  • The transient-effect term has a logarithmic upper bound obtained from the Markov-chain lemma and epoch-count bounds.
  • The bad-arm term is bounded by separately controlling bad-arm time during exploration and exploitation epochs.
  • Combining the component bounds gives the regret upper bound stated in the theorem.

APPENDIX D. PROOF OF THEOREM 5

The decentralized proof bounds regret from coordination, exploration, and exploitation mistakes under shared-arm dynamics. The resulting regret has logarithmic order in both exogenous and endogenous restless models.

  • The decentralized regret bound combines switching, exploration, exploitation, and conflict-related terms.
  • Exploitation epochs assign players rotating target arms so the best M arms can be played without conflict when identification succeeds.
  • Identification mistakes during exploitation are bounded separately for no-reward-conflict and reward-sharing models.
  • The transient-effect component is constant under the exogenous restless model and has order log t under the endogenous restless model.
  • All regret components are no larger than f(t) log t, so total decentralized regret has the same order.

APPENDIX F. PROOF OF THEOREM 7

The proof bounds the expected occurrences of exploration, incorrect best-arm identification, and collisions by logarithmic order in time. It first controls singular slots, then shows collisions in non-singular periods are also logarithmic.

  • The proof identifies three regret-producing events: incorrect identification of the M best arms, exploration, and collisions among players.A singular slot is defined as one in which either incorrect identification or exploration occurs.
  • The expected number of singular slots is logarithmic because each player’s learning mistakes and local exploration sequence have logarithmic expected cardinality.
  • Between successive singular slots, players correctly identify the M best arms, so collisions occur only when at least two players choose the same arm.
  • Randomized arm selection after collisions bounds the expected collisions before players become orthogonalized into the M best arms by a time-uniform constant.
  • Because the expected number of periods between singular slots is logarithmic, collisions across all non-singular slots are logarithmic in time.
Loading 1011.4969v2…