Author companion · Learning automata

Hierarchical Learning Automata Without a Shared Reinforcement Signal: Recovering the Environment Response From Action-Probability Changes

Preprint · arXiv:2605.00921 · Version 3, revised 2026-10-13

In a hierarchy of learning automata, only the root may see whether a decision succeeded. Follow two rounds to see how the sign of a share change carries that response to every level, and why selection matters.

Can a level learn without being told the outcome?

Hierarchies of learning automata select one root-to-leaf path per round, and the classical analyses deliver the environment response to every automaton on that path. Many deployed hierarchies cannot do that. The response is measured at the root, and the interfaces below carry requests but no feedback channel, because the levels belong to different parties, the interface is fixed, or the channel was never built.

What every level can still observe is whether its parent raised or lowered the probability of choosing it. The paper shows that this sign is enough. An active child reads the response from the direction of its own share change and updates its own children with it.

Follow one outcome through two levels

An animated reading of Table 2

The allocation change carries the bit

Root selectorObserves failure: 0
Selector 10.495incoming share from rootDecoded: 0
a0.595
b0.405
Selector 20.505incoming share from rootInactive: no decoding
c0.500
d0.500
Round 2 · Root → Selector 1 → b

After the second round, Selector 1 has decoded failure and reduced b’s local share to 0.405. Selector 2 remains inactive, so c and d keep equal local shares.

Exact two-round example from Section 4.1, using the proportional reward-penalty rule with update rate η = 0.1. The two numbers in each local allocation vector sum to one. Child weights are local shares, not shares of all root traffic.

The same example, without motion
AllocationInitialRound 1: success, select aRound 2: failure, select b
Root → Selector 10.5000.5500.495
Root → Selector 20.5000.4500.505
Selector 1 → a0.5000.5500.595
Selector 1 → b0.5000.4500.405

The sign recovers the response at every depth

The inactive branch matters. Its incoming share also changes, but in the opposite direction. If it decoded that change as an evaluation of its own choice, it would read the wrong response. Every node therefore checks whether it was on the selected path before decoding or updating its children.

The result covers a whole class of update rules. Whenever the selected action's probability rises on reward and does not rise on penalty, the decoded bit equals the root response at every depth. Linear reward-penalty, reward-inaction and reward-epsilon-penalty all qualify. The hierarchy that decodes signs and the hierarchy that broadcasts the response therefore produce identical sample paths, so convergence results proved for broadcast hierarchies under these rules carry over without the broadcast.

The proportional reward-penalty rule

Let w be the selected child’s current weight and let η be the update rate, strictly between zero and one. After a reward its new weight is (1 − η)w + η, and each sibling’s weight is multiplied by 1 − η.

After a penalty the selected weight becomes (1 − η)w. Every sibling’s weight is multiplied by (1 − w + ηw) / (1 − w). This returns the removed share to the other children in proportion to their weights, so the allocation stays interior.

For two actions this rule coincides with symmetric linear reward-penalty. For three or more it lies outside the classical schemes. Its mean flow converges globally to a closed-form allocation and drops actions below a computable threshold. High-precision replays on hierarchies of up to 16,384 leaves record zero decoding errors.

One selected path per round

The model selects one child per selector and one path per round. It does not divide a shared outcome among several simultaneous contributors or infer how an unselected alternative would have performed.

The protocol needs the exact sign of the parent's update. A child that estimates its share from a noisy traffic count is not covered. The proportional rule's convergence is proved for a single selector with fixed child response probabilities. Joint convergence of a hierarchy whose levels adapt at once remains open, and the rule is not claimed to track a changing environment better than reward-inaction. The two-round animation is an exact worked example, not evidence for those stronger claims.

Minimal feedback and hierarchical systems

This paper contributes to my work on adaptive and hierarchical systems. Source-side sufficiency for IB asks a separate question about preserving task information when reducing a source. Here the task is to recover a selected round’s evaluation from an observable change in allocation.

Multi-Resolution Attribution from Adaptive Routing State examines related questions about attribution. Sharing a hierarchical setting does not make these results interchangeable with attribution among simultaneous contributors.

Paper and citation

J. Armstrong, “Hierarchical Learning Automata Without a Shared Reinforcement Signal: Recovering the Environment Response From Action-Probability Changes,” arXiv:2605.00921, 2026. This explanation follows v3, revised 2026-10-13. Current public record.

Download BibTeX citation · Version explained here: v3