Abstract
Due to its application in numerous engineering problems, the restless multi-armed bandit (RMAB) problem is of fundamental importance in stochastic decision theory. However, solving the RMAB problem is well known to be PSPACE-hard, with the optimal policy usually intractable due to the exponential computation complexity. A natural alternative approach is to seek simple myopic policies which are easy to implement. This paper presents a generic study on the optimality of the myopic policy for the RMAB problem. More specifically, we develop three axioms characterizing a family of generic and practically important functions termed as regular functions. By performing a mathematical analysis based on the developed axioms, we establish the closed-form conditions under which the myopic policy is guaranteed to be optimal. The axiomatic analysis also illuminates important engineering implications of the myopic policy including the intrinsic tradeoff between exploration and exploitation. A case study is then presented to illustrate the application of the derived results in analyzing a class of RMAB problems arising from multi-channel opportunistic access.
Introduction
The Restless Multi-Armed Bandit (RMAB) problem is a cornerstone of stochastic decision theory, particularly relevant in fields like wireless networking and resource allocation. In an RMAB scenario, a decision-maker chooses a subset of arms to activate, where the state of each arm evolves according to a Markov process regardless of whether it is selected. This "restless" nature makes the problem PSPACE-hard, rendering optimal policies computationally intractable for real-time applications.
Engineers often resort to a myopic policy, a greedy strategy that maximizes immediate rewards. While computationally efficient, its long-term optimality is rarely guaranteed. Previous research has largely focused on simplified versions of the problem, such as those with perfectly observable states or identical (i.i.d.) arms. This paper addresses the more complex and realistic scenario involving heterogeneous (non-i.i.d.) arms and imperfect (noisy) observations.
Methodology: The Axiomatic Approach
The core contribution of this work is the introduction of an axiomatic framework to define a broad class of reward functions, termed $g$-regular functions. These functions are characterized by three fundamental axioms:
- Symmetry: The total reward is invariant to the permutation of the chosen arms.
- Monotonicity: The expected reward increases monotonically with the probability of an arm being in a "good" state.
- $g$-Decomposability: The reward function can be decomposed using a continuous, increasing function $g(\omega)$. This allows the framework to encompass a wide variety of practical utility functions, including logarithmic (e.g., Shannon capacity) and power-law functions.
The system is modeled as a partially observable Markov decision process (POMDP). The decision-maker maintains a "belief vector"—the probability distribution over the states of all arms—which is updated via Bayes' Rule following noisy observations. By employing backward induction on a "pseudo value function," the authors derive conditions under which the myopic policy aligns with the long-term optimal strategy.
Key Results and Insights
The theoretical analysis culminates in two landmark theorems that provide sufficient conditions for myopic optimality:
- Theorem 1 (Finite Horizon): Establishes a closed-form inequality involving the derivatives of the reward function and the transition probabilities of the arms. If satisfied, the myopic policy is optimal for any finite time horizon.
- Theorem 2 (Infinite Horizon): Extends the result to the infinite horizon case by defining a maximum discount factor ($\beta$). This factor represents the weight given to future rewards; below this threshold, the myopic policy remains optimal.
A significant breakthrough is the handling of heterogeneity. Unlike prior literature, these results are valid for non-i.i.d. arms, where each channel can have distinct Markovian transition rates. Furthermore, the authors successfully bound the non-linearity introduced by imperfect sensing, which typically makes belief updates indeterministic.
Discussion and Limitations
While the paper provides a robust theoretical foundation, it notes certain limitations. The derived conditions are sufficient but not necessary, meaning the myopic policy might perform optimally even when these strict criteria are not met. Additionally, the constraints on transition probabilities (specifically $\delta_p^{max} \leq 0.5$) are more restrictive than those in some i.i.d. models to accommodate the added complexity of heterogeneous arms.
Future research directions include extending this framework to multi-user scenarios where competition and collisions introduce further layers of complexity.
Conclusion
This work bridges the gap between abstract RMAB theory and practical engineering by proving the optimality of greedy policies in noisy, heterogeneous environments. By defining $g$-regular functions, the authors provide a versatile tool for analyzing a wide range of real-world utility functions, offering a rigorous justification for the use of simple myopic strategies in complex stochastic systems.
Summary updated