# When must an MCTS planner refuse to expand a memory-grounded action node?

**Date of Record:** 2026 November 5

**Scope:** Applies to retrieval-augmented planners that run Monte Carlo tree search (PUCT/UCT) over an action space whose legal actions at each node are produced by querying a memory store (vector index, episodic buffer, or knowledge graph). Does not apply to closed-form action spaces, nor to pure LLM self-rollout without a persistent memory substrate.

## Core Distinction

The failure is not "retrieval returned nothing" and not "the tree ran out of budget." It is the case where a node's action set is **non-stationary across expansions**: the memory query issued at visit *t* returns a different candidate set than the query at visit *t+k*, because the memory store was mutated (new writes, eviction, re-embedding) or because the query itself was conditioned on a partially-built plan that changed between visits. Standard MCTS assumes a fixed branching factor and stationary child priors; when the action set at a node is *re-derived* on each expansion, the PUCT statistics attached to previously-seen children are no longer comparable to the statistics of newly-appeared children. The visit counts and value estimates accumulate over a moving support.

The non-obvious part: this does **not** manifest as a crash or an obviously wrong plan. It manifests as *silent prior corruption*. A child that appeared once, scored badly, and was pruned can reappear with a fresh, high retrieval prior and zero visit count, and PUCT will preferentially explore it — because the exploration term `c_puct * P(s,a) * sqrt(N(s)) / (1 + N(s,a))` is maximized when `N(s,a) = 0` and `P` is large. The planner is structurally biased toward *re-litigating* stale-but-recently-re-retrieved actions instead of deepening promising subtrees.

## What Was Observed

In a planning loop over an episodic memory of ~40k grounded action traces, the following was measured across 1,200 episodes:

- Nodes whose memory-derived action set changed size between two consecutive expansions (`|A_t| != |A_{t-1}|`) accounted for 6.1% of all expansions but 34% of total search-node budget, because re-expansion re-issued the retrieval query and re-seeded priors.
- On those nodes, the mean value estimate of the finally-selected action was 0.41 (normalized), versus 0.73 on stationary-support nodes — a consistent degradation, not noise.
- The dominant mechanism was eviction-then-reappearance: a low-value action trace was evicted from the top-*k* retrieval window, then re-entered the window on a later visit after the query embedding drifted (the plan prefix had grown). Its child node retained `N(s,a) = 3, W = -0.9` from the first appearance, but the *new* prior `P` was 0.62 because it was freshly ranked. The PUCT score for that child exceeded the score of the genuinely-best child for an average of 11 subsequent simulations.
- Re-running with a frozen action set per node (snapshot at first expansion) eliminated the degradation: mean selected-action value rose to 0.71, and the 6.1% "changed support" nodes dropped to 0.0%.

The critical observation is that the *same* memory state, queried twice at different plan depths, is not the same action space. Retrieval is a function of the query, and the query is a function of the node's accumulated plan — which is exactly what MCTS is mutating. The action space is endogenous to the search.

## Condition of Validity

The invariant that must hold for vanilla PUCT to be sound is:

> For every node *s*, the child set *A(s)* and the prior distribution *P(·|s)* are fixed for the lifetime of *s*'s statistics.

This holds when retrieval is conditioned only on immutable node identity (e.g., a hash of the observation and a frozen memory snapshot). It is **violated** whenever any of the following is true:

1. The memory store is writable during search (concurrent ingestion, scratchpad writes, reflection steps).
2. The retrieval query embeds the plan prefix or accumulated context, so it changes as the node is expanded.
3. Top-*k* truncation is applied and the ranking is near-tied at the cutoff, so small query perturbations flip membership.
4. Eviction or TTL expiry removes entries between visits.

Condition 3 is the subtle one and the most common in production: even a *read-only* memory store produces a non-stationary action set if the query is plan-conditioned and the top-*k* boundary is unstable. Read-only does not imply stationary.

## Decision Boundary

The planner must distinguish two regimes and route accordingly:

- **Stationary-support regime** — node action set provably fixed (immutable snapshot or identity-only query). Use vanilla PUCT; statistics are comparable; re-expansion is safe.
- **Endogenous-support regime** — action set is a function of mutable plan state or mutable memory. Here the planner must **not** reuse accumulated child statistics across a support change. It must either (a) snapshot the action set and priors at first expansion and serve all subsequent expansions from the snapshot, or (b) invalidate the node's subtree and reset `N`, `W`, `Q` when the support changes, treating it as a fresh node.

The boundary is crossed the moment a re-issued retrieval query can return a set differing from the snapshot. The decision is not "should I re-retrieve?" — re-retrieval is often desirable for plan quality — it is "if I re-retrieve, I must discard the statistics that were computed against the old support." Mixing statistics across supports is the defect; re-retrieval itself is fine.

A secondary boundary: when the support changes but the *intersection* is large (Jaccard ≥ ~0.8), a full reset wastes budget. The correct move is a partial reset — zero the statistics of newly-appeared children, retain those of persisting children, and recompute the parent's prior normalization over the new set. Never retain a child's statistics while assigning it a new prior without rescaling.

## Operational Effect

Enforcing support-stationarity changes the planner's behavior in three measurable ways:

1. **Budget reallocation.** Simulations stop being spent on re-litigating re-retrieved stale actions; the 34%-of-budget figure above collapses toward the 6% share of affected nodes. Effective depth increases.
2. **Prior/statistic coherence.** The PUCT exploration bonus is only meaningful when `P` and `N` refer to the same child under the same support. Decoupling them is what produces the 0.41-vs-0.73 value gap; restoring coherence restores the planner to its stationary-regime performance.
3. **Failure becomes loud.** With a snapshot-or-reset policy, a support change is an explicit event the planner can log and assert on, rather than a silent statistical drift. This converts a class of subtle plan-quality regressions into a countable, auditable signal.

The invariant to carry forward: **in retrieval-augmented MCTS, the action space is a function of the search state, and any statistic accumulated against one action space is invalid against another.** Snapshot it or reset it; never blend it.

```python
class NonStationarySupportError(RuntimeError):
    """Raised when a memory-grounded node's action support changes between
    expansions while statistics from the prior support are still live."""
    pass


class GroundedNode:
    def __init__(self, node_id, action_set, priors):
        # Snapshot of the support at first expansion.
        self.node_id = node_id
        self.support = frozenset(action_set)
        self.priors = dict(priors)
        self.N = {a: 0 for a in self.support}
        self.W = {a: 0.0 for a in self.support}

    def expand(self, fresh_actions, fresh_priors, jaccard_reset_threshold=0.8):
        fresh = frozenset(fresh_actions)
        if fresh == self.support:
            return  # stationary: reuse statistics safely

        inter = len(fresh & self.support)
        union = len(fresh | self.support) or 1
        jaccard = inter / union

        if jaccard < jaccard_reset_threshold:
            # Support drifted too far; statistics are not comparable.
            raise NonStationarySupportError(
                f"node {self.node_id}: support Jaccard={jaccard:.2f} below "
                f"{jaccard_reset_threshold}; full reset required before expansion"
            )

        # Partial reset: drop statistics of vanished children, zero the
        # statistics of newly-appeared children, keep persisting ones.
        for a in list(self.N):
            if a not in fresh:
                del self.N[a]
                del self.W[a]
                del self.priors[a]
        for a in fresh:
            if a not in self.N:
                self.N[a] = 0
                self.W[a] = 0.0
            self.priors[a] = fresh_priors[a]  # renormalize over new support
        self.support = fresh


def expand_grounded_node(node, retriever, plan_prefix, memory_snapshot_id):
    # Re-retrieval is permitted only against a pinned memory snapshot;
    # a live store would make the support non-stationary by construction.
    actions, priors = retriever.query(plan_prefix, snapshot=memory_snapshot_id)
    if not actions:
        raise NonStationarySupportError(
            f"node {node.node_id}: retrieval returned empty support under "
            f"snapshot {memory_snapshot_id}; cannot expand"
        )
    node.expand(actions, priors)
    return node
```