Index policies for discounted bandit problems with availability constraints

Savaş Dayanik, Warren B. Powell, Kazutoshi YamazakiAdvances 2008 · DOI

Abstract

A multiarmed bandit problem is studied when the arms are not always available. The arms are first assumed to be intermittently available with some state/action-dependent probabilities. It is proven that no index policy can attain the maximum expected total discounted reward in every instance of that problem. The Whittle index policy is derived, and its properties are studied. Then it is assumed that the arms may break down, but repair is an option at some cost, and the new Whittle index policy is derived. Both problems are indexable. The proposed index policies cannot be dominated by any other index policy over all multiarmed bandit problems considered here. Whittle indices are evaluated for Bernoulli arms with unknown success probabilities.

Introduction

In the classical multiarmed bandit (MAB) framework, a decision-maker selects one of $N$ arms at each time step to maximize the expected total discounted reward. The Gittins index has long been the gold standard for solving these problems, providing an optimal strategy under the assumption that arms are always available and only change state when played. However, real-world applications—such as scheduling maintenance, managing construction projects subject to weather, or navigating volatile supply chains—frequently violate these assumptions. In these scenarios, options (arms) may be intermittently unavailable or may break down entirely.

This research extends the MAB framework to address these "restless" characteristics, where an arm's state can change even when it is not being played. The authors specifically investigate two scenarios: intermittent availability based on state-dependent probabilities and a breakdown/repair model where availability can be restored at a cost.

Problem Formulation

The paper addresses two distinct versions of the availability-constrained bandit problem:

  1. Intermittent Availability: Arms are not always accessible for selection. The probability of an arm being available depends on its current state and the action taken. This reflects scenarios like a job queue where certain tasks are temporarily blocked.
  2. Breakdown and Repair: Arms can transition into a "broken" state. While in this state, they cannot be played for reward, but the decision-maker has the option to pay a "repair cost" to attempt to bring the arm back online. This introduces a trade-off between immediate expenditure and future potential gains.

Methodology: The Whittle Index Approach

Because these scenarios fall under the umbrella of Restless Bandit Problems (RBP), which are known to be PSPACE-hard, the authors utilize the Whittle index. The Whittle index generalizes the Gittins index by introducing a "subsidy for retirement." This subsidy is the theoretical payment required to make a decision-maker indifferent between playing an arm and letting it rest.

Key Theoretical Contributions

  • Proof of Non-existence: The authors mathematically demonstrate that no single index policy can be universally optimal for every instance of an availability-constrained MAB. This justifies the search for robust, high-performing heuristic policies like the Whittle index.
  • Indexability: A critical requirement for the Whittle index to be valid is "indexability," which ensures that as the retirement subsidy increases, the set of states in which it is optimal to rest the arm also increases. The authors prove that both the intermittent availability and breakdown/repair models are indexable.
  • Restart-in Formulation: To overcome the computational hurdles of calculating indices in complex state spaces, the authors developed a "restart-in" formulation. This approach transforms the dynamic programming problem into a more manageable structure solvable via value iteration.

Key Insights and Results

The research yields several intuitive yet mathematically rigorous insights into decision-making under uncertainty:

  • The Pessimism of Unavailability: When arms are likely to become unavailable, the Whittle index naturally encourages a more "short-sighted" strategy. It prioritizes immediate, certain rewards over long-term exploration, as the opportunity to exploit an arm in the future is not guaranteed. The classical Gittins index fails to account for this risk.
  • Repair as a Strategic Action: In the breakdown model, the Whittle index effectively treats repair as an investment. It weighs the immediate cost against the "option value" of the arm's future availability.
  • Empirical Performance: Through numerical simulations using Bernoulli arms (with success probabilities modeled via Beta distributions), the Whittle index policy consistently outperformed the Gittins index. In a 12-arm simulation of intermittent availability, the Whittle policy achieved a reward of approximately 6.93, compared to 6.56 for the Gittins policy.
  • Non-Dominance: The authors prove their Whittle policies are "non-dominated," meaning no other index policy can perform better across all possible instances of the problems studied.

Conclusion

This work provides a robust framework for managing multiarmed bandits in environments where availability is not guaranteed. By proving indexability and providing an efficient calculation method through the restart-in formulation, the authors bridge the gap between theoretical MAB models and practical resource allocation problems. While challenges remain regarding computational complexity in massive state spaces and the nuances of partially observable availability, the Whittle index policy stands as a superior alternative to classical methods in constrained environments.

Summary updated

Abstract

A multiarmed bandit problem is studied when the arms are not always available. The arms are first assumed to be intermittently available with some state/action-dependent probabilities. It is proven that no index policy can attain the maximum expected total discounted reward in every instance of that problem. The Whittle index policy is derived, and its properties are studied. Then it is assumed that the arms may break down, but repair is an option at some cost, and the new Whittle index policy is derived. Both problems are indexable. The proposed index policies cannot be dominated by any other index policy over all multiarmed bandit problems considered here. Whittle indices are evaluated for Bernoulli arms with unknown success probabilities.
BibTeX
@inproceedings{dayanik2008index,
  author = {Savaş Dayanik and Warren B. Powell and Kazutoshi Yamazaki},
  title = {{Index policies for discounted bandit problems with availability constraints}},
  booktitle = {Advances},
  year = {2008},
  doi = {10.1239/aap/1214950209},
}
Figure