🤖 machine learning

When Does Reward Teach State? A Hidden-Automaton Instrument and the Group-Language Boundary

This paper introduces a white-box hidden-automaton framework to rigorously distinguish between reward maximization and genuine latent-state learning in reinforcement learning, revealing that high reward does not guarantee task understanding and that state recovery gaps are predictable based on task structure, optimizer strength, and observation informativeness.

Original authors: Jim Allchin

Published 2026-07-15

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Jim Allchin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a robot to navigate a secret maze. The robot gets a single, tiny gold star at the very end if it reaches the exit. If it hits a wall or takes a wrong turn, it gets nothing.

Now, here is the big question: If the robot gets that gold star, does it actually understand the map of the maze? Or did it just memorize a lucky shortcut, like "always turn left at the red sign," without ever realizing there is a hidden door behind it?

For a long time, scientists couldn't answer this. They could see the robot get the star, but they couldn't see inside the robot's brain to know if it was thinking about the map or just guessing.

This paper builds a special, "white-box" maze to solve that mystery. The researchers created a digital world based on a hidden machine (called a DFA) that knows the true path. They let the robot play, but they also kept a secret cheat sheet that told them exactly where the robot should be at every step. This allowed them to measure two things separately:

Did the robot get the star? (Reward success)
Did the robot actually know where it was? (Latent state learning)

The Big Surprise: Getting the Star Doesn't Mean You Know the Map

The most exciting finding is that these two things are not the same. A robot can get a high score (lots of gold stars) while having absolutely no idea where it is in the maze. It's like a student who gets an A on a test by memorizing the answer key but failing to understand the math.

The paper proves that just because an agent is "good" at getting rewards, it doesn't mean it has learned the task. It might just be riding a lucky wave.

The Three Knobs That Control the Robot's Brain

The researchers found that whether the robot learns the map or just the shortcut depends on three specific "knobs" they can turn:

1. The "Brain Power" Knob (Optimizer Strength)
If you use a weak training method (like a simple, clumsy teacher), the robot will get the star but fail to learn the map. It's like trying to teach a toddler to solve a Rubik's cube with a stick; they might get lucky, but they won't understand the puzzle.
However, if you use a stronger, smarter training method (like PPO), the robot starts to actually learn the map. But even with the best teacher, it's not perfect. The robot learns some of the map, but there's still a gap. The paper shows that with a strong teacher, the robot's "map knowledge" recovers only partially and varies significantly depending on the random seed, reaching gaps of around +0.20 compared to a theoretical maximum of +0.48 or +0.60, depending on the specific puzzle.

2. The "Puzzle Shape" Knob (Task Structure)
This is the paper's coolest discovery. Some mazes are built in a way that makes them impossible for the robot to learn, no matter how smart the teacher is.
The researchers found that if the maze follows a specific "group" pattern (mathematically called a permutation automaton), the robot hits a wall. It's like a maze where every turn you make just spins you in a circle without ever letting you remember where you started.

The Warning Sign: Before even training the robot, the researchers can look at the maze's blueprint and say, "Warning! This is a permutation maze. The robot will likely be blind to the map."
The Proof: They tested this on 153 brand new, random mazes. When the maze had this "permutation" shape, the robot failed to learn the map 86% of the time (89 out of 103 cases). It's a high-precision warning light.
What it's NOT: If the maze doesn't have this shape, the robot might still fail for other reasons, but it's not guaranteed to be blind. The shape is a warning, not a guarantee of safety for other shapes.

3. The "Clue" Knob (Observation Informativeness)
Sometimes the robot fails because it's flying blind. If the robot can't see any clues about where it is, it can't learn.
The paper tested this by giving the robot a tiny hint (like a colored dot that appears 10% of the time).

Result: If the robot gets any hint (even a tiny one, like a 0.10 probability), the helper task suddenly becomes fully effective, and the robot recovers the map.
The Catch: If the robot gets no hints (0% probability), a helper task that tries to guess the next step is useless. It's like trying to teach someone to drive by asking them to guess the color of the car ahead when they can't see the road. The robot recovers the state in proportion to how much the observations actually reveal.

Two Types of Failure: "Blind" vs. "Clueless"

The paper introduces a crucial distinction that only this special testbed could reveal:

The Perception Gap: The robot could learn the map (it has the brain power), but it doesn't. It's like a student who has a textbook but refuses to read it. This happens with those tricky "permutation" mazes.
The Planning Gap: The robot knows the map perfectly but can't figure out how to use it to get the star. It's like a student who knows the math but freezes when trying to write the answer.

Most people only look at the gold star (the reward). They think, "Oh, the robot failed, so it didn't learn." But this paper shows that sometimes the robot did learn the map, it just couldn't use it. Without this special test, you'd never know the difference.

Real-World Checks

The researchers didn't just make up these mazes. They looked at real computer code (like checksums used to check if data is correct) and real business workflows (like loan applications).

Real Code: They found that code for checking numbers (like "is this divisible by 7?") often has that tricky "permutation" shape. This means real-world AI agents might be blind to these tasks, just like their robot.
Real Workflows: They looked at 7 real-world business processes (like billing or permits). None of them had the tricky shape. They were all learnable. This suggests that while the "blindness" problem is real, it might not be the most common problem in everyday business logs.

The Takeaway

The paper concludes that we can't just trust an AI because it gets good scores. We need to check if it actually understands the task.

The Good News: We now have a tool to check. If we see a "permutation" shape in a task, we know to be careful.
The Fix: If an AI is blind, we can fix it by making the task easier to see (adding clues) or by changing the task so the robot can "lock in" its progress (adding a "hold" button).
The Limit: The paper admits that while they found this pattern in 153 new mazes and some real code, they haven't tested it on massive, complex AI systems yet. They are just starting to build the tools to test those bigger systems.

In short: High rewards don't prove understanding. Sometimes, the AI is just lucky. But with the right tools, we can finally peek under the hood and see if it's actually driving or just riding along.

Technical Summary: When Does Reward Teach State? A Hidden-Automaton Instrument and the Group-Language Boundary

1. Problem Statement

Reinforcement learning (RL) agents often achieve high reward scores without necessarily learning the underlying latent state of their task. Instead, they may learn "reward-correlated shortcuts" or heuristics that succeed under specific training distributions but fail to generalize when the task structure changes (e.g., longer horizons, noise, or distribution shifts). This phenomenon, known as goal misgeneralization, is difficult to diagnose because the "true state" of a task is typically undefined or unobservable in standard benchmarks.

The core question addressed is: Does a high-reward agent represent the task's latent state, or is it merely exploiting a shortcut? To answer this, the paper proposes a framework where the latent state is an exactly known, measurable object, allowing researchers to decouple "reward success" from "state learning."

2. Methodology: The Hidden-Automaton Instrument

The authors introduce a white-box experimental instrument based on Hidden Deterministic Finite Automata (DFAs) under Partial Control.

The Environment (PartialControlDFAEnv)

Task Definition: The task is defined as a DFA $M = (Q, \Sigma, \delta, q_0, F)$ .
Partial Control: In an episode of length $T$ , at each step, the agent chooses the next symbol with probability $p_{control}$ ; otherwise, the environment samples the symbol uniformly.
Observations: The agent observes the emitted symbol stream, whether the step was controllable, and the time remaining. Crucially, the agent never observes the hidden state $q_t$ .
Reward: Sparse and terminal. The agent receives $r=1$ if the final state $q_T \in F$ (accepting state), and $0$ otherwise.

The Oracle and Probes

Because the automaton is known to the experimenter, two critical capabilities are available "for free":

Exact Oracle: The optimal achievable return $V(q, r)$ is computed via backward induction. This allows raw rewards to be normalized into an interpretable score (0.0 to 1.0) comparable across tasks.
Exact Latent State Probe: The true state $q_t$ at every step is known. Researchers can fit a linear classifier to the agent's internal features to measure how well the agent represents the true state (the "probe gap").

Diagnostic Axes

The instrument measures the coupling between reward success and state learning along three controllable axes:

Optimizer Strength: Comparing weak optimizers (A2C) against stronger ones (PPO+GAE).
Task Structure: Specifically, whether the automaton exhibits group-language (permutation) structure, where every symbol induces a bijection on the reachable states (no state merging).
Observation Informativeness: The degree to which observations reveal the latent state, controlled via a tunable parameter $\beta$ (state coloring).

3. Key Contributions

Measurement Methodology: A recipe to express any FSM-approximable task as a hidden partial-control DFA. This yields an exact oracle for normalization, an exact latent state for linear probing, and an off-policy supervised capacity bound.
Benchmark Instance (PartialControlDFAEnv): A taxonomy separating diagnostic automata (where state tracking is necessary) from trivial ones.
Optimizer-Dependent Coupling: Evidence that the link between reward and state learning is governed by optimizer strength. Weak optimizers (A2C) often fail to install latent state representations despite achieving reward, while stronger optimizers (PPO) improve this coupling, though recovery is often partial and high-variance.
Distinction of Failure Modes: The instrument distinguishes between:
- Perception Gap: The agent cannot recover the latent state (probe at chance), even though it is representable.
- Planning Gap: The agent represents the state (high probe score) but fails to use it to maximize reward.
Structural Warning Signal: Identification of permutation (group-language) structure as a high-precision, pre-training warning signal for the perception gap. This is computable from the transition function $\delta$ alone, prior to any training.

4. Key Results

Optimizer Strength and State Recovery

Under weak on-policy RL (A2C), the state probe remains at chance levels for all architectures, even those (like GRUs) proven to have the representational capacity to solve the task.
Switching to PPO+GAE significantly improves both reward and state recovery. However, recovery is often partial (e.g., probe gaps of ~0.20 vs. a supervised capacity ceiling of ~0.48–0.60) and exhibits high seed variance.
Conclusion: Sparse reward alone is insufficient to guarantee state learning; optimizer strength is the dominant driver of the reward-state coupling.

The Perception Gap and Group Languages

Permutation Automata: Tasks where the automaton is a permutation (group language) require the agent to "accumulate" state without forgetting (no state merging). These tasks are significantly harder for sparse-reward RL.
Predictive Power: A predictor based on the conjunction of permutation structure and low control leverage (how much the agent can influence the state) perfectly ranks difficulty in-sample.
Held-Out Validation: On a held-out set of 153 fresh random DFAs, permutation structure predicts the perception gap with precision 0.86 (89 of 103 permutation automata exhibited the gap).
Real-World Mining: The authors mined hidden DFAs from real-world logic (checksums) and process logs.
- Real checksums (e.g., divisibility by 7) exhibited the permutation structure and the perception gap.
- Real process logs (e.g., procurement, clinical workflows) were non-permutation and learnable, suggesting the perception gap is present in real logic but not the universal case for workflows.

Auxiliary Signals and Observation Informativeness

Label-Free Auxiliaries: Predicting the next emitted symbol is vacuous if observations carry no state information ( $\beta=0$ ). However, as soon as observations reveal any state information ( $\beta \ge 0.10$ ), a label-free auxiliary recovers the latent state and rescues reward performance.
Privileged Auxiliaries: Providing the true state as an auxiliary is nearly inert when the base learner (PPO) already recovers the state, but provides significant gains when the base learner fails (weak optimizers or high complexity).

Planning vs. Perception Gaps

The study identifies a critical distinction invisible to reward-only evaluation:

Planning Gap: An agent (e.g., on ends_with_1000) has a high state probe score but low reward, indicating it knows the state but cannot act on it.
Perception Gap: An agent (e.g., on mined_ean) has low reward and a chance-level probe, indicating it never learned the state.
Behavioral metrics (reward gaps) are nearly uncorrelated with the recoverable state, proving that high reward does not imply task understanding.

5. Significance and Claims

The paper claims that reward success is not evidence of task understanding. The ability of an agent (or a cheap auxiliary) to recover the latent state is predictable in advance based on the automaton's structure.

The "Perception Gap": The paper establishes that for permutation (group-language) automata, sparse-reward RL often fails to install the latent state representation, even when the architecture is capable of it. This is a "perception gap" driven by credit-assignment difficulties in non-merging state spaces.
The "Planning Gap": Conversely, agents can learn the state but fail to utilize it, a failure mode distinct from perception.
Actionable Audit: The primary contribution is the instrument itself. It allows researchers to audit any agent task by converting it to a hidden FSM, providing an exact oracle and state probe. This enables a "white-box" audit to determine if an agent learned the task or just a shortcut.
Causal Fixes: The paper demonstrates that the perception gap can be causally closed by making the latent state observable (adding state-revealing emissions) or latchable (adding controllable hold actions), without needing a perfect a-priori predictor.

The authors note that while the structural predictor is high-precision for the perception gap, it is not a guarantee of safety for non-group tasks (which are heterogeneous). Furthermore, the findings are currently limited to small synthetic automata and a preliminary port to LLM agents, which reproduced the axes but did not yet produce a clean large-scale perception gap. The instrument is released to facilitate further investigation into stateful agent reliability.