Minimizing Cost Rather Than Maximizing Reward in Restless Multi-Armed Bandits

R. Teal Witter, Lisa HellersteinarXiv 2024 · DOI · arXiv

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.

Algorithm 1: The standard Greedy Maximization Heuristic (GREEDYMAX), which serves as a baseline and contrast for the proposed cost-minimization strategies.

The paper introduces two primary alternatives:

  1. Increasing Budget (Alg 3): Gradually expands the budget to favor low-cost actions initially.
  2. 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

Abstract

Restless Multi-Armed Bandits (RMABs) offer a powerful framework for solving resource constrained maximization problems. However, the formulation can be inappropriate for settings where the limiting constraint is a reward threshold rather than a budget. We introduce a constrained minimization problem for RMABs that balances the goal of achieving a reward threshold while minimizing total cost. We show that even a bi-criteria approximate version of the problem is PSPACE-hard. Motivated by the hardness result, we define a decoupled problem, indexability and a Whittle index for the minimization problem, mirroring the corresponding concepts for the maximization problem. Further, we show that the Whittle index for the minimization problem can easily be computed from the Whittle index for the maximization problem. Consequently, Whittle index results on RMAB instances for the maximization problem give Whittle index results for the minimization problem. Despite the similarities between the minimization and maximization problems, solving the minimization problem is not as simple as taking direct analogs of the heuristics for the maximization problem. We give an example of an RMAB for which the greedy Whittle index heuristic achieves the optimal solution for the maximization problem, while the analogous heuristic yields the worst possible solution for the minimization problem. In light of this, we present and compare several heuristics for solving the minimization problem on real and synthetic data. Our work suggests the importance of continued investigation into the minimization problem.
BibTeX
@misc{witter2024minimizing,
  author = {R. Teal Witter and Lisa Hellerstein},
  title = {{Minimizing Cost Rather Than Maximizing Reward in Restless Multi-Armed Bandits}},
  year = {2024},
  eprint = {2409.03071},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2409.03071},
}
Figure