- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The paper introduces the Menu–Innovation No-go Test (MINT), a model-based certificate of instability for a single queue with Bernoulli() arrivals served by a server whose hidden mode evolves as a Markov chain. The controller observes only past departures and its own actions, and acts through a label-only interface: an encoder with unlimited memory selects one of K labels, and a stateless decoder samples the action from a fixed distribution installed for that label. The paper first defines two necessary service bounds, an interface only bound and a prediction only bound, and shows that both can exceed demand even when no stable controller exists. MINT combines the two by averaging service over the unobserved mode change before optimizing over K action menus. If arrivals exceed this ceiling, every compliant controller has growing expected backlog and is unstable. The authors show the significance of the certificate by looking at matched cycle family of m-mode environments where MINT excludes every controller with labels while both separate tests pass. Matching constructions show that an m-label tracker is stable under departure feedback, and that m − 1 labels suffice if the encoder observes the current mode, giving exact minimum label budgets. Simulations at m = 4 are consistent with these results, and a reward-only search recovers the stable tracker at K = 4; neural (GRU-PPO) training succeeds only under specific training choices.
Critical strengths
- The insight is clean, forming a certificate that looks into both the interface and the unseen mode change is intuitive.
- The figures in the paper gives the reader a good high level understanding of the setting.
- The authors provide an honest report of scope and failures.
Critical weaknesses
- MINT is shown to beat the simpler tests only in the matched-cycle family, plus two four-mode examples. The construction needs modes that change very rarely, a matched action that almost never fails, and an arrival rate inside a narrow window.
- The m vs m-1 result is fairly intuitive, a controller that tracks the mode from feedback would require a label for every node.
- Applying MINT requires knowing the model exactly. The robustness margin is very small (1/4000 in the example), and choosing the best menu is computationally hard in general, with no method offered for larger problems.
Questions for authors
- How does MINT relate to known results on queue stability with delayed channel-state information?
- Is there a separation that does not require very persistent modes, near-certain matched service, or a load window that shrinks as the number of modes grows?
- Which real systems or learned architectures satisfy the label only, no bypass assumption?
2 comments
Thank you for the detailed response and the substantial additions. They address most of the concerns in my review.
The new three-mode example, with a 0.30 probability of a mode change and matched service of 0.85, is a useful addition. It shows that the separation does not depend on extremely persistent modes or near-certain matched service. The load window in this example (about 0.498–0.511) is still fairly narrow. The polling construction shows that the gap in command count can grow with the number of queues at a fixed load. I see this mainly as a replication argument across independent queues, and it would help to say explicitly what it adds beyond the single-queue result.
The linear-programming upper bound with a dual certificate addresses my concern about the cost of the menu search. The finite-data certificate is a good step toward practical use. My understanding is that it requires service trials labelled by the previous hidden mode and known stationary mode weights. Since the setting assumes the mode is hidden from the controller, it would be helpful to discuss when such labelled data could realistically be obtained.
Delayed information and architectures: Thank you for positioning MINT relative to work on delayed channel-state information. I would encourage citing and discussing that literature explicitly in the paper. The firmware transmission-profile example is a helpful illustration of the label-only interface. It would be stronger with a concrete system shown to satisfy the no-bypass condition, since real firmware often adapts internally using feedback.
The response and the new results address most of my concerns, although I am not fully convinced on the width of the separation window, the data requirements of the certificate, and how practical the interface assumption is. I have not been able to go through the new sections and appendices (Sec. 3.4, App. J.1, K.1, K.3) in full detail, and my familiarity with this area is broad rather than specialist, so my confidence remains limited. Taking the added constructions and tools into account, I am raising my score by one point.
To address your concerns about parameter choices, the narrow load interval, and practical use of the bound, we add a fixed-parameter scaling construction, a computable upper bound, and a finite-data certificate.
W1. Parameters and interval width. Section 3.4 and Appendix J.1 give a three-mode example with a 0.30 probability of changing modes and matched-service probability 0.85. Its two-command departure-feedback bound is 0.498; a three-command tracker is stable below approximately 0.51111. For n independent queues under fixed polling, the same total-load interval (0.498,0.51111…) separates 2n-command current-mode control from 2n-command departure-feedback control. Its width stays fixed as n grows.
W2. Exact command budgets. Our service bound covers all history-based controllers, including those with unlimited memory and randomized command distributions. It establishes the necessary budget; the tracker and current-mode policy attain the corresponding sufficient budgets. Together they give exact minimum command counts for the stated family.
W3. Computation and data. Section 4 and Appendix K.1 give a linear-programming upper bound. For 100 queues, an exact dual certificate puts it below 0.498000000001, versus load 0.510. To address estimation from data, Appendix K.3 gives a 95% confidence guarantee using independent service trials labeled by previous mode and action, with known stationary mode weights. At load 0.510, the synthetic calibration issued certificates in 1,473 of 2,000 replicates with 100,000 trials per service pair and 100,000 arrival observations (Table 13).
Q1. Delayed information. Prior work studies queue stability with delayed channel information. We use the corresponding predicted-service matrix and ask how that information delay interacts with a fixed number of commands. Appendix E also shows how the bound changes with observation delay.
Q2. A growing gap at fixed load. In the polling construction (Section 3.4, Appendix J.1), at total load 0.510, current-mode observation needs at most 2n commands, while departure feedback needs at least ⌈59n/28⌉. The absolute difference grows with the number of queues, at fixed local parameters and load.
Q3. An architecture. A recurrent host can select fixed transmission-profile IDs exposed by firmware. The host retains the action and departure history; the executor reads only the current ID and samples from its fixed action distribution. Figure 1 shows this division. For the polling construction, each ID also identifies a queue.