PaperlayerView exact revision on arXiv

Source-linked AI summary

Indexability of Restless Bandit Problems and Optimality of Whittle's Index for Dynamic Multichannel Access

Keqin Liu, Qing Zhao

arXiv:0810.4658v3cs.IT

TL;DR

Whittle’s index policy is difficult to establish and compute, especially for restless bandit problems with uncountable state spaces. This paper establishes indexability and closed-form indices, and shows optimality under certain conditions for stochastically identical arms through equivalence with the myopic policy.

  • Problem

    Whittle’s index policy is difficult to establish and compute, especially for restless bandit problems with uncountable state spaces.

  • Method

    The paper establishes indexability under discounted and average reward criteria and derives Whittle’s index in closed form, leveraging its equivalence with a simpler myopic index.

  • Results

    For stochastically identical arms, Whittle’s index policy coincides with the myopic policy and is optimal under certain conditions.

  • Takeaways & Limitations

    The equivalence permits work with the simpler myopic index and yields a semi-universal structure for Whittle’s index policy.

Abstract

from arXiv · show

We consider a class of restless multi-armed bandit problems (RMBP) that arises in dynamic multichannel access, user/server scheduling, and optimal activation in multi-agent systems. For this class of RMBP, we establish the indexability and obtain Whittle's index in closed-form for both discounted and average reward criteria. These results lead to a direct implementation of Whittle's index policy with remarkably low complexity. When these Markov chains are stochastically identical, we show that Whittle's index policy is optimal under certain conditions. Furthermore, it has a semi-universal structure that obviates the need to know the Markov transition probabilities. The optimality and the semi-universal structure result from the equivalency between Whittle's index policy and the myopic policy established in this work. For non-identical channels, we develop efficient algorithms for computing a performance upper bound given by Lagrangian relaxation. The tightness of the upper bound and the near-optimal performance of Whittle's index policy are illustrated with simulation examples.

I. INTRODUCTION

The paper studies restless bandit problems arising in multichannel access and related scheduling settings, where passive arms evolve and exactly K of N arms are selected to maximize long-run reward. It addresses difficult indexability and computation questions by deriving Whittle’s index for a relevant class and analyzing its optimality, structure, and performance bounds.

  • A. Restless Multi-armed Bandit Problem: Restless multi-armed bandits allow multiple arms to be activated while passive arms continue changing state, making general optimization PSPACE-hard.Whittle’s index policy relaxes the per-time activation constraint to an average constraint, which decouples the arms.
  • C. Main Results: Whittle indexability and index computation are challenging, particularly for RMBPs with uncountable state spaces and indices often requiring numerical approximation.The paper targets these existence and complexity difficulties for a class relevant to multichannel dynamic access.
  • B. Dynamic Multichannel Access: In the studied problem, a player probes K of N independent two-state Markov chains and receives rewards determined by the probed chains’ states.The objective is to select K chains at each time to maximize long-run reward.
  • B. Dynamic Multichannel Access: This model captures dynamic multichannel access, including cognitive radio, cellular downlink scheduling, fading-channel transmission, and target tracking.Channel states represent communication quality or occupancy, while related applications include tracking N targets with K unmanned aerial vehicles.
  • C. Main Results: For this class, the paper establishes indexability and closed-form Whittle indices under both discounted and average reward criteria.The closed forms reduce implementation to simple evaluations, while the proof extends an approach previously used for classical multi-armed bandits to a nontrivial RMBP.
  • C. Main Results: For stochastically identical arms, Whittle’s index policy coincides with the myopic policy and is optimal under certain conditions.The policy also has a semi-universal structure requiring only the ordering of p11 and p01, not the transition probabilities themselves.
  • C. Main Results: For non-identical arms, the paper develops efficient algorithms for computing a Lagrangian-relaxation performance upper bound.The bound can be computed within ε-accuracy in O(N(log N)^2) time, or exactly in O(N^2 log N) time when every channel satisfies p11 < p01.

D. Related Work

The paper situates its RMBP results within work on multichannel access, scheduling, indexability, and approximation. It extends prior analyses by treating discounted and average rewards, Lagrangian upper bounds, and identical-channel optimality.

  • Prior work applies RMBPs to cognitive-radio access, mobile-network allocation, multicast scheduling, target tracking, and Internet advertising.
  • Existing studies establish indexability or closed-form Whittle indices for several specific RMBP and POMDP formulations.
  • Earlier work characterizes myopic-policy structure and optimality for identical channels, including N > 2 under p11 ≥ p01.
  • For related RMBPs, prior approximation approaches include a constant-factor 1/68 policy and a factor-2 policy via LP relaxation.
  • This paper differs by covering discounted and average rewards, Lagrangian-relaxation performance bounds, and semi-universal optimality results for identical channels.
  • The studied model consists of N independent Gilbert-Elliot channels, with K channels sensed per slot and channel-specific transition behavior.

B. Restless Multi-armed Bandit Formulation

The formulation models partially observed Gilbert-Elliot channels as restless bandit arms whose belief states guide sensing decisions. The paper evaluates policies under discounted and average reward criteria.

  • B. Restless Multi-armed Bandit Formulation: Because channel states are unobserved, each arm is represented by its belief state, the conditional probability that the channel is good.
  • B. Restless Multi-armed Bandit Formulation: The sensing action and observations update the belief vector, while both active and passive arms continue to evolve.
  • B. Restless Multi-armed Bandit Formulation: The objective is to design a policy maximizing expected long-term reward, measured either by infinite-horizon discounted reward or average reward.
  • A. Index Policy: An index policy computes arm-specific indices and activates the K arms with the largest current values.
  • A. Index Policy: Strong decomposability reduces index computation from an N-dimensional problem to N independent one-dimensional problems.
  • B. Indexability and Whittle’s Index Policy: Whittle’s index is defined through a passivity subsidy, with indexability requiring the passive set to grow monotonically from empty to the whole state space.

IV. WHITTLE’S INDEX UNDER DISCOUNTED REWARD CRITERION

For the discounted criterion, the paper establishes indexability, derives Whittle’s index in closed form, and develops efficient algorithms for an upper bound on optimal performance. The analysis relies on threshold policies and belief-transition properties.

  • The discounted-reward analysis establishes indexability, a closed-form Whittle index, and efficient computation of an optimal-performance upper bound.
  • A. Properties of Belief State Transition: Unobserved-arm beliefs remain within the interval bounded by p01 and p11 and converge toward the stationary belief ωo = p01.
  • A. Properties of Belief State Transition: For positively correlated channels, T k(ω) converges monotonically to ωo; for negatively correlated channels, even and odd iterates converge from opposite directions.
  • A. Properties of Belief State Transition: The crossing time L(ω, ω′) is the minimum time for a passive arm’s belief to move across ω′ from ω.
  • B. The Optimal Policy: The subsidized single-arm problem has a threshold optimal policy, with the threshold arising from the linear active value and convex passive value.
  • B. The Optimal Policy: For 0 ≤ m < 1, the active and passive value functions have one unique intersection defining the threshold.
  • B. The Optimal Policy: When m ≥ 1, passivity is always optimal, whereas when m < 0, activation is always optimal.

C. Closed-form Expression of The Value Function

The paper derives closed-form value and passive-time expressions by exploiting threshold crossings of belief trajectories. These expressions support efficient indexability analysis and upper-bound computation, with a stated derivative convention at nondifferentiable subsidies.

  • C. Closed-form Expression of The Value Function: Closed-form value functions are obtained by solving the coupled quantities Vβ,m(p01) and Vβ,m(p11).
  • C. Closed-form Expression of The Value Function: The crossing-time representation accumulates subsidy during initial passive slots, then activates the arm at the crossing slot.
  • C. Closed-form Expression of The Value Function: The derivation identifies the first slot when the belief crosses the optimal threshold and uses the resulting passive and active phases.
  • D. The Total Discounted Time of Being Passive: The total discounted passive time Dβ,m(ω) is computed through a dynamic program analogous to the value-function recursion.
  • D. The Total Discounted Time of Being Passive: At subsidy nondifferentiability points, the paper includes the threshold in the passive set and uses the right derivative.
  • D. The Total Discounted Time of Being Passive: Dβ,m(ω) is monotonically increasing and piecewise constant in m, while Vβ,m(ω) is piecewise linear and convex in m.
  • D. The Total Discounted Time of Being Passive: These passive-time properties enable an efficient algorithm for computing a performance upper bound.

E. Indexability and Whittle’s Index Policy

The paper establishes indexability and closed-form Whittle indices for the restless bandit process, with structure depending on channel correlation. For stochastically identical arms, monotonicity makes Whittle’s index policy equivalent to the myopic policy.

  • The restless multi-armed bandit process is indexable, and Whittle’s index is obtained in closed form.The result is stated in Theorems 1 and 2 for the considered channel model.
  • Whittle’s index increases monotonically with belief, making its policy equivalent to the myopic policy for stochastically identical arms.This equivalence provides a simple index form for analyzing the policy’s structure and optimality.
  • For positively correlated channels, Whittle’s index is piecewise concave with countable pieces and is linear on [0, p01] and [p11, 1].The interval [p01, ωo) contains the most complex structure, with countable concave pieces associated with crossing times.
  • For negatively correlated channels, Whittle’s index is piecewise convex with finite pieces and is linear on [0, p11] and [p01, 1].Its remaining regions are described using the threshold-related points ωo and T(p11).
  • Under the relaxed constraint, activating arms whose Whittle indices exceed the Lagrangian multiplier m∗ is optimal.The multiplier m∗ satisfies the relaxed activation constraint or achieves the infimum in the Lagrangian formulation.

2) An Upper Bound of The Optimal Performance:

The paper uses Lagrangian relaxation to upper-bound optimal performance and exploits convexity and piecewise-constant passive-time structure to compute the bound efficiently. The resulting bound benchmarks strict-constraint policies, while simulations show tightness and near-optimal Whittle performance.

  • The relaxed optimum provides a performance benchmark for all RMBP policies, including Whittle’s index policy.The relaxation permits time-varying activation counts whose discounted average equals K.
  • The Lagrangian objective Gβ,m(Ω(1)) is convex in m, and its infimum occurs when its right derivative first becomes nonnegative.This property supports sequential region searches over subsidy values.
  • The discounted passive time is piecewise constant in m, enabling partition-based searches for the minimizing subsidy.Figures 10 and 11 distinguish the passive-time structure for p11 < p01 and p11 ≥ p01.
  • When m∗ lies outside the gray area, the algorithm returns the exact relaxed optimum; if every channel is negatively correlated, it is always exact.For positively correlated channels, infinite constant regions create the gray-area approximation issue.
  • O(N^2 log N) time is sufficient to output a value G within ǫ of the relaxed optimum for any ǫ > 0.The algorithm is described in Fig. 12.
  • A binary-search alternative runs in O(N(log N)^2) time but cannot output the exact value of m∗ and the relaxed optimum.
  • Simulations demonstrate near-optimal Whittle performance and a tight performance upper bound under the discounted criterion.The example in Fig. 13 uses N = 8 and β = 0.8.

A. The Value Function and The Optimal Policy

For the average reward criterion, the paper derives threshold optimal policies, preserves indexability and closed-form Whittle indices, and studies their limiting relationship with discounted policies. The resulting index policy has near-optimal simulated performance and yields an efficiently computable benchmark.

  • The Value Function and The Optimal Policy: The single-armed bandit with subsidy has a threshold optimal policy under the average reward criterion.The threshold is the limit of discounted-policy thresholds as β → 1.
  • B. Indexability and Whittle’s index policy: The restless multi-armed bandit process remains indexable under average reward, with Whittle’s index available in closed form.This is stated in Theorem 4 for positively and negatively correlated channels.
  • B. Indexability and Whittle’s index policy: The monotonicity and piecewise concave or convex structure of Whittle’s index under discounting are preserved under average reward.For negatively correlated channels, the average-reward index is constant on ωo ≤ ω < T^1(p11).
  • The Value Function and The Optimal Policy: The value function Jm and average passive time Dm have closed-form expressions, with Dm piecewise constant and increasing in m.These expressions support computation of the subsidy achieving the Lagrangian infimum.
  • The Value Function and The Optimal Policy: The relaxed average-reward optimum provides a benchmark for Whittle’s index policy under the strict activation constraint.The upper bound can be evaluated using a modified version of the discounted-case algorithm.
  • The Value Function and The Optimal Policy: Simulations show near-optimal performance of Whittle’s index policy under the average reward criterion.

VI. WHITTLE’S INDEX POLICY FOR STOCHASTICALLY IDENTICAL CHANNELS

For stochastically identical channels, Whittle’s index policy is equivalent to the myopic policy, yielding a simple queue-based implementation. Its semi-universal structure requires only the ordering of p11 and p01, and it tracks model variations while supporting optimality and performance guarantees under stated conditions.

  • Whittle’s index policy is analyzed through its equivalence to the simpler myopic policy for stochastically identical channels.
  • Channel selection is implemented by maintaining a queue, sensing the K channels at its head, and reordering channels after each slot.
  • When p11 ≥ p01, channels observed in state 1 remain at the queue head, while channels observed in state 0 move to the end.
  • When p11 < p01, channels observed in state 0 remain at the head, channels observed in state 1 move to the end, and unobserved-channel ordering is reversed.
  • The queue structure requires no computation and little memory, and it can be implemented without knowing transition probabilities beyond the order of p11 and p01.
  • Whittle’s index policy tracks channel-model variations when the ordering of p11 and p01 remains unchanged.The paper reports effective tracking after transition probabilities change.
  • The paper also derives performance bounds, including an approximation factor approaching 1 as K increases and at least half the optimal performance for negatively correlated channels.The approximation factor may improve for positively correlated channels under additional transition-probability conditions.
  • For stochastically identical channels, the policy is optimal under certain conditions, including K = 1 for positively correlated channels and K = N−1.Optimality for K = N is stated to be trivial; numerical examples also match Whittle and optimal actions for general K.

APPENDIX A: PROOF OF LEMMA 3

The appendix proves Lemma 3 by expressing value functions through crossing times and establishing the monotonicity needed for indexability. The proof treats negatively and positively correlated channels separately.

  • Two equations in the crossing times determine Vβ,m(p01) and Vβ,m(p11) across the relevant regions of ω∗β(m).
  • Indexability is reduced to proving monotonicity of the threshold ω∗β(m) with respect to the subsidy m.
  • Negatively correlated channel: For negatively correlated channels, the proof establishes the required inequality by showing an auxiliary function is negative for 0 ≤ β < 1.
  • Positively correlated channel: For positively correlated channels, the proof reduces the condition to inequalities involving x = p11 − p01 and crossing time L, then verifies monotonicity arguments.

APPENDIX C: PROOF OF THEOREM 3

The appendix establishes the average-reward result by bounding value functions, handling the β → 1 limit, and showing convergence from discounted threshold policies. It also gives an O(N2 log N) algorithmic complexity bound.

  • The algorithm’s overall running time is at most O(N2 log N).The stated bounds include O(N) for Step 1, at most O(N log N) for Step 2, and O(N(log N)2) for Step 3.
  • Value boundedness follows by bounding Vβ,m(ω) between endpoint values and controlling differences between Vβ,m(p01) and Vβ,m(p11).
  • For 0 ≤ m < 1, the average-reward value function W(ω) is defined as limβ→1 Wβ(ω), with the limit given in Theorem 4.
  • For m < 0 the arm is always active, for m ≥ 1 it is always passive, and for 0 ≤ m < 1 activity is governed by a threshold.
  • The threshold policy is optimal for the single-armed bandit under the average-reward criterion when the discounted process satisfies value boundedness.

APPENDIX F: PROOF OF THEOREM 4

The appendix connects the Whittle index to the subsidy threshold through monotonic belief updates. This yields the queue ordering used by the policy for positively and negatively correlated channels.

  • The threshold ω∗(m) is monotonically increasing with the subsidy m.
  • Whittle’s index at belief state ω is the infimum subsidy m for which ω enters the passive set, equivalently W(ω).
  • For unobserved channels, T1(ω) increases when p11 > p01 and decreases when p11 < p01, while beliefs remain bounded between p01 and p11 after the first slot.
  • p11 ≥ p01: When p11 ≥ p01, channels observed in state 1 attain belief p11 and channels observed in state 0 attain p01, so the equivalent myopic policy keeps state-1 channels preferred.
  • p11 < p01: For p11 < p01, reversing the order of unobserved channels preserves belief ordering because T1(ω) is decreasing.

APPENDIX H: PROOF OF THEOREM 5

The proof bounds Whittle-policy performance by analyzing transmission-period lengths under positively and negatively correlated channels. It establishes optimality in key cases and at least half-optimal performance for negatively correlated channels.

  • The proof bounds throughput by bounding the average transmission-period length E[τ], whose behavior depends on channel correlation.A transmission period is the number of consecutive slots during which a channel is sensed.
  • For positively correlated channels, larger initial belief values stochastically increase transmission-period length; for negatively correlated channels, the ordering reverses.
  • Whittle’s index policy is optimal for K = 1 and p11 ≥ p01 through its equivalency with the myopic policy.
  • Whittle’s index policy is optimal when K = N −1 by matching the genie-aided system’s performance.The genie-aided system reveals all channel states at each slot, providing an upper bound for the original system.
  • Whittle’s index policy achieves at least half the optimal performance for negatively correlated channels, where p11 < p01.
Loading 0810.4658v3…