PaperlayerView exact revision on arXiv

Source-linked AI summary

Asymptotically optimal priority policies for indexable and nonindexable restless bandits

I. M. Verloop

arXiv:1609.00563v1math.PR

TL;DR

Optimal control of restless bandits is typically intractable, motivating policies with provable asymptotic guarantees. The paper develops priority policies for fixed and dynamic populations and uses fluid scaling and linear programming to analyze them. Under stated conditions they are asymptotically optimal, and for indexable bandits Whittle’s policy is among them.

  • Problem

    Finding optimal control for restless bandits is typically intractable, and asymptotic guarantees for Whittle’s policy need extension to multiple classes and arriving bandits.

    Source: §5.1 · p. 17

  • Method

    The paper combines fluid-scaling and linear-programming techniques to derive priority policies for fixed or dynamic populations, without requiring indexability.

    Source: §1 · p. 4, §9 · p. 34

  • Results

    Under a global-attractor property and technical conditions, the priority policies are asymptotically optimal, and Whittle’s policy is included for indexable bandits.

    Source: §1 · p. 4

  • Takeaways & Limitations

    The framework covers nonindexable systems and extends Whittle-policy asymptotic results to multiple classes, arrivals, and multiple actions.

    Source: §1 · p. 4, §9 · p. 34

    The guarantees require technical conditions, including a global attractor; without the relevant condition, optimal fluid behavior may cycle, be chaotic, or converge to a nonoptimal equilibrium.

    Source: §1 · p. 3, §6 · p. 25

Abstract

from arXiv · show

We study the asymptotic optimal control of multi-class restless bandits. A restless bandit is a controllable stochastic process whose state evolution depends on whether or not the bandit is made active. Since finding the optimal control is typically intractable, we propose a class of priority policies that are proved to be asymptotically optimal under a global attractor property and a technical condition. We consider both a fixed population of bandits as well as a dynamic population where bandits can depart and arrive. As an example of a dynamic population of bandits, we analyze a multi-class $\mathit{M/M/S+M}$ queue for which we show asymptotic optimality of an index policy. We combine fluid-scaling techniques with linear programming results to prove that when bandits are indexable, Whittle's index policy is included in our class of priority policies. We thereby generalize a result of Weber and Weiss [J. Appl. Probab. 27 (1990) 637-648] about asymptotic optimality of Whittle's index policy to settings with (i) several classes of bandits, (ii) arrivals of new bandits and (iii) multiple actions. Indexability of the bandits is not required for our results to hold. For nonindexable bandits, we describe how to select priority policies from the class of asymptotically optimal policies and present numerical evidence that, outside the asymptotic regime, the performance of our proposed priority policies is nearly optimal.

1. Introduction.

The paper develops asymptotically optimal priority policies for multi-class restless bandits with fixed or dynamic populations, including settings that are not indexable. Under indexability, Whittle’s index policy belongs to this class, extending earlier asymptotic results to arrivals and multiple actions.

1. Introduction.

  • For nonindexable bandits, the authors describe how to choose policies from the asymptotically optimal class and report near-optimal performance outside the asymptotic regime in an example.The class of policies does not rely on indexability.Source: §1 · pp. 3–4
  • Allowing fewer than α active bandits is handled with dummy bandits, so the policy activates bandits with the largest strictly positive Whittle indices and leaves negative-index states passive.The restless setting is difficult because bandits may change state while passive.Source: §1 · pp. 2–3
  • The proof combines fluid scaling and linear programming: an optimal fluid equilibrium yields priority policies whose scaled cost matches an LP lower bound.A reformulated relaxed LP connects Whittle’s policy to the fluid LP, allowing the proof to include arrivals unlike the approach in.Source: §1 · pp. 3–4
  • The proposed priority policies are asymptotically optimal for possibly nonindexable, fixed- or dynamic-population bandits when a global attractor and technical conditions hold.The paper also establishes those technical conditions for fixed populations under a unichain assumption and for dynamic populations when passive bandits eventually leave.Source: §1 · p. 4
  • For indexable bandits, Whittle’s index policy is included among the asymptotically optimal priority policies for both fixed and dynamic populations.This extends Weber and Weiss to multiple classes and arrivals; the results also extend to multiple actions per bandit.Source: §1 · pp. 2–4

2. Related work.

Related work covers index policies for restless bandits, prior asymptotic results, dynamic-population models, and LP approaches. The paper’s setting builds on these lines while addressing multiple classes, arrivals, multiple actions, and nonindexable systems.

2. Related work.

  • Gittins’ index policy is optimal for the nonrestless problem when α = 1, while Whittle’s restless-bandit policy extends to multiple actions [20] and has been applied across scheduling and communication settings.For α > 1, Gittins-policy optimality requires additional conditions in some settings.Source: §2 · pp. 4–5
  • For fixed populations, prior results establish Whittle-index optimality in specific models, while Weber and Weiss prove asymptotic optimality for symmetric bandits under a global-attractor condition.Other asymptotic studies include multiple activation levels and a two-class model with a recurrence condition.Source: §2 · p. 5
  • Prior dynamic-population studies are few; work on wireless channels and impatient-customer queues examined index policies, and established maximum stability and asymptotic fluid optimality under a different scaling.In, at most one bandit is active at a time, whereas the scaling in and this paper allows the active-bandit count to grow.Source: §2 · pp. 5–6
  • A fixed-population model can represent arrivals of entities through bandit states, but its Whittle index may depend on arrival characteristics and system population, unlike the dynamic-population formulation.Prior work found Whittle-index optimality in light- and heavy-traffic limits.Source: §2 · p. 6
  • Earlier nonindexable heuristics include a primal–dual index with a sub-optimality guarantee and fair-charge policies for make-to-stock systems.An adapted primal–dual heuristic is included in this paper’s priority-policy class, whereas the heuristic in is not.Source: §2 · p. 6
  • LP methods have been used to characterize or compute indexability and to derive discounted-cost performance bounds.The paper uses LP techniques as part of its asymptotic-optimality proof.Source: §2 · p. 6

3. Model description.

The model is a continuous-time, multi-class restless-bandit system with constrained activation, state transitions, and optional arrivals and departures. It evaluates policies by stability and long-run average holding cost, with fixed and dynamic population cases.

3. Model description.

  • The model has K continuous-time bandit classes, each with finitely many states; class-k arrivals are Poisson with rate λk and enter state j with probability pk(j).Under action a, a bandit transitions between states at exponential rates qk(j|i,a), and state 0 denotes departure.Source: §3 · pp. 6–7
  • At each decision epoch—an arrival, state change, or departure—a policy selects active bandits subject to the constraint that at most α are active.Bandits may also evolve under the passive action, which is the restless feature.Source: §3 · pp. 7–8
  • A fixed population has no arrivals or departures, whereas a dynamic population has arrivals and permits bandit departures.The model description sets λk = 0 and qk(0|j,a) = 0 for fixed populations; dynamic populations have positive arrival rates and at least one possible departure state and action per class.Source: §3 · p. 7
  • The performance criteria are stability and long-run average holding cost, and the objective is to find a Markovian policy that minimizes average cost subject to the activation constraint.For fixed populations, the finite state space makes a unichain process sufficient for stability; dynamic-population stability is more involved and policy-dependent.Source: §3 · pp. 7–8
  • Although the model focuses on passive and active actions, its results extend to multiple actions when policy definitions are modified accordingly.The standard fixed-population formulation requiring exactly α active bandits can be recovered by adding a sufficiently large passive-action cost.Source: §3 · pp. 8–9

4. Fluid analysis and asymptotic optimality.

The section formulates a mean-drift fluid control problem whose optimum lower-bounds stochastic costs and uses its optimal equilibria to derive priority policies. It proves that, under stated attraction and technical conditions, these policies attain the fluid-scaled optimum in steady state as the scaling grows.

4.1. Fluid control problem and lower bound.

  • The mean-drift fluid control problem is an LP whose optimum lower-bounds stochastic-model cost for fixed populations and, under stated stability conditions, dynamic populations.For dynamic populations, the lower-bound relation holds when the policy is stable, or mean rate-stable with strictly positive holding costs.Source: §4.1 · p. 11

4.2. Priority policies.

  • Priority policies order states using optimal fluid equilibria, require no indexability, and include Whittle’s index policy when the system is indexable.The policy activates as many bandits as possible in the highest-priority states; the equilibrium-based ordering ranks states according to their active and passive fluid allocations.Source: §4.2 · pp. 11–12

4.3. Asymptotic optimality of priority policies.

  • The asymptotic result uses fluid scaling of arrivals, activation capacity, and initial populations by r; priority policies are invariant to that scaling.For dynamic populations, examples satisfying the technical condition include systems where passive bandits eventually leave, and systems allowing only active bandits.Source: §4.3 · pp. 14–15
  • As r grows, a policy from Π* achieves the fluid optimum v*(x) when its equilibrium is a global attractor and Condition 4.12 holds.Condition 4.12 requires a unique invariant distribution with finite first moment for each r, plus tightness and uniform integrability of the distribution family.Source: §4.2 · p. 14, §4.3 · pp. 15–16
  • For π∗∈Π(x∗), the fluid-scaled steady-state queue converges to x∗, so its cost converges to the LP value v∗(x), a lower bound on average cost.This establishes asymptotic optimality of the priority policy π∗.Source: §4.3 · p. 16

5. Whittle’s index policy.

The section derives Whittle’s index policy from a relaxed-constraint problem and establishes conditions under which it is asymptotically optimal for fixed and dynamic populations. For populations with arrivals, the policy uses limiting discounted indices.

5.1.1. Relaxed-constraint optimization problem.

  • The relaxed-constraint problem replaces the instantaneous activation limit with a time-average or discounted constraint, whose optimal cost lower-bounds costs under the original constraint.A Lagrange multiplier acts as a cost per active bandit, allowing the problem to decompose into bandit-specific subproblems.Source: §5.1.1 · pp. 17–18
  • Dummy bandits represent unused activation capacity, allowing the formulation to handle policies that activate fewer than α bandits.Their zero index means real bandits with nonpositive indices remain passive.Source: §5.1.1 · pp. 17–19

5.1.2. Whittle’s index policy as heuristic.

  • Whittle’s index policy activates bandits with the highest nonnegative indices, so fewer than α may be activated when remaining indices are nonpositive.With multiple actions, the result applies under the stronger indexability condition that specifies an optimal activation mode.Source: §5.1.2 · p. 20

5.2. Asymptotic optimality for a fixed population of bandits.

  • For fixed populations, Whittle’s index policy is asymptotically optimal when the bandits are indexable for average cost and the stated unichain and technical conditions hold.The policy is shown to belong to the asymptotically optimal priority-policy set.Source: §5.2 · p. 21

5.3. Asymptotic optimality for a dynamic population of bandits.

  • For dynamic populations, a policy using limiting discounted Whittle indices is asymptotically optimal under the stated indexability, boundedness, and technical conditions.The limiting index is formed along a subsequence as the discount factor decreases to zero.Source: §5.3 · pp. 22–23
  • For dynamic populations, the limiting-index policy is robust: it does not depend on arrival characteristics or the exact activation capacity.The proof approach reformulates the relaxed problem as a linear program, allowing arrivals to be included.Source: §5.3 · p. 23

6. On the global attractor property.

The asymptotic-optimality argument relies on a global attractor for the fluid process under a priority control. When that property fails, the optimal fluid control may require transient behavior that the priority-policy argument does not capture.

6. On the global attractor property.

  • For fixed populations, the required global-attractor condition coincides with the condition used by Weber and Weiss.That work also gave an example where Whittle’s index policy is not asymptotically optimal.Source: §6 · p. 23
  • The global attractor property ensures that the priority control reaches an optimal fluid equilibrium, thereby solving the fluid control problem.The approach selects an optimal equilibrium and builds a priority policy around it rather than solving the transient fluid-control problem directly.Source: §6 · p. 24
  • Without the property, an optimal fluid control may be cyclic, chaotic, or converge to a nonoptimal equilibrium, requiring analysis of its transient behavior and translation to the stochastic model.The paper leaves this analysis for future research.Source: §6 · pp. 24–25

7. Case study: A multi-server queue with abandonments.

The case study applies the restless-bandit framework to a multi-class multi-server queue with abandonments. Its index policy is asymptotically optimal under the paper’s conditions, with an index that measures per-unit-time cost reduction from service.

7. Case study: A multi-server queue with abandonments.

  • The policy serves at most S customers with the highest strictly positive class indices; customers in negative-index classes are never served.When class indices are strictly ordered, this policy coincides with the limiting Whittle index policy.Source: §7 · p. 26
  • The class index represents the reduction in cost per time unit when a customer is made active rather than passive.The rule does not depend on arrival rates or the number of servers.Source: §7 · p. 26
  • Solving the queue’s linear program places the index policy in the asymptotically optimal priority-policy set.When the class indices are strictly ordered, it has the same priority ordering as Whittle’s limiting index policy.Source: §7 · pp. 26–27
  • The queue index policy is asymptotically optimal as the number of servers and arrival rates scale by r and r tends to infinity.The proof establishes that the policy lies in the priority-policy set, has a unique global attractor, and satisfies the technical condition.Source: §7 · pp. 27–28
  • In the cited underload setting with zero service holding cost, every nonidling policy has zero equilibrium cost, so the asymptotic optimality result is not informative there.The paper contrasts this with overload, where the fluid-scaled cost is nonzero.Source: §7 · p. 28

8. Nonindexable restless bandits.

The section gives a way to select among asymptotically optimal priority policies for nonindexable bandits and evaluates those choices outside the asymptotic regime. In the example, selected policies have the smallest sub-optimality gaps, while gaps for alternative policies can be made arbitrarily large.

8.1. Policy selection.

  • The set Π* can contain multiple policies, and the selection method chooses among them as α changes.For indexable problems Whittle’s index policy is one choice in Π*(α), but this need not hold for nonindexable problems.Source: §8.1 · p. 29, §8 · p. 29
  • The selection method assigns priority according to the LP solution’s high- and low-priority states, with low-priority states activated only under specified capacity conditions.It holds the chosen policy constant across intervals of α where the LP’s binding constraints and optimal-solution basis do not change.Source: §8.1 · pp. 29–30

8.2. Performance evaluation.

  • The numerical evaluation tests priority policies outside the asymptotic regime at α = 1 (at most one bandit active at a time), varying the number of bandits X(0), and uses numerically obtained optimal basic solutions of (LP).For 4 ≤ x(0) ≤ 7, the authors focus on policy prio21.Source: §8.2 · pp. 31–32
  • The selected policies have the smallest relative sub-optimality gaps across the evaluated values of x(0).Figure 1 compares policies at α = 1, with x(0) on the horizontal axis.Source: §8.2 · p. 32, Figure 1 · p. 33
  • In the example, the selected policies outperform prio123 and prio213, and parameter changes can make their sub-optimality gap arbitrarily large.For fixed X(0), the gap grows linearly with C(3,1); the illustrated change sets C(3,1) = 5 and q(1|3,1) = q(2|3,1) = 0.001.Source: §8.2 · pp. 32–33, Figure 2 · p. 33

9. Conclusion and further research.

The paper presents a unified LP-based approach to asymptotically optimal priority policies for fixed and dynamic populations, without requiring indexability. Its guarantee relies on a global attractor property, and the conclusion identifies models outside that condition and broader multi-action settings as topics for further work.

9. Conclusion and further research.

  • The LP-based class Π* applies to fixed and dynamic populations without requiring indexability, and contains Whittle’s index policy when the bandits are indexable.The paper identifies understanding performance outside the asymptotic regime as future work.Source: §9 · p. 34
  • The global attractor property is crucial to the proof of asymptotic optimality, and characterizing policies for models that lack it remains an open research direction.The paper also calls for sufficient conditions guaranteeing that policies in Π* have the property.Source: §9 · p. 34
  • The authors identify broader multi-action models as a future extension; this paper discusses the case where each action has weight 1.They contrast this with prior work investigating index-policy asymptotic optimality for weights equal to the action value.Source: §9 · p. 34

APPENDIX A: PROOF OF LEMMA 4.1

  • The proof excerpt establishes that the optimal LP value is finite when the feasible set is nonempty and the objective minimizes cost.This excerpt states the conclusion without the preceding proof details.Source: Appendix A · p. 35

APPENDIX B: PROOF OF LEMMA 4.3

The proof uses time-averaged state-action behavior to relate policies to the LP. It treats fixed populations and dynamic populations under stability assumptions.

APPENDIX B: PROOF OF LEMMA 4.3

  • For a fixed population or a dynamic population under a stable policy, the proof considers a subsequence along which the finite long-run average cost is approached.It then extracts a further subsequence on which time-averaged state-action quantities converge.Source: Appendix B · p. 36
  • The proof concludes that the limiting policy occupation values are feasible for the LP, yielding the stated comparison with the LP optimum.The dynamic-population argument also assumes strictly positive costs for every class, state, and action.Source: Appendix B · p. 36
  • For dynamic populations, the proof uses rate stability to make the normalized state counts vanish in the limit.The text says the mean-rate-stability case follows along similar lines and omits its proof.Source: Appendix B · p. 37

APPENDIX C: PROOF OF PROPOSITION 4.13

The proof establishes stability for the relevant dynamic-population process using drift arguments, then bounds passive-bandit counts to obtain tightness and uniform integrability.

APPENDIX C: PROOF OF PROPOSITION 4.13

  • A multi-step drift criterion yields a unique invariant distribution once the process has negative drift outside a compact set.The proof first assumes irreducibility for the priority policy under consideration.Source: Appendix C · pp. 37–38
  • When the stopping time until an active bandit becomes passive has finite expectation, passive bandits depart with positive probability, yielding negative drift for sufficiently large populations.The proof bounds the stopping-time expectation uniformly and uses a positive lower bound on the departure probability.Source: Appendix C · pp. 37–38
  • If that stopping time has infinite expectation in some state, the passive-bandit population behaves as an M/G/∞ queue, which the proof uses to establish stability.The argument also invokes irreducibility to reach the relevant state in finite expected time.Source: Appendix C · p. 37
  • Passive-bandit counts are bounded by an M/G/∞ queue, whose stationary Poisson scaling supports tightness and uniform integrability.The proof uses the passive transition rates to define service requirements and bounds arrivals using the maximum active transition rate.Source: Appendix C · p. 38

APPENDIX D: PROOF OF PROPOSITION 4.14

The proof models the priority-policy process as a density-dependent population process and uses the global-attractor condition to show its fluid limit converges to the optimal state. This convergence makes the steady-state cost attain the lower bound.

APPENDIX D: PROOF OF PROPOSITION 4.14

  • The process under the priority policy is a density-dependent population process, with transition rates of the form r b_l(x).This representation supports applying fluid-scaling results to the process.Source: Appendix D · p. 39
  • The fluid limit has the unique global attractor x*, so the scaled stationary distribution converges to a Dirac measure at x*.The proof uses tightness of the stationary distributions and the global-attractor condition.Source: Appendix D · p. 39
  • The steady-state cost converges to the cost at x*, which is a lower bound on steady-state cost and therefore establishes asymptotic optimality.The limit-and-summation step uses uniform integrability; the lower-bound claim follows from Lemma 4.3.Source: Appendix D · pp. 39–40

APPENDIX E: PROOF OF PROPOSITION 5.6

The proof formulates the relaxed optimization problem as a linear program using state-action frequencies. For indexable bandits, the relaxed optimum supplies a priority policy containing Whittle’s index policy.

APPENDIX E: PROOF OF PROPOSITION 5.6

  • The relaxed optimization problem is formulated as a linear program in stationary state-action frequencies.Symmetry for bandits in the same class allows the frequency constraints to be written by class.Source: Appendix E · p. 40
  • An optimal policy for the relaxed problem yields state-action frequencies that solve the corresponding LP, and rescaling them by the initial class populations gives an optimal solution of the fluid LP.The proof uses the correspondence between feasible LP solutions and stationary policies.Source: Appendix E · p. 41
  • Whittle’s index policy belongs to the priority-policy set when the relaxed optimum is used to define its state target.The proof handles states with nonpositive indices by showing they are never activated.Source: Appendix E · pp. 41–42

APPENDIX F: PROOF OF PROPOSITION 5.9

The proof constructs an optimal solution of the fluid LP from per-class discounted problems and shows that an indexable bandit’s Whittle policy meets the priority-policy conditions. This establishes its inclusion in the asymptotically optimal class.

APPENDIX F: PROOF OF PROPOSITION 5.9

  • Uniformization converts the continuous-time discounted finite-state bandit problem into a discrete-time discounted problem for the LP construction.The passage identifies the discount factor as part of this transformation.Source: Appendix F · p. 42
  • Indexability makes the optimal action in each bandit subproblem follow a priority ordering based on its index.The proof uses discounted index thresholds to construct per-class optimal solutions.Source: Appendix F · pp. 42–43
  • The proof obtains a common threshold ν* and combines per-class optimal solutions into an optimal solution of the fluid LP.The per-class solutions are selected through a limiting argument for the perturbed discounted problems.Source: Appendix F · pp. 43–44
  • The Whittle index policy is included in the priority-policy set for an optimal fluid-LP solution.The proof chooses a common index threshold and verifies that the policy does not activate states whose index is below the threshold.Source: Appendix F · pp. 44–45

APPENDIX G: PROOF OF LEMMA 8.1

The appendix establishes a structural property of optimal LP solutions and verifies the global-attractor condition for the multi-class M/M/S+M queue. These results support the priority-policy proof and its queueing example.

APPENDIX G: PROOF OF LEMMA 8.1

  • An optimal basic feasible solution of the fluid LP can be chosen to satisfy the property in Definition 4.4.The proof uses basic solutions and, when needed, a perturbation argument followed by a limit to an optimal solution of the unperturbed LP.Source: Appendix G · pp. 46–47

APPENDIX H: CONDITION ?? FOR AN M /M /S + M QUEUE

  • For the multi-class M/M/S+M queue, the equilibrium is a global attractor, as established by adapting the result in with service rates μ_i+θ̃_i.The appendix also states that the ODE has a unique equilibrium point.Source: Appendix H · p. 48

Related papers

Loading 1609.00563v1…