報酬はいつ状態を教えるか？隠れオートマトン操作変数と群言語境界When Does Reward Teach State? A Hidden-Automaton Instrument and the Group-Language Boundary

Reinforcement learning agents routinely operate in environments where the true state is hidden, and a longstanding theoretical question is whether the reward signal alone carries enough information to recover that latent state. A new paper posted to arXiv tackles this question directly, formalizing when reward observations can identify the underlying environment configuration and pinpointing a precise boundary, drawn from formal language theory, that separates the identifiable case from the impossible one.

The work matters because most practical agents do not enjoy direct access to ground-truth state. In partially observable settings, an agent sees only observations and rewards while the environment evolves according to dynamics it cannot inspect. If a system designer wants guarantees, for example that a learned representation reflects real environmental structure rather than spurious correlation, they need to know under what conditions the observable signals uniquely pin down the hidden mechanism. Identifiability, a notion borrowed from statistics and econometrics, is exactly this: two distinct latent models should not produce indistinguishable observable behavior.

The paper's central construction is what it calls a hidden-automaton instrumental framework. The idea appears to combine two threads. First, it models the latent environment as an automaton whose state transitions are driven by actions, so that sequences of actions become strings over an input alphabet and the reward becomes a function of the automaton's trajectory. Second, it imports the logic of instrumental variables, a technique from causal inference in which an external source of variation, the instrument, is used to disentangle a causal effect that would otherwise be confounded. Here, the agent's own actions or exploratory choices appear to play the role of instruments, injecting controlled variation that, under the right conditions, exposes the latent transition structure through its effect on rewards.

The most distinctive claim is that the frontier of identifiability coincides with the group-language boundary. In algebraic automata theory, regular languages are classified by the structure of their syntactic monoid. Group languages are those whose syntactic monoid is a finite group, meaning every input symbol induces a permutation of the automaton's states, so nothing is ever collapsed or forgotten because permutations are reversible. This reversibility is the crux. When the underlying automaton behaves like a group, action sequences permute states without destroying information, and the paper argues that reward signals can in principle be inverted to recover the state. When the automaton falls outside the group class, when some inputs are non-invertible and merge distinct states, information about the latent state is irreversibly lost, and no amount of reward observation can separate the merged possibilities. The boundary between these regimes is therefore not a heuristic but a structural dichotomy tied to well-established algebraic classifications, such as the Krohn-Rhodes decomposition and the aperiodic-versus-group distinction that underpins much of formal language theory.

For context, this line of reasoning connects several communities that rarely meet. Automata learning has a long history, from Angluin's L-star algorithm for learning regular languages via queries to more recent spectral methods for learning weighted automata and predictive state representations. Work on POMDP identifiability and on hidden Markov model recovery addresses related questions with probabilistic tools. The novelty here appears to be the explicit fusion of causal instrumental reasoning with the algebraic taxonomy of languages, using the latter to characterize exactly when the former succeeds.

The practical implications should be read cautiously, since the results are theoretical and likely rest on idealized assumptions such as exact rewards, sufficient exploration, or noiseless observation. Even so, the framing offers a useful diagnostic. It suggests that reward-only state estimation is feasible in reversible, symmetry-rich domains but fundamentally limited wherever the environment discards information, which may guide how researchers design reward functions, choose exploration strategies, or decide when auxiliary observations are indispensable. If the group-language boundary holds up under noise and approximation, it could become a reference point for reasoning about representation learning and reward design in partially observable reinforcement learning, and a bridge between the theory of computation and the practice of building agents.