Abstract
Restless Multi-Armed Bandits (RMABs) are typically used to maximize rewards under a fixed budget. However, in critical domains like healthcare and wildlife conservation, the primary objective is often to reach a specific goal at the lowest possible cost. This paper introduces the RMAB minimization problem, establishing its PSPACE-hardness and a mathematical link between maximization and minimization indices. We propose several heuristics, most notably "Truncated Reward," designed to avoid high-risk, high-cost actions. Our results on real-world healthcare data and synthetic benchmarks show that prioritizing reliability over expected value leads to significantly lower costs in stochastic environments.
Introduction
Traditional RMAB models ask: "Given a budget $X$, how can I maximize my reward?" While useful, this framing is often backwards for high-stakes interventions. For instance, in patient care, the goal is to achieve stability, not to spend a specific amount of money. Stopping treatment because a budget is reached—regardless of the patient's state—is unethical. Conversely, achieving stability at the lowest cost is a vital operational goal. This paper shifts the focus from reward maximization to cost minimization to reach a target reward threshold.
Complexity and Theoretical Foundations
The authors prove that the RMAB minimization problem is PSPACE-hard, even for approximation. A key theoretical contribution is the Whittle Index Link. If a problem is indexable, the maximization index ($\lambda^+$) and the minimization index ($\lambda^-$) share a reciprocal relationship: $\lambda^+ = 1/\lambda^-$. This bridge allows the application of existing RMAB maximization literature to the minimization context.
Proposed Heuristics
To address the computational hardness, the authors introduce several heuristics. While standard greedy approaches, such as the Greedy Maximization Heuristic (GREEDYMAX) shown in Algorithm 1, are effective for maximization, they often fail in minimization scenarios where reward variance is high.
The paper introduces two primary alternatives:
- Increasing Budget (Alg 3): Gradually expands the budget to favor low-cost actions initially.
- Truncated Reward (Alg 4): The primary innovation. By capping rewards at the threshold, it prevents the algorithm from being lured by high-payoff but low-probability "lottery" actions. This ensures the selection of reliable actions that consistently move the system toward the goal.
Experimental Evaluation
The heuristics were tested on two main datasets:
- National Inpatient Sample (NIS): Real-world healthcare data where actions are elective care and rewards are improvements in patient severity.
- Hidden Two-State MDPs: Synthetic benchmarks including "Adversarial" setups with unreliable bandits that provide high but infrequent rewards.
Key Results and Insights
- The "Greedy Trap": In adversarial environments, standard greedy maximization (Alg 1) performs poorly because it repeatedly selects high-reward bandits that rarely pay out, leading to excessive costs. In contrast, the Truncated Reward heuristic excels by favoring reliability.
- Reliability over Expectation: In minimization, variance is a critical risk factor. A "boring" action with a guaranteed small reward is often superior to an "exciting" one with a high average but high failure rate.
- Cost of Certainty: Experiments show that as the required success probability ($\rho$) increases, the discounted cost rises sharply, quantifying the price of certainty in stochastic systems.
Conclusion
This work provides a robust framework for cost-minimization in RMABs, bridging the gap between theoretical indexability and practical, reliable decision-making. Future work will focus on removing the dependency on reward simulations and exploring more complex cost structures, such as time-varying costs.
Summary updated