On Optimality of Greedy Policy for a Class of Standard Reward Function of Restless Multi-armed Bandit Problem

Quan Liu, Kehao Wang, Lin ChenarXiv 2011 · arXiv

Introduction

The Restless Multi-armed Bandit (RMAB) problem is a cornerstone of stochastic scheduling and resource allocation. Unlike the classical Multi-armed Bandit, where only the chosen arm's state changes, the "restless" variant allows the state of every arm to evolve according to a Markov process, regardless of whether it is selected. This added complexity makes the RMAB problem PSPACE-hard, rendering the search for an optimal policy computationally prohibitive for large-scale systems.

In practice, engineers often rely on "greedy" (or myopic) policies. A greedy policy prioritizes immediate rewards, choosing actions that maximize the payoff in the current time step. While computationally efficient, greedy strategies are generally suboptimal because they fail to account for how current choices affect future states. This paper investigates the conditions under which this simple greedy approach is, in fact, the optimal strategy for a specific class of reward functions.

Defining Standard Reward Functions

The authors introduce the concept of Standard Reward Functions to categorize a wide range of objectives used in engineering. For a reward function to be classified as "standard," it must satisfy three fundamental properties:

  1. Symmetry: The reward is invariant to the permutation of channels. It depends on the collective states of the chosen channels rather than the identity of any specific channel.
  2. Affinity: The function is an order-1 polynomial (linear) with respect to the probability of each individual channel being in a "good" state.
  3. Monotonicity: The reward is non-decreasing with respect to the probability of any channel being in a "good" state.

These properties encompass many practical reward structures used in communication networks, such as the probability of successful transmission or the total throughput across multiple channels.

The Optimality Condition

Using backward induction and the structural properties of Partially Observed Markov Decision Processes (POMDPs), the authors prove that if an immediate reward function is "standard," the long-term discounted reward function also maintains these properties.

The central contribution of the paper is the derivation of a closed-form condition for the discount factor, $\beta$. This factor represents how much the decision-maker values future rewards relative to immediate ones. The authors provide a specific inequality (Theorem 1) involving the derivatives of the reward function and the transition probabilities of the underlying Markov chains. If $\beta$ remains below this threshold, the greedy policy is guaranteed to be optimal.

Applications in Cognitive Radio

The theoretical framework is validated through three specific models relevant to Cognitive Radio Networks (CRNs):

  • Sensing Order Problems: The goal is to maximize the probability of finding at least one idle channel among $k$ sensed channels.
  • Linear Access: The reward is the sum of the states of the sensed channels, representing a scenario where multiple channels can be used simultaneously for data transmission.
  • Product Rewards: A reward is only obtained if all $k$ selected channels are in a "good" state, modeling systems that require high-bandwidth synchronization across multiple bands.

Key Results and Implications

The analysis yields several significant insights:

  • The $k=1$ and $k=n-1$ Cases: A particularly striking finding is that for any standard reward function, the greedy policy is optimal for any discount factor ($0 < \beta \leq 1$) when the decision-maker chooses either exactly one channel or all-but-one channel ($n-1$). This holds true even for the average reward criterion, where future rewards are weighted equally with the present.
  • Linear vs. Non-Linear Rewards: For linear reward functions (such as the sum of states), the greedy policy is shown to be optimal for any number of channels $k$ and any discount factor. However, for non-linear rewards (like the "at least one" sensing problem), greed is generally only optimal if the discount factor is sufficiently small or if $k$ falls into the special cases mentioned above.
  • Analytic Robustness: Unlike previous research that relied on complex "coupling arguments," this paper utilizes the analytic properties of reward functions. This approach provides a more robust and generalizable framework for determining policy optimality without the need for extensive simulations.

Limitations and Future Work

While the paper provides a powerful framework, it operates under the assumption that all channels are Independent and Identically Distributed (IID). In many real-world environments, channels exhibit heterogeneous transition probabilities (non-IID). Furthermore, the model assumes a binary state space ("good" or "bad"). Extending these proofs to multi-state systems—where channels might have varying levels of quality or interference—remains a significant challenge for future research.

By identifying the boundaries of greedy optimality, this work provides engineers with a rigorous justification for using simple, myopic strategies in complex restless bandit environments, provided the system parameters fall within the calculated thresholds.

Summary updated

BibTeX
@misc{liu2011optimality,
  author = {Quan Liu and Kehao Wang and Lin Chen},
  title = {{On Optimality of Greedy Policy for a Class of Standard Reward Function of Restless Multi-armed Bandit Problem}},
  year = {2011},
  eprint = {1104.5391},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1104.5391},
}
Figure