PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Learning of Rested and Restless Bandits

Cem Tekin, Mingyan Liu

arXiv:1102.3508v1math.OCcs.LG

TL;DR

The paper addresses online selection of multiple arms when rested and restless Markov chains have unknown state spaces and statistics, a setting relevant to opportunistic spectrum access. It extends UCB1 to multiple plays and constructs a regenerative cycle algorithm, obtaining logarithmic regret for the restless problem. The conclusion states that the restless regret bound is optimal.

  • Problem

    The paper studies how to select M of K unknown rested or restless Markovian arms over time to maximize long-term reward, including opportunistic spectrum access.

  • Method

    It extends UCB1 to multiple plays and constructs the regenerative cycle algorithm RCA for restless bandits.

  • Results

    The algorithms achieve logarithmic regret for restless Markovian bandits, with the stated regret bound also optimal.

  • Takeaways & Limitations

    The paper provides logarithmic-regret learning procedures for both rested and restless multiarmed bandits with multiple plays.

Abstract

from arXiv · show

In this paper we study the online learning problem involving rested and restless multiarmed bandits with multiple plays. The system consists of a single player/user and a set of K finite-state discrete-time Markov chains (arms) with unknown state spaces and statistics. At each time step the player can play M arms. The objective of the user is to decide for each step which M of the K arms to play over a sequence of trials so as to maximize its long term reward. The restless multiarmed bandit is particularly relevant to the application of opportunistic spectrum access (OSA), where a (secondary) user has access to a set of K channels, each of time-varying condition as a result of random fading and/or certain primary users' activities.

I. INTRODUCTION

The paper studies online selection of M arms from K rested or restless Markovian arms with unknown statistics, motivated by opportunistic spectrum access. It develops logarithmic-regret algorithms while addressing the exploration–exploitation tradeoff.

  • Problem setting: The problem is to select M of K arms at each time to maximize long-term reward using past actions and observations.Each played arm produces a state-dependent reward, while arm states are observed only when played.
  • Problem setting: Rested arms freeze when unplayed, whereas restless arms continue evolving according to a possibly different law regardless of user actions.For restless arms, the next observed state depends on the elapsed time between plays.
  • Motivation: Opportunistic spectrum access models channel conditions as Markov chains affected by fading and primary-user activity, with good conditions yielding higher data rates or lower power.The user probes M channels and may use those sensed to be available.
  • Exploration and exploitation: The central challenge is balancing exploration of all arms against exploiting arms believed to be best, without wasting plays collecting statistics.The paper measures performance using regret relative to an ideal policy, focusing on weak regret.
  • Contributions: The paper first studies rested Markovian bandits and then shows that a straightforward multiple-play extension of UCB1 yields logarithmic regret for restless bandits.The construction exploits the distinction between rested and restless settings to develop a regenerative cycle algorithm.

II. PROBLEM FORMULATION AND PRELIMINARIES

The paper formulates rested and restless arms as finite-state, irreducible, aperiodic Markov chains with stationary rewards and multiple plays. It defines regret relative to the M best arms and develops bounds using Markov-chain concentration and hitting-time properties.

  • Model: Each arm is a finite-state, irreducible, aperiodic discrete-time Markov chain with transition matrix P_i and stationary distribution π_i.The arms are assumed mutually independent.
  • Rested and restless arms: A rested arm changes only when played, whereas a restless arm changes regardless of the user’s actions; the rested model is a special case of the restless model.The restless model can use active and passive transition laws, while the development follows the rested model.
  • Rewards and actions: At each discrete time step, the player selects M arms, and each arm’s reward depends on its observed state.The mean reward μ_i is defined under the arm’s stationary distribution.
  • Assumptions: For restless arms, the analysis assumes μ_M > μ_M+1 to prevent potentially more-than-logarithmic switching between the M-th and (M+1)-th arms.The strict separation is not necessary for rested arms, where μ_M ≥ μ_M+1 suffices.
  • Regret: Regret compares a policy’s expected total reward through time n with the expected reward obtained by always playing the M-best arms.The objective is to establish order-optimal regret by bounding expected plays of suboptimal arms.
  • Analysis tools: The analysis invokes Markov-chain large-deviation bounds and stopping-time results, including eigenvalue gaps and mean hitting times.These tools support concentration and regenerative-cycle arguments for the proposed policies.

III. ANALYSIS OF THE RESTED BANDIT PROBLEM WITH MULTIPLE PLAYS

This section analyzes rested Markovian bandits with multiple plays and presents UCB-M, which selects multiple arms using confidence indices. Under stated Markov-chain conditions and a sufficient exploration constant, its regret is logarithmically bounded.

  • Modeling multiple plays: The multiple-play setting is represented as M coordinated players, each playing one arm per time step with centralized information and no collisions.This is a presentation device for a single player selecting M arms.
  • UCB-M algorithm: UCB-M selects the M arms with the highest indices at each time step and updates those indices using observed rewards.Each index combines an arm's sample mean reward with an exploration term reflecting uncertainty.
  • Assumptions and proof strategy: The analysis assumes finite-state, irreducible, aperiodic Markov chains with irreducible multiplicative symmetrizations of their transition matrices.The proof proceeds by relating regret to expected arm plays and bounding each suboptimal arm's expected plays logarithmically.
  • Regret guarantee: UCB-M achieves logarithmic regret for rested bandits when the exploration constant satisfies the stated sufficient condition.The theorem requires L ≥112S2, and the regret bound includes logarithmic and problem-dependent constant terms.
  • Regret guarantee: The sufficient condition for the exploration constant requires knowledge of the underlying Markov chains.The paper notes that adapting L over time may remove this requirement.

IV. ANALYSIS OF THE RESTLESS BANDIT PROBLEM WITH MULTIPLE PLAYS

The paper develops RCA-M, a regenerative-cycle algorithm for restless bandits with multiple plays, and establishes logarithmic regret under stated assumptions. RCA-M uses only observations from regenerative-cycle sub-blocks for index computation while retaining other rewards in total reward.

  • RCA-M extends the regenerative cycle algorithm to the multiple-play restless bandit problem and guarantees logarithmic regret.
  • Restless arms continue evolving when unplayed, so observation distributions depend on the elapsed time since an arm was last played.
  • RCA-M stitches observations from regenerative cycles into sample paths with the original Markov-chain statistics, enabling sample-mean estimation of stationary rewards.
  • Each block repeatedly plays one arm until a designated state is observed twice, and multiple blocks can overlap because M arms are played simultaneously.
  • RCA-M divides blocks into three sub-blocks and computes arm indices using rewards collected during SB2, while SB1 and SB3 rewards still contribute to total reward.
  • The analysis bounds suboptimal-arm block selections logarithmically, uses finite expected block lengths, and shows switching regret is also logarithmic.

V. AN EXAMPLE FOR OSA: GILBERT-ELLIOT CHANNEL MODEL

The paper evaluates RCA-M in four Gilbert-Elliot channel environments representing bursty and non-bursty channels with separated or similar mean rewards. Normalized regret is compared under the minimum sufficient L values and L = 1.

  • V. AN EXAMPLE FOR OSA: GILBERT-ELLIOT CHANNEL MODEL: RCA-M is simulated under the Gilbert-Elliot channel model, where channels have good and bad states and primary-user activity induces state transitions.The resulting problem is framed as opportunistic spectrum access.
  • V. AN EXAMPLE FOR OSA: GILBERT-ELLIOT CHANNEL MODEL: Normalized regret is computed as regret per single play, R(n)/M, by averaging the simulation results.The figures report normalized regret for the four environments under different L values.
  • V. AN EXAMPLE FOR OSA: GILBERT-ELLIOT CHANNEL MODEL: The four environments vary burstiness and whether channel mean rewards are close: S1 is bursty and separated, S2 non-bursty and separated, S3 bursty and similar, and S4 non-bursty and similar.Transition probabilities and mean rewards are specified in Tables I and II.
  • V. AN EXAMPLE FOR OSA: GILBERT-ELLIOT CHANNEL MODEL: The logarithmic-regret bound is evaluated at the minimum L values satisfying its sufficient condition, using Figures 4, 6, 8, and 10.These correspond to the displayed environments and their respective minimum sufficient L settings.
  • V. AN EXAMPLE FOR OSA: GILBERT-ELLIOT CHANNEL MODEL: Normalized regret is smaller for L = 1 than for the minimum L values required by the logarithmic bound.The comparison is made between Figures 4, 6, 8, 10 and Figures 5, 7, 9, 11.
  • V. AN EXAMPLE FOR OSA: GILBERT-ELLIOT CHANNEL MODEL: For the Gilbert-Elliot model, regret can be smaller when L is below 112S2.The paper therefore presents the logarithmic-bound condition on L as sufficient but not apparently necessary.

VI. DISCUSSION

The discussion considers ways to improve RCA-M's performance and possible relaxations and extensions. It focuses on improving constants rather than changing the main asymptotic result.

  • VI. DISCUSSION: The discussion examines improvements to RCA-M's performance in terms of constants, along with possible relaxations and extensions.These topics organize the subsequent discussion.
  • VI. DISCUSSION: The proposed discussion concerns both performance improvement and relaxation of conditions or extensions of the setting.The passage presents these as possible directions rather than established results.

A. Applicability, Performance Improvement, and Relaxation

The paper extends its logarithmic-regret analysis to general restless bandits and discusses modifications that reduce wasted observations by selecting regenerative states with shorter estimated recurrence times.

  • A. Applicability, Performance Improvement, and Relaxation: The same logarithmic regret bound derived in the paper holds for the general restless bandit problem.The extension allows distinct active and passive transition matrices for each arm.
  • A. Applicability, Performance Improvement, and Relaxation: Different passive transition matrices do not affect the analysis because rewards depend on active transitions and the first state after an interruption.The resulting regret contribution from passive dynamics is at most logarithmic when expected hitting times are finite.
  • A. Applicability, Performance Improvement, and Relaxation: The logarithmic bound continues to hold even when an arm is not Markovian during passive periods.This follows in the paper from logarithmically many plays of suboptimal arms and finite expected hitting times.
  • A. Applicability, Performance Improvement, and Relaxation: RCA-M can select each arm's regenerative state by recording observations across states and choosing the state with the smallest observed recurrence count.For arm i at block n, the modification sets γi(n) to the state minimizing ki(s, t_n−1).
  • A. Applicability, Performance Improvement, and Relaxation: The modification is intended to reduce observations excluded from index computation and the probability of selecting a suboptimal arm.The paper presents these as performance improvements of the modified regenerative-state choice.
  • A. Applicability, Performance Improvement, and Relaxation: The regenerative state may be selected arbitrarily within a block if successive SB2 blocks end and start in the same state.That continuity condition preserves the sample-path property used by the analysis.

B. Relaxation of Certain Conditions

The paper discusses relaxing the sufficient condition on L and addressing tied boundary-arm rewards. It notes empirical and asymptotic alternatives, while retaining a strict inequality assumption for the restless problem.

  • B. Relaxation of Certain Conditions: The sufficient condition on L does not appear necessary, since the examples achieve smaller regret with L = 1.The condition originates from the large-deviation bound used in Lemma 1.
  • B. Relaxation of Certain Conditions: A tighter large-deviation bound could relax the condition on L.The paper identifies this as a possible analytical relaxation.
  • B. Relaxation of Certain Conditions: Without information needed to derive the sufficient condition, choosing L to grow slowly with time achieves o(log(n)f(n)) regret for any increasing sequence f(n).The paper points to this approach as an alternative when the condition cannot be determined.
  • B. Relaxation of Certain Conditions: The restless multiarmed bandit analysis requires the strict inequality μM > μM+1.The tied case is treated separately through the threshold modification, whose logarithmic-regret guarantee remains unverified.
  • B. Relaxation of Certain Conditions: When μM = μM+1, the indices of the M-th and (M+1)-th arms can oscillate indefinitely, producing many discontinuities.The paper contrasts this with the requirement that discontinuities from optimal arms be no more than logarithmic for logarithmic regret.
  • B. Relaxation of Certain Conditions: Adding a threshold ε so a new arm must exceed the weakest played arm's index by at least ε can avoid indefinite switching when ε is sufficiently small.The paper states that further analysis is needed to verify logarithmic regret for this approach.

C. Definition of Regret

The paper uses weak regret, comparing the learning strategy with the best single-action strategy. A regret measure relative to the optimal policy would be preferable in principle, but is generally intractable for restless bandits because that policy is not known.

  • Weak regret compares the learning strategy with the best single-action strategy.
  • With known statistics, the best achievable strategy is generally not a single-action policy.Such a policy can in principle be driven using dynamic programming.
  • Ideally, regret would be measured relative to the optimal policy.
  • In restless bandits, the optimal policy is generally unknown, making this comparison intractable.Comparison is possible only in some very limited cases where the optimal policy is known.

D. Extensions to A Decentralized Multiplayer Setting and Comparison with Similar Work

The paper contrasts RCA-M with prior restless-bandit methods and notes that its current form does not straightforwardly extend to decentralized multiplayer settings. RCA-M implicitly combines exploration and exploitation through an index, unlike block-based alternatives.

  • Extensions to A Decentralized Multiplayer Setting: RCA-M does not currently extend straightforwardly to decentralized multiplayer settings with collisions.
  • Comparison with Similar Work: A prior method achieves logarithmic regret using exploration and exploitation blocks that grow geometrically with time.
  • Comparison with Similar Work: That prior construction is amenable to multiplayer extension because its growing block length can be synchronized among players.
  • Comparison with Similar Work: RCA-M reduces a restless bandit problem to a rested version through its sampling approach.
  • Comparison with Similar Work: Unlike the block-based scheme, RCA-M performs exploration and exploitation simultaneously and implicitly through an index.

VII. CONCLUSION

The paper studies rested and restless Markovian bandits with multiple plays, extending UCB1 and introducing RCA-M for restless arms. RCA-M uses regenerative-cycle sampling to obtain logarithmic, optimal regret under mild transition-probability conditions, with numerical evaluation on Gilbert-Elliot channels.

  • The paper considers rested and restless multiarmed bandits with Markovian rewards and multiple plays.
  • A simple multiple-play extension of UCB1 produces logarithmic regret uniformly over time.
  • RCA-M computes a sample-mean-based index policy using regenerative cycles of a Markov chain.
  • Under mild conditions on transition probabilities, RCA-M achieves logarithmic regret uniformly over time, and the bound is optimal.
  • The algorithm is numerically examined for opportunistic spectrum access with the Gilbert-Elliot channel model.

APPENDIX F

The appendix bounds regret by analyzing discontinuities, blocks, and regenerative cycles for optimal and suboptimal arms. The resulting logarithmic bound does not depend on the selected regenerative states.

  • The regenerative sample paths are formed by joining intervals between visits to designated states, yielding a continuous Markov-chain sample path.
  • The number of time slots in which an optimal arm is not played is at most logarithmic, as is the number of discontinuities in playing an optimal arm.
  • Each combined block of an optimal arm contains an initial segment before returning to its regenerative state and a segment of regenerative cycles.
  • The number of combined blocks for an optimal arm is bounded by its play discontinuities and therefore by the blocks in which suboptimal arms are played.
  • The resulting regret bound is logarithmic and independent of the chosen regenerative states.
Loading 1102.3508v1…