PaperlayerView exact revision on arXiv

Source-linked AI summary

Whittle Index Policy for Three State Collapsing Bandits

Rahul Meshram, Anu Krishna, Kesav Ram Kaza

arXiv:2610.36733v1eess.SYcs.SY

TL;DR

The paper studies three-state partially observable restless bandits, where an arm's state is revealed when activated but remains unobserved when passive. It derives belief-space threshold and indexability conditions and reports simulation comparisons of the Whittle-index, myopic, and round-robin policies.

  • Problem

    Two-state models dominate partially observable RMAB research, while three-state models can represent health-severity levels unavailable in a two-state representation.

    Source: §I · p. 1

  • Method

    The authors analyze three-state collapsing bandits using belief-value and subsidy-sensitivity Lipschitz bounds to derive threshold and indexability conditions.

    Source: 1) Our Contributions · p. 2

  • Results

    The authors establish sufficient conditions for threshold-type optimal policies and arm indexability, and simulations find the Whittle-index policy better than myopic and round-robin under some conditions and at least as good as myopic in others.

    Source: 1) Our Contributions · p. 2, §VII · p. 10

  • Takeaways & Limitations

    The results extend threshold-policy and indexability analysis to three-state collapsing bandits under less restrictive model assumptions.

    Source: 1) Our Contributions · p. 2, §VII · p. 10

Abstract

from arXiv · show

Partially observable restless multi-armed bandit models have been studied for dynamic resource allocation problems under uncertainty. This paper analyzes three-state restless multi-armed bandits with partial observability. These are called collapsing bandit problems if the state of an arm (bandit) is perfectly observable when it is scheduled for allocation. The state is not observable when the arm is not scheduled. The planner has a budget constraint on the scheduling decisions in each time slot. The planner's goal is to maximize expected cumulative long term discounted reward. We study the Whittle index policy. To analyze index policy, first the $N$-armed collapsing bandit problem is decoupled into $N$ single arm problems, and convexity and monotonicity of the optimal value function in belief vector are derived using monotone likelihood ratio (MLR) ordering on state transition dynamics and monotone reward structure assumption. We next show that the optimal policy is of threshold type in belief under sufficiency conditions on the model. These sufficiency conditions depend on Lipschitz bound on the value function in the belief. We further prove the indexability for an arm using Lipschitz bound on subsidy sensitivity with minimal restrictive assumption on the transition probability model and discount factor $\beta.$ Our results generalize to three state and strengthen existing results on threshold policy and indexability with weaker model assumptions. We provide index computation algorithm and we present comparison of the Whittle-index, myopic policy and round-robin policies in the simulation study.

I. INTRODUCTION

The paper extends partially observable restless bandits to three-state collapsing arms, motivated by resource allocation and the limits of two-state models. It develops threshold and indexability results, an index-computation approach, and a model with belief-based decision making under a scheduling budget.

I. INTRODUCTION

  • Three-state collapsing bandits extend two-state models to represent different levels of health severity, while retaining state observation when an arm is active.The paper frames this extension as furthering RMAB applicability to healthcare planning.Source: §I · p. 1, 1) Our Contributions · p. 2, §II · p. 3

A. Related Work

  • Earlier partially observable RMAB research largely focused on two-state models; multi-state indexability results imposed restrictions on the discount factor or transition probabilities.The paper positions its results as broadening indexability conditions to three-state collapsing bandits with TP2 transitions, including β→1.Source: A. Related Work · pp. 1–2

1) Our Contributions:

  • Under MLR transition ordering, monotone rewards, and a Lipschitz bound, the authors establish sufficient conditions for a threshold-type optimal policy in belief space.The results characterize the optimal action regions for the three-state setting.Source: 1) Our Contributions · p. 2
  • A Lipschitz bound on subsidy sensitivity gives a sufficient indexability condition based on the discount factor and the discrepancy between active posterior and passive-prediction beliefs.The paper also establishes indexability for birth-death and restart models, and addresses differentiable and nondifferentiable subsidy points.Source: 1) Our Contributions · p. 2
  • The paper presents two index-computation approaches: two-timescale stochastic approximation and bisection, with bisection using successive interval halving.Both require value-function computation on a faster timescale.Source: 1) Our Contributions · p. 2
  • Simulations with homogeneous and heterogeneous arms report that the Whittle-index policy performs better than myopic and round-robin policies.The conclusion qualifies the comparison: the index policy is better under some conditions and at least as good as myopic in other examples.Source: 1) Our Contributions · p. 2

II. MATHEMATICAL MODEL

  • Each arm has three states and two actions; activation reveals its state, whereas passivity leaves the state unobserved.The arms are assumed independent, and the model uses a partially observable Markov decision process for each arm.Source: §II · p. 3

A. Belief Update

  • After activation and observation, the belief updates to the posterior associated with the observed state; under passivity, it evolves according to passive transitions.Beliefs represent probability distributions over an arm's states when its current state is unobserved.Source: §II · p. 3, A. Belief Update · p. 3

III. DECOUPLING OF RESTLESS MULTI-ARMED BANDIT

The relaxed scheduling problem separates into single-arm problems, enabling analysis through each arm’s belief-state value function. Under stated transition, reward, and Lipschitz conditions, the paper establishes value-function properties and sufficient conditions for threshold-type optimal policies.

III. DECOUPLING OF RESTLESS MULTI-ARMED BANDIT

  • The Lagrangian relaxation decouples the N-arm problem into N single-arm restless bandits.Each arm’s value function depends on its own belief state.Source: §III · p. 4

IV. SINGLE-ARMED RESTLESS BANDIT

  • For fixed λ, the single-arm optimal value function is convex in the belief state.Source: §IV · p. 5
  • Under Assumption 1, the optimal value function is nondecreasing in belief under MLR order.Assumption 1 includes TP2 transitions and monotone state-dependent rewards.Source: §IV · p. 5
  • A reward- and transition-dependent Lipschitz bound on the value function supports the threshold-policy analysis.The bound depends on reward span and transition properties; strict contraction can keep it bounded as β approaches 1.Source: §IV · pp. 5–6
  • Under sufficient conditions, the action advantage is MLR-nondecreasing, yielding a threshold-type optimal policy.The analysis introduces a parameter-dependent Lipschitz constant to address a continuation term whose sign can obstruct the proof.Source: §IV · pp. 5–6
  • The sufficient threshold condition remains bounded as β approaches 1 when the relevant transition contraction is strict.If c = 1 and L_RDΓ > 0, the bound instead diverges as β approaches 1.Source: §IV · p. 6

A. Birth-death model

The section specializes threshold-policy analysis to a three-state birth-death model. Under the stated transition and model conditions, its optimal policy has a threshold structure in MLR order.

A. Birth-death model

  • The three-state birth-death transition matrix under each action uses upward probability p_a, downward probability q_a, and remaining probability 1 − p_a − q_a.Source: A. Birth-death model · p. 6
  • The transition probabilities satisfy p_a, q_a ≥ 0 and p_a + q_a ≤ 1.Source: A. Birth-death model · p. 6
  • With TP2 transition probabilities and Assumption 1, the optimal policy is threshold-type with respect to MLR order.Source: A. Birth-death model · p. 6

B. Restart Model

The paper gives sufficient conditions for indexability using a bound on subsidy sensitivity, and proves a threshold result for a three-state restart model. The indexability criterion depends on model discrepancy and the discount factor, with limits as the discount factor approaches one when discrepancy stays positive.

B. Restart Model

  • For the restart model, the optimal policy is threshold-type in MLR order under Assumption 1.The restart action sends every state to the same distribution γ.Source: B. Restart Model · p. 6
  • The restart model’s identical-row action yields the explicit sufficient criterion md ≥ 2βc_0/(1−βc_0) L_R.The paper contrasts this directly verifiable criterion with the more general structural conditions in.Source: B. Restart Model · p. 6

V. WHITTLE INDEX POLICY AND INDEX COMPUTATION SCHEME

  • Subsidy sensitivity has a uniform Lipschitz bound with L_G = β/(2(1−β)).Source: §V · p. 7
  • If βL_GD_Γ,τ ≤ 1, the subsidy advantage is nondecreasing in λ and the arm is indexable.The condition makes passive sets nondecreasing as the subsidy rises.Source: §V · p. 7
  • For fixed positive D_Γ,τ, the sufficient indexability condition cannot hold for discount factors arbitrarily close to one.When D_Γ,τ = 0, the condition holds for every β in (0, 1).Source: §V · p. 7
  • D_Γ,τ measures the maximal gap between activation-conditioned posterior beliefs and passive predictions; smaller gaps make the indexability condition easier to satisfy.Source: §V · p. 7

A. Whittle Index Computation Algorithm

The Whittle index is computed by finding the subsidy at which the action-value difference reaches zero. The section presents a two-timescale stochastic-approximation method and a bisection alternative that halves a bracketed search interval.

Index definition

  • The Whittle index W(ω) is the subsidy λ where Δ(ω, λ) = Qλ(ω, 0) − Qλ(ω, 1) reaches zero.Because closed-form value functions and indices are unavailable, action values are computed numerically.Source: A. Whittle Index Computation Algorithm · pp. 7–8

Stochastic approximation

  • Stochastic approximation updates the subsidy on a slower timescale while value iteration computes action values on a faster timescale.The method uses positive step sizes; the inner value iteration has tolerance ϵVI, chosen smaller than the index tolerance to limit numerical error.Source: A. Whittle Index Computation Algorithm · p. 8

Bisection method

  • Bisection brackets W(ω) with endpoints whose action-value differences have opposite signs, then halves the interval at each iteration.At each midpoint, value iteration supplies the action values; the sign of Δ determines which endpoint is updated.Source: A. Whittle Index Computation Algorithm · p. 8

Stopping and complexity

  • Bisection stops when the action-value difference or subsidy interval meets its prescribed tolerance, and returns the midpoint as the numerical index.Its accuracy hλ entails logarithmic search complexity in the interval width; stochastic approximation instead has complexity O(NSACVI).Source: A. Whittle Index Computation Algorithm · p. 8

VI. SIMULATION RESULTS

The simulations use a three-state model and include a demonstration of the threshold-type policy alongside comparisons of Whittle-index, myopic, and round-robin policies. In the threshold demonstration, increasing the subsidy expands the passive region.

VI. SIMULATION RESULTS

  • The simulation section compares Whittle-index, myopic, and round-robin policies for homogeneous and heterogeneous arms in the three-state model.The supplied passages describe the comparison scope but do not report which policy performs best.Source: §VI · p. 8

A. Demonstration of threshold-type policy

  • With active rewards [0, 1, 2] and passive rewards [0, 0.8, 1.6], β = 0.99, the discounted Bellman equation is solved by value iteration on a belief-simplex grid of resolution 80 until tolerance 10^-6.Source: A. Demonstration of threshold-type… · p. 9
  • As the subsidy increases from λ = 0.4 to λ = 0.5, the passive set expands across belief states, illustrating indexability.Figure 1 marks passive beliefs in blue, active beliefs in red, and the switching boundary in black.Source: A. Demonstration of threshold-type… · p. 9, Figure 1 · p. 9

B. Performance evaluation of different policies

Across homogeneous and heterogeneous simulations, the Whittle index policy is compared with greedy and round-robin scheduling. The relative performance of the policies varies with the reward structure.

B. Performance evaluation of different policies

  • For homogeneous arms, the Whittle index policy outperforms the myopic policy by looking ahead rather than choosing greedily.The authors relate the gap to contrasting active and passive rewards and transition matrices that pull toward different states.Source: 1) Homogeneous arms · p. 9, Figure 2 · p. 9

2) Heterogeneous arms:

  • For heterogeneous arms, the Whittle index policy performs close to the greedy policy.The authors attribute this to structured transition variation and pronounced reward heterogeneity, which makes instantaneous rewards a strong indicator of arm quality.Source: 2) Heterogeneous arms · p. 10, Figure 3 · p. 10

3) Impact of reward structure on performance with heterogeneous arms :

VII. CONCLUSION

  • The conclusion reports that the index policy is better than myopic and round-robin policies under some conditions and at least as good as myopic in other examples.The authors identify generalized multi-state models and applications to public health as future work.Source: §VII · p. 10

APPENDIX A PROOF OF LEMMA 1

These proof sections develop the single-arm Bellman formulation and bounds used to analyze value-function behavior over beliefs.

APPENDIX A PROOF OF LEMMA 1

  • The proof rewrites the Bellman operator and identifies the single-arm Bellman equation as a step in the argument.For the passive action, belief updates follow τ(ω) = (P 0)^Tω; for the active action, continuation values average over revealed-state beliefs Γi.Source: Appendix A · p. 11, Appendix C · p. 12

APPENDIX C PROOF OF LEMMA 4 (LIPSCHITZ BOUND ON VALUE

  • The value function is Lipschitz in belief, with bound LR/(1−βc) times the ℓ1 distance, where c is the maximum contraction coefficient across actions.The proof uses contraction of passive belief dynamics and a bound on the active continuation operator.Source: Appendix C · p. 12, Appendix B · p. 12
  • Under the stated Lipschitz, monotonicity, and MLR-preservation assumptions, the active continuation term and passive-advantage differences admit bounds in belief distance.For three ordered states, an increasing statewise passive reward advantage has margin md, the minimum gap between adjacent advantages.Source: Appendix C · pp. 12–13

APPENDIX D PROOF OF LEMMA 5

The proofs establish conditions for increasing passive advantage and for a threshold-type optimal policy in the three-state birth-death setting.

APPENDIX D PROOF OF LEMMA 5

  • When the sufficient margin condition holds, the passive-action advantage is increasing in belief for fixed subsidy.The proof combines an increasing statewise reward difference with a bound on continuation-value variation.Source: Appendix E · p. 13

APPENDIX F PROOF OF THEOREM 2

  • For TP2 transition matrices in the three-state birth-death model, the general threshold theorem gives a sufficient condition for an MLR-monotone optimal policy.The proof bounds transition contraction using mP and applies the resulting value-function Lipschitz bound.Source: Appendix F · pp. 13–14

APPENDIX G PROOF OF LEMMA 6

This proof characterizes how the value function responds to subsidy and bounds that sensitivity across belief states.

APPENDIX G PROOF OF LEMMA 6

  • Where the value function is differentiable in subsidy, its derivative equals expected discounted passive occupation time and lies between 0 and 1/(1−β).The bound is uniform over the belief space and all subsidies.Source: Appendix G · p. 14
  • The subsidy sensitivity has Lipschitz constant β/[2(1−β)] in the active region, and the proof extends this bound across regions under its regularity conditions.The argument uses differentiated Bellman equations, contraction of passive belief dynamics, and regularity at optimal-action switching boundaries.Source: Appendix G · pp. 14–15
  • If both beliefs remain in the passive region indefinitely, subsidy sensitivity is constant across them at 1/(1−β).For the admissible-range argument, the condition β^2DΓ,τ ≤ 2(1−β) is stated as equivalent to DΓ,τβ^2 + 2β − 2 ≤ 0.Source: Appendix G · p. 15, PROOF OF DISCREPANCY BOUND 0 ≤DΓ,τ ≤2 · p. 15

APPENDIX I JOINT CONTINUITY OF THE VALUE FUNCTION

The value function is convex and nondecreasing in the subsidy, and its joint continuity in belief and subsidy follows from bounds on its variation in each argument.

APPENDIX I JOINT CONTINUITY OF THE VALUE FUNCTION

  • The argument establishes convexity in belief and subsidy and derives one-sided derivatives in subsidy, with differentiability except at countably many points.The proof takes the supremum over policies and uses bounded rewards with geometric discounting.Source: Appendix I · p. 16
  • For each belief, the value function is finite, convex, nondecreasing, and 1/(1 − β)-Lipschitz in subsidy.The bound follows from the range of discounted passive occupation time.Source: Appendix I · p. 16
  • The value function is jointly continuous in belief and subsidy.The proof combines continuity bounds in the two arguments.Source: Appendix I · p. 16
  • For each fixed policy, the value is convex in subsidy because it is affine in subsidy, and the optimal value is the supremum over policies.The proof uses a common admissible policy class independent of initial belief and subsidy.Source: Appendix I · p. 16

LIPSCHITZ CONSTANT

The section bounds subsidy sensitivity using discounted passive occupation, then controls its variation across beliefs to obtain a conditional indexability criterion. The subdifferential result is local and depends on policy stability assumptions.

LIPSCHITZ CONSTANT

  • 1/(1 − β) bounds subsidy sensitivity for every belief, yielding a universal Lipschitz bound for the optimal value.The bound uses that discounted passive occupation lies between 0 and 1/(1 − β).Source: LIPSCHITZ CONSTANT · p. 17
  • β/[2(1 − β)] bounds how a fixed policy’s discounted passive occupation changes across beliefs when its initial action is belief-independent.The bound is stated for a fixed history-dependent policy with the same deterministic time-zero action under every initial state.Source: LIPSCHITZ CONSTANT · p. 18
  • Under the envelope and common-optimal-policy assumptions, the optimal value’s subsidy subdifferential is Hausdorff-Lipschitz across beliefs in U.The policy family must be optimal throughout U and each policy must have a deterministic initial action independent of initial state.Source: LIPSCHITZ CONSTANT · pp. 17–18
  • The subdifferential-continuity theorem is local to U, not automatically global; policy changes at boundaries need a separate compatibility argument.Assumption 3 is a sufficient policy-stability condition, not a primitive condition on rewards and transition matrices.Source: LIPSCHITZ CONSTANT · p. 19
  • At a boundary between uniquely optimal switching policies, Hausdorff continuity forces their limiting occupation measures to agree.The result assumes continuous limits of those occupation measures.Source: LIPSCHITZ CONSTANT · p. 19
  • If the successor-belief subdifferentials satisfy the stated bound, the passive-minus-active action-value difference is strictly increasing in subsidy.This supplies the single-crossing direction for passive optimality.Source: LIPSCHITZ CONSTANT · p. 19

A. Various bounds on DΓ,τ under different model assumptions

The sufficient indexability condition trades off discount factor and posterior-prediction discrepancy. It yields a transition-matrix-independent discount threshold and increasingly restrictive discrepancy bounds as the horizon lengthens.

A. Various bounds on DΓ,τ under different model assumptions

  • β²DΓ,τ ≤ 2(1 − β) is the sufficient condition, so a smaller belief discrepancy permits a larger discount factor.The discrepancy is bounded above by 2 because the compared beliefs are probability vectors.Source: A. Various bounds on DΓ,τ under… · p. 19
  • β ≤ (√5 − 1)/2 ≈ 0.6180 guarantees the sufficient condition for every three-state transition model, without extra transition-matrix restrictions.This threshold follows from DΓ,τ ≤ 2.Source: A. Various bounds on DΓ,τ under… · p. 19
  • As β approaches 1, the sufficient condition requires DΓ,τ = O(1 − β), with a sufficiently small leading constant.Thus the posterior-prediction discrepancy must decrease approximately linearly with 1 − β.Source: A. Various bounds on DΓ,τ under… · p. 20
  • At β = 0.95, the condition requires DΓ,τ ≤ 0.1108; at β = 0.99, it requires DΓ,τ ≤ 0.0204.The paper notes the latter makes the sufficient condition more restrictive for long-horizon decision makers.Source: A. Various bounds on DΓ,τ under… · p. 20
Loading 2610.36733v1…