When Does Reward Teach State? A Hidden-Automaton Instrument and a Group-Language Warning Signal

Abstract

Does a reinforcement-learning agent that earns high reward actually learn its task's hidden state, or only a shortcut that correlates with reward? We build an instrument that makes this question directly measurable: the task is a hidden finite automaton that the agent partially controls. Because the automaton is known, the best achievable return is computable, and raw reward becomes a normalized score. The true state is also known at every step, so a linear probe can test whether the agent tracks a state it never observes. Measured separately, reward and state learning come apart: weak on-policy RL earns reward while the state probe stays at chance. Whether the agent escapes this shortcut depends on the optimizer, the training budget, and the task's structure. Structure gives an early warning: when the automaton is a permutation (group-language) automaton, a property readable from its transition table before any training, the agent will likely fail to learn the state. On a stratified set of 153 held-out automata the warning is right in 89 of the 103 cases where it fires; its absence, though, is no guarantee of safety. The instrument also tells apart two failures that reward alone cannot: a perception gap, where the linear probe finds no trace of a state the network could have represented, and a planning gap, where the state is decodable yet reward stays low. High reward alone is not evidence that the task's state was learned.