acceptodds
Under review as a conference paper at ICLR 2027

MINT: Certifying Queue Instability from Limited Commands and Hidden Modes

Abstract

Can observation and command interfaces each pass a capacity test while together making stabilization impossible? We introduce MINT (Menu–Innovation No-go Test), a model-based certificate for controllers that send one of labels to a stateless executor with fixed action templates. MINT first averages each action's service over the unseen mode change, then finds the best service possible with fixed action templates, even granting the controller knowledge of the previous mode. If arrivals exceed this joint ceiling, every compliant controller using past departure feedback has growing expected backlog, regardless of its memory or training method. Separate command-only and prediction-only ceilings can both miss this obstruction. For every , we give an -mode queue family and an open load interval where MINT detects it. Matching stable constructions establish exact minimum budgets of commands with departure history and with current-mode observation; two noncyclic instances show the same separation. In a four-mode task, reward-only search recovers finite controllers that are certified stable after training at a feasible budget.

Primary area:
learning theory
Keywords:
queue stability, stochastic control, partial observability, action interfaces, information constraints, finite-state controllers

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_AwFWOpenReview ↗
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(λ\lambda) 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 m−1m-1 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

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 nn independent queues under fixed polling, the same total-load interval (0.498,0.51111…)(0.498,0.51111\ldots) separates 2n2n-command current-mode control from 2n2n-command departure-feedback control. Its width stays fixed as nn 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 2n2n commands, while departure feedback needs at least ⌈59n/28⌉\lceil59n/28\rceil. 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.

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.

Reviewer_KuRoOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies stabilizing a discrete-time queue whose server has a hidden Markov mode that sets the success probability of each action. The controller observes only past actions and departures. It acts through a "label-only" interface: an unrestricted history encoder sends one of K labels, and a stateless executor samples the physical action from a fixed distribution ("template") for that label.

The main result (Thm 2) is a no-go certificate. Departure feedback cannot reveal the most recent mode change, so achievable service is at most Ψ_K = Γ_K(ν, HR), the best K-action menu value of the one-step-predicted service matrix. If arrivals exceed this ceiling, expected backlog grows linearly for every compliant controller. The paper shows this joint bound can be strictly tighter than both an interface-only bound (current mode known, K labels) and a prediction-only bound (previous mode known, unrestricted actions).

For an m-mode cyclic family (Thm 4), matching constructions give exact minimum budgets on a load interval: m labels with departure feedback and m−1 with current-mode observation. A "stay on success, advance on failure" tracker achieves the former. The appendices add NP-completeness of deciding whether a budget suffices (Prop 6) and two noncyclic instances.

Critical strengths
  1. Theoremm 4 pairs a class-wide impossibility result with explicit stable constructions, turning the bound into exact interface thresholds within the family. The noncyclic instances (App. G) and replayable exact certificates in the supplement add credibility. This matters because the paper's main claim is that observation and command capacity must be evaluated jointly, and the matching constructions show the joint bound is tight rather than merely conservative.

  2. In the learning study, finite controllers found by reward-only search are certified stable after training at the feasible budget and never at the infeasible one. Neural results are explicitly labeled as finite-run checks. This supports the practical message without overclaiming.

Critical weaknesses
  1. The connection to learning is a small case study on one 4-mode instance which has limited applications.
  2. The core inequality (Thm 2) follows from simply conditioning on (S_{t−1}, Z_t) and maximizing per label.
  3. The strict separation is demonstrated on a constructed family over a load interval of width |I_m| = Θ(1/m), with a one-label difference.
Questions for authors
  1. How does MINT relate to the known capacity/stability regions for Markov ON/OFF channels inferred from ACK feedback (Jagannathan et al. 2011; Li & Neely 2010)?
  2. Can you give a concrete learning system where the label-only/no-bypass contract holds and MINT changes a design decision? Examples might be a fixed skill library in hierarchical RL, or a finite tool/command API.
  3. Proposition 6 concerns the current-phase menu capacity (via Prop 5). Is anything beyond max-k-cover hardness known or expected for the departure-feedback case?
2 comments

We address your concerns about the learning evidence, the size of the separation, and the relation to prior work below. We also add a scaling construction and a complexity result for the departure-feedback bound.

W1. Learning evidence. With four commands, all ten reward-only searches found controllers that can be proved stable after training. The three-command bound excludes every history-based controller, regardless of its memory. The experiment therefore connects the policy-class limit to a learned and certified controller on the same task (Section 5 and Appendix H).

Section 5.2 and Appendix J.2 extend these learned controllers to independent queues under fixed polling. At total load 0.78, four commands per queue suffice for any finite number of queues, while three per queue are insufficient.

W2. Contribution beyond conditioning. In the four-mode example at load 0.78, both separate service bounds exceed demand, while their combined bound excludes every three-command history policy. Stable policies show that four commands with departure feedback, or three with current-mode observation, suffice. Theorem 4 pairs the bound with these constructions to establish exact minimum budgets for the stated mm-mode family.

W3. Width and command gap. To address the shrinking interval and one-command difference, Section 3.4 and Appendix J.1 give nn independent three-mode queues under fixed polling. Throughout (0.498,0.51111…)(0.498,0.51111\ldots), current-mode observation permits stability with 2n2n commands, while departure feedback requires more than 2n2n; 3n3n suffice. At load 0.510, departure feedback requires at least ⌈59n/28⌉\lceil59n/28\rceil. The absolute gap therefore grows with nn while the interval width stays fixed.

Q1. ACK-based capacity. Prior ACK-based work characterizes stability under incomplete observations. We add a limit on the number of fixed action distributions and optimize over the command library. Our stable constructions then show exactly how this limit changes the minimum budget in the examples (Section 6).

Q2. A learning architecture. Consider a recurrent host that selects fixed transmission-profile IDs exposed by firmware. The host remembers past actions and departures; the executor uses only the current ID. In the four-mode instance, observing the current mode makes three commands sufficient, whereas departure feedback requires four. The result can therefore guide the choice between expanding the command library and improving observation.

Q3. Complexity. Appendix K.2 proves that deciding whether the predicted-service bound exceeds a threshold is NP-complete, even with a strictly positive mode transition matrix. Appendix K.1 gives a linear-programming upper bound for certifying exclusion. The complexity of deciding actual stability from departure histories remains open.

Thank you for providing explanations and answers to my questions.

Reviewer_AiWVOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper analyzes queue instability of a simple discrete-time single-server queue with Bernoulli arrivals. The controller outputs a categorical distribution over discrete actions. The paper derives conditions accounting separately and jointly for the command restriction and hidden-mode transitions yielding queuing instability. The paper also provides an example with a specific transition kernel H and function R that shows where the joint condition is tight.

Critical strengths

The results are plausible and appear to be correct. The impossibility conditions enable arbitrary controller memory. I did not check every proof line by line; my assessment included an AI-assisted mathematical audit.

Critical weaknesses

My concerns are related to the relevance of the problem and the connection to machine learning.

  1. The queueing dynamics are basic (Bernoulli arrivals, fully determined model, low dimensional). The controller is stateless and selects from fixed action templates. The paper would benefit from a concrete application showing why this particular restriction is natural and why the resulting bounds are practically consequential.

  2. The instability conditions concern arbitrary state-less controllers, including controllers that can be learned. However, for evaluating the bounds, model parameters need to be known, in particular the hidden-state transition matrix H, the probabilities R, the arrival rate \lambda. It is unclear how the bounds can be evaluated from finite data. The learning experiments consequently provide a relatively narrow demonstration. I therefore don't see the fit of this work for ICLR.

  3. The writing appears to be very fluffy, and introduced unnecessary terminology and framing that obscure the mathematical structure. I recommend the authors to largely improve the writing by 1) motivating the problem formulation with a concrete example of an actual queue, 2) leaving all the fluffy language 'menu', 'innovation', 'no-bypass', 'interface-only', etc. away and getting straight to the relevant mathematics, 3) adopting established terminology from relevant fields such Markov decision processes and queuing theory.

  4. Technical novelity is unclear. The main bounds use conditional expectation and finite-dimensional optimization over categorical distributions, while the stability arguments use Markov-chain and Lyapunov methods that appear basic. The authors should explain directly what the exact instability bounds add beyond well-known existing results.

Questions for authors

See weaknesses.

2 comments

We address your concerns about the application, connection to learning, use of finite data, writing, and technical contribution below. The revision adds a packet-queue example, a finite-data certificate, and a direct comparison with related capacity results.

W1. Controller and application. The controller may retain its entire action and departure history. Its stateless executor maps each command ID to a fixed action distribution. A recurrent host selecting firmware transmission profiles is an example of this architecture.

In our four-mode example at load 0.78, no three-command controller with departure feedback can stabilize the queue, even with unlimited memory. Four commands suffice; with current-mode observation, three suffice. The result identifies a concrete design choice: expand the command library or improve observation.

For 100 independent queues under fixed polling at total load 0.510, current-mode observation permits stability with 200 commands; departure feedback requires at least 211, and 300 suffice (Section 3.4 and Appendix J.1).

W2. Learning and finite data. We use reward-only search to test whether learning can find a stable controller when the budget permits one. All ten four-command runs recover controllers that are proved stable after training; the theorem excludes the entire three-command class. Finite controllers make it possible to verify the learned policies over the unbounded queue (Section 5 and Appendix H).

To address finite-data evaluation, Section 4 and Appendix K.3 give 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 produced certificates in 1,473 of 2,000 replicates with 100,000 trials per service pair and 100,000 arrival observations (Table 13).

W3. Writing. In response to your suggestions, the paper now begins with a packet queue and defines the controller and executor before presenting the service bounds. We use “commands,” “mode transitions,” and “service bounds” throughout; Figure 1 separates controller memory from the fixed action table.

W4. Technical contribution. Our result combines the effect of limited commands with an unobserved mode change. In the four-mode example, either restriction considered alone leaves stability possible, but together they exclude every three-command history policy. Stable policies show how adding a command or observing the current mode restores stability. Theorem 4 extends this necessity-and-sufficiency comparison to the stated mm-mode family. Section 6 explains the distinction from ACK-based and delayed-information capacity results.

Thank you for the reply and for improving the manuscript. However, these seem marginal improvements, and I think a major revision is needed. I will therefore keep my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.