A Stack-Shaped Belief for Delayed Control of Nested Tasks

Many robot tasks have a nested, last-in-first-out shape. A robot opens a drawer, then a box inside it, then must close them in the reverse order. Or it interrupts a subtask to handle another, then resumes the first. Now add sensor delay: observations arrive late and sometimes out of order, so for stretches of time the robot acts on a guess about the present. Current delay-aware learners keep that guess in a single fixed-size recurrent vector. Recurrent world models are networks that summarize history in a hidden state and can imagine forward when data is missing. Work on formal languages shows such vectors blur exact nesting over long horizons. We propose a world model whose hidden state includes a differentiable stack and whose belief, during a delay window, is a weighted superposition of possible stack histories. The model commits the stack only for time steps whose observations have all arrived.

The point is twofold. Nested task structure is exactly what plain recurrent belief filters lose while imagining through a delay. And the obstacle to using the right memory, the cubic cost of tracking every stack configuration, goes away once nondeterminism is confined to the delay window. Cost then grows with the delay, not with the episode length.

Core Claim

When a control task's hidden progress follows a context-free pattern and observations are randomly delayed, two things should hold. First, a recurrent belief filter with a stack component tracks task progress through blind periods far better than a plain recurrent filter. Second, the stack must be nondeterministic within the delay window, meaning it holds a weighted mix of possible push/pop histories rather than committing to one guess. Otherwise early wrong guesses about unobserved push/pop events compound.

The new technical piece is windowed nondeterminism. The superposition only has to cover the last $d$ steps, where $d$ is the current observation lag. Per-step cost then scales as $O(d^3)$ rather than the $O(n^3)$ in episode length $n$ of the full nondeterministic stack.

Where This Sits

Three papers supply the motivation and the starting method on the control side.

Model-Based Reinforcement Learning under Random Observation Delays introduces DA-Dreamer. Its recurrent state-space world model updates its belief when a delayed observation arrives and rolls forward on learned prior dynamics when one is missing. We keep that filtering scheme and change what the belief is made of.

Recurrent Neural Networks for Stochastic Control Problems with Delay shows that LSTMs handle even infinite delay when the history acts as a fading average. Our tasks are deliberately the opposite case: history matters exactly and without decay.

Delay-Aware Diffusion Policy skips trajectory states to cover execution delay. In a nested task, skipping states can skip a push or pop, which is the tension our belief representation is built to handle.

On the grammar side, two papers motivate the design and constrain it.

Recognizing Long Grammatical Sequences Using Recurrent Networks Augmented With An External Differentiable Stack and Enhancing Reinforcement Learning with discrete interfaces to learn the Dyck Language document "memory smearing," where a recurrent vector degrades on deep nesting. Both fix it with external stack or deque memory, but only on static strings with no environment and no delay.

Learning Context-free Languages with Nondeterministic Stack RNNs supplies the core mechanism. Its NS-RNN uses Lang's algorithm to sum over exponentially many stack configurations at $O(n^3)$ time. It also supplies two constraints: deterministic stacks get stuck on ambiguous structure, and the cubic cost plus degraded extrapolation beyond length 80 are real.

We read the NS-RNN's weighted superposition of stacks as a belief over a hidden pushdown state. That reading turns a parsing device into a filter. It also tells us where the superposition can be collapsed: wherever all the evidence is in.

SEM-CTRL enforces grammar and logic constraints through solver-masked search. It assumes a known grammar and no latency. We assume neither, and use a known-grammar symbolic tracker only as an oracle upper bound.

Research Program

We will build a delay-aware world model whose latent state has two parts: the usual recurrent vector, and a stack belief.

The stack belief has two layers. The committed prefix is a single deterministic differentiable stack. The window is a small weighted automaton over the last $d$ steps, run in the log semiring as in the NS-RNN. At each step the recurrent controller emits push, pop, and no-op weights.

When an observation $o_\tau$ arrives late, the filter re-scores the window paths that pass through step $\tau$. Once every step up to $\tau'$ has been observed, the window is collapsed up to $\tau'$ into the committed stack. Collapse means taking the expected stack contents, a choice we will compare against taking the single most likely path. Training follows DA-Dreamer: the world model is learned on re-ordered complete sequences, and the policy is learned in imagination.

The analysis has three parts. We will measure belief quality directly by probing the predicted stack top and depth during blind windows against ground truth. We will measure how wall-clock cost per control step grows with $d$ and with $n$. As a real-time reference, Recurrent Model Predictive Control reports 4.7 ms per step for its recurrent controller. Finally, we will characterize when commitment errors occur.

The test environments are built from benchmarks in the file. The first is a symbolic control testbed in which the agent must respond to Dyck-structured cues, using the bracket-matching languages D2, D3, and D6 from the stack-RNN papers. The second is a set of nested Meta-World variants. Meta-World comes from Meta-World and is standardized in Meta-World+. Its drawer, door, and lid tasks will be chained, and the agent must undo them in reverse order of a randomly sampled opening sequence. The third adds interrupt-and-resume subtasks in ManiSkill2. All three use the uniform U{0,20} and truncated-Gaussian delay distributions from the DA-Dreamer study.

Baselines

The naive reference is a memoryless agent and an observation-stacking agent. The latter corresponds to the Stack-Dreamer baseline in Model-Based Reinforcement Learning under Random Observation Delays. Both are trained with the same environment steps. They show how much any belief filtering buys.

The strongest existing method is DA-Dreamer itself, run on its released settings with the same total parameter count as our model. We will widen its recurrent state to absorb the parameters the stack would otherwise use, so any gain is not just extra capacity.

On standard delayed MuJoCo, that paper reports Humanoid return of about 1854 under 0–10 step random delay, versus about 1062 for DCAC. On Meta-World it reports near-perfect success under heavy delay, without exact numbers. Our first requirement is to reproduce roughly 1854 on Humanoid and not lose it: the stack must be harmless when there is no nesting. No reported result was found on Lacuna for any method on nested, delayed control tasks, so those numbers will be ours.

Beating DA-Dreamer means two things. On nested tasks, success should be clearly higher at nesting depths beyond training (train at depth up to 3, test at depth 6) and at the larger delays. On non-nested tasks, results should stay within noise.

Two ablations isolate the key ingredients. The first replaces the windowed nondeterministic stack with a deterministic stack that commits immediately, in the style of the DiffStk-RNN. The second uses a full-history nondeterministic stack without windowing. The first tests whether nondeterminism under delay matters. The second tests whether windowing costs accuracy while saving compute.

The upper bound is an oracle. The true grammar is given and a symbolic pushdown tracker is fused with DA-Dreamer, in the spirit of SEM-CTRL.

Every agent gets the same environment interaction budget, the same number of hyperparameter search trials, and the same seeds (at least five).

Why not just…?

Why not just give DA-Dreamer a bigger hidden state? This is the main threat, since at shallow depth a wide recurrent vector may track nesting well enough. The stack-RNN papers report that plain LSTMs fall to low accuracy on Dyck languages as length grows, which suggests width does not fix exact nesting. That evidence comes from static strings, however. The capacity-matched baseline across a sweep of depth and delay will settle the question. If the wide model matches us out to depth 6, the claim fails.

Why not just use a transformer world model over the full observation history? Attention can look back at the arrival-ordered history directly. Two pieces of evidence argue against it here. Enhancing Reinforcement Learning with discrete interfaces to learn the Dyck Language reports that sequence models without structured memory fail to extrapolate from length 10 to 100. And full-history attention grows with episode length, which conflicts with control-step budgets. We will include a transformer world model of matched size, report both depth extrapolation and per-step latency, and accept a loss if it extrapolates.

Why not just hand the agent the grammar as a symbolic automaton? If the task grammar is known, a symbolic tracker is simpler and exact, and it is our oracle. The proposal's claim is therefore limited to settings where the nested structure must be learned from reward and observations. We will report the remaining gap to the oracle honestly rather than claim to beat it.

Why not just use a deterministic stack, which is cheaper? The NS-RNN paper shows deterministic stacks get stuck on ambiguous languages. Under delay, every unobserved push/pop decision is ambiguous until its observation arrives. The commit-immediately ablation measures whether this matters in control. If it does not, the windowed machinery is unnecessary and we will say so.

Proposed Experiments

The decisive experiment is a grid over nesting depth (1–6, trained up to 3) and delay distribution, run on the Dyck control testbed and the nested Meta-World chain. The metrics are task success, stack-top probe accuracy during blind windows, and milliseconds per step.

The proposal is supported if three things hold together. Our model's advantage over the capacity-matched DA-Dreamer must grow with both depth and delay. The commit-immediately ablation must degrade specifically as delay grows. And windowed cost must stay flat in episode length while full nondeterminism grows cubically.

The sanity check is standard delayed Humanoid, where we must stay near the reported DA-Dreamer return of about 1854.

A negative result is also informative. If a wide recurrent state or a transformer closes the gap, that would show memory smearing is not the binding limitation for delayed control. Instead it would characterize when plain recurrent belief filters are enough, which is Gap 3 in the file.