PaperlayerView exact revision on arXiv

Source-linked AI summary

Load Balancing with Partial Queue Information - Threshold Optimality and Indexability

Sathwik Chadaga, Eytan Modiano

arXiv:2609.28219v1cs.NI

TL;DR

The paper addresses dispatching when a central dispatcher lacks current queue backlogs, making direct optimal control computationally infeasible. It models the problem as an RMAB using recent observations and their ages, then establishes threshold and indexability results for two queue models. The standard finite-queue model is indexable with a closed-form Whittle index, while blocking-queue indexability is shown for special cases.

  • Problem

    Whittle-index methods are difficult to apply because partially observed queues have multidimensional belief vectors, unlike scalar-belief cases with closed-form relaxed solutions.

    Source: §I · pp. 1–2

  • Method

    The paper models each arm by its most recent backlog observation and its age, then analyzes standard finite and blocking queues through decoupled single-arm problems.

    Source: §I · p. 2, §III · p. 4

  • Results

    The standard finite-queue model is indexable with a closed-form Whittle index, while the blocking-queue model is indexable for K ≤2 and β ≤0.5.

    Source: §I · p. 2, B. Indexability for special cases · p. 6

  • Takeaways & Limitations

    Threshold structure supports a closed-form index policy for standard finite queues, while the blocking-queue conclusion is limited to special cases.

    Source: §I · p. 2

    Extensions to random dispatcher arrivals and exogenous server arrivals remain future work because the transition matrix would not be lower triangular and the value function may not be well behaved.

    Source: §VII · p. 7

Abstract

from arXiv · show

We consider the problem of load balancing in a system with one dispatcher and $N$ parallel servers. The dispatcher must select one server to dispatch new jobs at every time-step and each server buffers incoming jobs in a queue. However, the dispatcher does not know the servers' backlogs and must make dispatching decisions based on previous observations. The dispatcher's objective is to dispatch jobs to the shortest queue. This problem can be formulated as a restless multi-arm bandit (RMAB) problem where each arm's state is its corresponding belief vector. Our goal is to verify Whittle indexability for this problem and derive a low complexity Whittle index policy. Previous Whittle indexability results cannot be directly applied due to the multi-dimensional nature of the belief vector. To overcome this issue, we define the RMAB state as the tuple of the most recent backlog observation and the time since this observation. We consider two model variations, a standard finite queue model and a blocking queue model. We show that the single-arm decoupled problems of both these models have threshold optimal solutions under some assumptions. For the standard finite queue model, we prove indexability and derive the Whittle index policy in closed form. For the blocking queue model, we derive a sufficient condition for indexability under threshold optimality and use it to show indexability for some special cases.

I. INTRODUCTION

The paper studies dispatching when a central dispatcher must choose among parallel queues without knowing their current backlogs. It recasts this partially observed problem as an RMAB and develops indexability results for two queue models.

I. INTRODUCTION

  • JSQ is delay optimal under certain assumptions, but requires all backlogs; probing every server adds communication overhead and motivates scalable alternatives.JSQ-d reduces overhead by probing d randomly selected servers, while JIQ uses idle-server tokens and dispatcher memory.Source: §I · p. 1
  • Belief-based RMAB methods are difficult to apply because each queue’s belief is a K + 1 dimensional vector, unlike the scalar beliefs in cited channel models.The multidimensional belief makes closed-form relaxed Bellman solutions difficult to derive.Source: §I · pp. 1–2
  • The dispatcher must choose a server using past observations because current backlogs are unknown, making optimal dynamic programming computationally infeasible.The objective is to maximize expected total discounted reward while favoring the shortest queue.Source: §I · p. 2
  • The paper represents each arm by its most recent backlog observation and that observation’s age, then studies standard finite and blocking queue models.This replaces the full belief-vector state with an observation-and-age tuple.Source: §I · p. 2
  • For standard finite queues, the paper proves threshold optimality and indexability and derives a closed-form Whittle index; for blocking queues, it proves indexability in special cases.The blocking-queue cases are K ≤2 and β ≤0.5.Source: §I · p. 2

II. PROBLEM FORMULATION

The formulation models partially observed finite-capacity server queues as restless arms. The dispatcher updates its information from the selected server’s acknowledgment and chooses actions to maximize discounted dispatched-job reward.

II. PROBLEM FORMULATION

  • The two queue models dispatch K − Q(t) jobs to fill available capacity, or K jobs only when the selected blocking queue is empty.Their dispatched-job rules are Aπ(Q(t)) = π(t)(K − Q(t)) and Aπ(Q(t)) = Kπ(t)I[Q(t) = 0], respectively.Source: §II · p. 2
  • The dispatcher observes only the selected server’s backlog, while each server has capacity K and evolves through departures and possible exogenous arrivals.The model later assumes zero exogenous arrivals to establish threshold optimality.Source: §II · p. 2
  • A server’s belief vector is sufficient for decision-making and can be represented by its latest observed backlog and the time since that observation.For an unselected server, the age increases; after selection, the observation and age are reset using its newly observed backlog.Source: §II · p. 3
  • The resulting state is each server’s observation-age tuple, and servers continue evolving even when unselected, making the system a restless multi-arm bandit.The state is S_i(t) := (q_i(t), τ_i(t)).Source: §II · p. 3
  • Selecting one server yields reward equal to the number of jobs dispatched, so the dispatcher seeks the shortest queue to maximize expected total discounted reward.The dispatching action selects exactly one server at each time.Source: §II · pp. 2–3

III. LAGRANGIAN RELAXATION AND THE SINGLE-ARM DECOUPLED PROBLEM

The Lagrangian relaxation decouples the RMAB into single-arm problems with a subsidy for idling. The paper uses threshold structure and monotonicity in the subsidy to establish indexability, assuming no exogenous arrivals.

III. LAGRANGIAN RELAXATION AND THE SINGLE-ARM DECOUPLED PROBLEM

  • The Lagrangian relaxation separates the RMAB into independent single-arm optimization problems.The original dynamic-programming solution is computationally infeasible.Source: §III · p. 3
  • In a single-arm problem, probing reveals backlog and yields dispatched-job reward, whereas idling yields subsidy γ and advances the observation age.The value function compares the discounted returns of probing and idling.Source: §III · pp. 3–4
  • Whittle indexability means the states where idling is optimal grow monotonically as the subsidy rises; the index is the lowest subsidy that makes idling and activation equally desirable.Indexability permits use of the Whittle index policy after the RMAB is relaxed and decoupled.Source: §III · p. 4
  • The threshold-based indexability analysis requires a lower-triangular transition matrix, which the paper obtains by assuming no exogenous server arrivals.Only dispatcher-sent jobs arrive under this assumption.Source: §III · p. 4

IV. MODEL 1: FINITE QUEUES

In the standard finite-queue model, probing fills the selected queue to capacity, reducing the state to the time since it was last filled. The single-arm problem has a threshold-optimal policy and is indexable, with a closed-form Whittle index.

IV. MODEL 1: FINITE QUEUES

  • Because probing fills the selected queue to capacity, its observed backlog is always K and the state reduces to time since last filling.This reduction makes the Bellman equation one-dimensional and permits a closed-form solution.Source: §IV · p. 4
  • The expected backlog E(τ) is non-increasing in τ, and its successive differences are also non-increasing.The analysis focuses on subsidy values γ ∈ [0, K]; outside this range, always-idle or always-probe is optimal.Source: §IV · p. 4
  • The optimal policy waits a fixed threshold time τ* after probing before probing again, with the threshold determined by W(τ*) ≤ γ ≤ W(τ* + 1).The threshold policy is optimal for the single-arm problem.Source: §IV · p. 4
  • The standard finite-queue model is indexable, and its Whittle index can be derived in closed form.The index is expressed in terms of expected values.Source: §IV · p. 4
  • As the subsidy γ increases, the optimal waiting threshold does not decrease, establishing indexability under threshold optimality.The proof uses the monotonicity of W(τ).Source: §IV · p. 4
  • The process is resetting because probing always moves the state to (K, 1), so prior indexability techniques also apply.The paper's approach additionally derives the index in closed form using expected values.Source: §IV · p. 4

V. MODEL 2: BLOCKING FINITE QUEUES

In the blocking finite-queue model, a server accepts new jobs only when empty. The analysis considers threshold policies in time since observation and indexability for special cases.

V. MODEL 2: BLOCKING FINITE QUEUES

  • The blocking model accepts new jobs only when the server is empty.When probed, an empty server receives K jobs and yields reward K; a nonempty server yields no reward, though its backlog is observed.Source: §V · p. 5
  • After probing, the state records the observed backlog q′ and resets the observation age to 1.For an empty server, the updated state is (K, 1); for a nonempty server, it is (q′, 1).Source: §V · p. 5
  • The section establishes threshold optimality in time since observation and examines indexability for special cases.The passage identifies these as the analysis goals without specifying those cases or their outcomes.Source: §V · p. 5

A. Threshold Optimality

For the blocking-queue single-arm problem, the authors establish threshold optimality by analyzing the value of waiting before probing. The resulting optimal waiting time depends on the observed backlog and is longer for higher backlogs, though its value is not available in closed form.

A. Threshold Optimality

  • The analysis recasts choosing an action as choosing how many steps to idle before probing, and compares the resulting total rewards.L(q, τ)(l) denotes the total reward from idling l steps, probing, and then continuing optimally.Source: A. Threshold Optimality · p. 5
  • Once waiting-value differences begin decreasing with additional idle steps, they continue decreasing, which yields an optimal time to wait before probing.The proof uses single-crossing and total-positivity properties of the Poisson transition matrix.Source: A. Threshold Optimality · p. 5
  • For each observed backlog q, the optimal policy idles for a threshold number of steps before probing again.The threshold is ordered by backlog: higher observed backlogs require longer waits.Source: A. Threshold Optimality · p. 5
  • The threshold values cannot be derived in closed form because the state is two-dimensional.Source: A. Threshold Optimality · p. 5

B. Indexability for special cases

For blocking queues, the authors give a sufficient indexability condition under threshold optimality and prove indexability for two special cases. The condition is difficult to check generally, so broader indexability is supported by numerical trends rather than a general proof.

B. Indexability for special cases

  • Under threshold optimality, nondecreasing thresholds in subsidy γ are ensured by a sufficient condition comparing discounted active times at the decision boundaries.The condition is checked specifically at the threshold policy’s decision boundaries, rather than across all states.Source: B. Indexability for special cases · p. 6
  • For general K and β, the authors report numerical trends supporting indexability, but do not prove it generally.The condition is difficult to check because closed-form thresholds are unavailable and the model is not resetting.Source: B. Indexability for special cases · pp. 5–6
  • The blocking-queue model is indexable for K ≤ 2 and, separately, for β ≤ 0.5.The β condition follows from a bound on discounted active time; for β ≤ 0.5, the derived lower bound is nonnegative.Source: B. Indexability for special cases · p. 6
  • Under the blocking queues model (Model 2), the job dispatching problem is indexable for K ≤ 2, as stated in Theorem 4.Source: B. Indexability for special cases · p. 6

A. Model 1: Finite Queues Model

In finite-queue simulations, the Whittle index policy earns higher reward than the myopic policy and performs comparably to oracle JSQ.

A. Model 1: Finite Queues Model

B. Model 2: Blocking Queues Model

For the blocking-queue single-arm problem, numerical thresholds increase with subsidy, indicating indexability; simulations find the Whittle policy competitive with oracle JSQ.

B. Model 2: Blocking Queues Model

VII. CONCLUSION

The paper establishes threshold optimality for both queue models, proves indexability for finite queues and selected blocking-queue cases, and develops the supporting results summarized below.

VII. CONCLUSION

  • The conclusion reports threshold optimality and indexability for finite queues, while blocking-queue indexability is proved for special cases.The authors identify random dispatcher arrivals and exogenous server arrivals as future extensions, which may be harder because the transition matrix is not lower triangular and the value function may not be well behaved.Source: §VII · p. 7

APPENDIX A PROOF OF LEMMA 1

  • For the conditional expected backlog after a full queue observation, the expected backlog decrease is nonnegative and diminishes over time.Source: Appendix A · pp. 7–8

APPENDIX B PROOF OF THEOREM 1

  • The proof verifies that the threshold policy’s value function satisfies the Bellman equation, establishing optimality for the single-arm problem.Source: Appendix B · p. 8

APPENDIX C PROOF OF PROPOSITION 1

  • The proof obtains x_0>0 and x_q<0 for q>0, so the relevant difference crosses zero only once.Source: Appendix C · p. 8

APPENDIX D PROOF OF THEOREM 3

These proofs establish how threshold policies evolve with observation age and subsidy, and verify indexability for the blocking model when K=2.

APPENDIX D PROOF OF THEOREM 3

  • The optimal waiting time follows l*(q,τ+1)=[l*(q,τ)-1]+, yielding a threshold policy.Source: Appendix D · pp. 8–9
  • The proof shows optimal thresholds τ*_q are non-decreasing in backlog q.Source: Appendix D · p. 9

APPENDIX E PROOF OF PROPOSITION 2

  • The contradiction argument uses subsidy sensitivity of total discounted passive time to rule out a decreasing optimal threshold.Source: Appendix E · p. 9

APPENDIX F PROOF OF THEOREM 4

  • For K=2, the proof verifies indexability by establishing the active-time inequalities for both observed backlogs q=1 and q=2.Source: Appendix F · p. 9
Loading 2609.28219v1…