Conditions for indexability of restless bandits and an algorithm to compute whittle index – CORRIGENDUM

Nima Akbarzadeh, Aditya MahajanAdvances 2023 · DOI · OpenAlex

Introduction

The Restless Multi-Armed Bandit (RMAB) problem is a fundamental framework in stochastic scheduling and resource allocation. It models scenarios where multiple projects (arms) change state independently, even when not actively engaged. To manage these systems efficiently, researchers use the Whittle index—a priority score that determines the optimal arm to activate at any given time.

In 2022, Akbarzadeh and Mahajan proposed an efficient $O(K^3)$ algorithm (where $K$ is the number of states) to compute these indices, relying on the Sherman–Morrison formula for fast matrix updates. This corrigendum addresses a critical mathematical error in the original update formula, ensuring the algorithm's robustness and accuracy for practical applications like sensor networking and clinical trial management.

The Mathematical Correction

The core of the correction involves the Sherman–Morrison formula, which allows for the efficient computation of a matrix inverse after a rank-1 change. In the context of RMABs, as the algorithm iterates through different states to find the Whittle index, the underlying transition matrices change slightly.

The original publication contained an error in Equation (19), which defines the update rules for two intermediate variables, $D^{(h_d,y)}$ and $N^{(h_d,y)}$. These variables are essential for determining the "break-even" point—the Whittle index—where a decision-maker would be indifferent between activating an arm or leaving it idle. The corrected formula now properly balances the terms in the numerator and denominator, ensuring the Sherman-Morrison update aligns with the fundamental theoretical framework (specifically Equations (8) and (18)) of the original study.

Geometric Consistency and the Whittle Index

A significant part of the corrigendum involves ensuring the geometric interpretation of the algorithm remains consistent with the mathematical proofs. The Whittle index can be visualized as the intersection of lines representing different policies in the space of value functions versus the subsidy $\lambda$.

Relationship between the value function $J_\lambda(x)$ and the subsidy $\lambda$, showing the intersection points $\lambda_c$ that define the Whittle index.

As shown in the figure above, the value function $J_\lambda(x)$ is piecewise linear due to the finite state space $\mathcal{X}$. The correction ensures that the visual representation of the Whittle index (as the intersection points $\lambda_c$ of lines representing different policies) matches the mathematical results. This visual alignment is vital for researchers proving the convergence of similar algorithms.

Key Results and Numerical Impact

The paper provides concrete numerical corrections for a sample problem with states $x \in \{1, 2, 3\}$. For a specific state $y=2$, the corrected intermediate value $D^{(h_{2,2})}$ is now identified as $[-0.21, -0.22, -0.37]$, resulting in a Whittle index of 0.8.

Furthermore, the paper corrects specific matrix values for $Z^{[g]}$ and $\tilde{Z}^{[g]}$, which are vital for anyone attempting to implement the algorithm in code. These adjustments ensure that the $O(K^3)$ algorithm remains a reliable tool for researchers and practitioners alike.

Conclusion

While the core logic of the original 2022 paper remains sound, these specific mathematical adjustments are necessary for the algorithm's practical accuracy. By securing the foundation of the existing $O(K^3)$ algorithm, this corrigendum enables future work to scale these methods to even larger state spaces or more complex constrained RMAB problems.

Summary updated

Abstract

Abstract This note corrects an error in the formula to obtain the Whittle index using the Sherman–Morrison formula in Akbarzadeh and Mahajan (2022). Also, some other minor typos are highlighted.
BibTeX
@inproceedings{akbarzadeh2023conditions,
  author = {Nima Akbarzadeh and Aditya Mahajan},
  title = {{Conditions for indexability of restless bandits and an algorithm to compute whittle index – CORRIGENDUM}},
  booktitle = {Advances},
  year = {2023},
  doi = {10.1017/apr.2022.77},
}
Figure