cs.FLNov 16, 2026

Tensorized Automata: Algebraically Informed Representation Learning for Sequential Decision Making

Authors: Anand Balakrishnan, Dweep Trivedi, Swarat Chaudhuri

Organizations: Department of Computer Science, University of Texas at Austin

Abstract

Task representations for sequential decision making should describe both an objective and progress toward it. We present an algebraically informed pipeline that uses the relational structure and language semantics of alternating finite automata (AFAs) to learn control features and compile compact execution operators. AND-OR message passing learns task and state vectors; selected configurations define an event-driven Boolean matrix operator. We prove that initial and successor language coverage make its carrier represent the exact residual after every prefix, with a sufficient capacity bound in terms of reachable configurations. Conjunction and disjunction use the same pipeline. Fidelity and composition audits evaluate copied formulas and learned disjunct assignments. In five-policy-seed XLand experiments with larger training pools, pooled execution-state vectors outperform raw carrier bits and task-blind conditioning across three task pools under two rejection rewards. They achieve 77.3% success on multi-event tasks and 99.4% on a four-task stratum with 33--128-state minimal DFAs, using 16 operator slots. LetterWorld results show useful residual conditioning alongside a remaining gap to RAD. These results connect algebraically informed representation learning to compact task execution and useful policy conditioning.

Figures & tables

Appendix figures & tables64 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Mar 20, 2026

Logic-Gated Time-Shared Feedforward Networks for Alternating Finite Automata: Exact Simulation and Learnability

We present a formal and constructive framework for simulating Alternating Finite Automata (AFAs) using Logic-Gated Time-Shared Feedforward Networks (LG-TS-FFNs). Unlike prior neural automata models limited to Nondeterministic Finite Automata (NFAs) and existential reachability, our architecture integrates learnable, state-dependent biases that function as differentiable logic gates, enabling the representation of both Existential OR and Universal AND aggregation within a shared-parameter linear recurrence. We prove that this architectural modification upgrades the network's computational class to be structurally isomorphic to AFAs, thereby inheriting their exponential succinctness: the network can represent regular languages requiring 2n2^n states in an NFA with only nn neurons. We rigorously establish that the forward pass of an LG-TS-FFN exactly simulates the reachability dynamics of an AFA, including instantaneous ε\varepsilon-closures. Furthermore, we demonstrate empirical learnability: a continuous relaxation of the logic gates allows the network to simultaneously recover the automaton's topology and logical semantics from binary labels via standard gradient descent. Extensive experiments confirm that our model achieves perfect recovery of ground-truth automata, bridging the gap between statistical learning and succinct, universal logical reasoning.
Jul 11, 2026

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

Does a reinforcement-learning agent that earns reward learn its task's hidden state? We study this question with hidden finite automata that the agent partially controls. Because each automaton is known, we can normalize reward by the best achievable return and probe the network for the true state at every step. Together the two measurements separate failures that reward alone conflates. An agent can encode too little of a state its network could hold, or encode the state and still control poorly. Weak on-policy RL matches random play while the state probe stays at chance. State learning depends on the optimizer, the training budget, and the task's structure. Permutation automata provide a warning before training: no input symbol maps two distinct states to the same successor. On a stratified held-out set, 86 of 103 permutation automata fail the state probe, and the classification is stable across probe read-outs and recovery thresholds. Most of these failures come with weak reward. High reward without the state occurs but is rare. Non-permutation automata can also fail. Oracle-normalized reward alone therefore does not establish that the task's state was learned.
Jun 2, 2026

A Goal-Set Characterization of Task Composition in the Boolean Task Algebra

The Boolean Task Algebra (BTA) provides a principled framework for zero-shot task composition in reinforcement learning by equipping goal-reaching tasks with Boolean operations. We revisit its structural assumptions and formalize a collapse in the space of optimal extended Q-value functions: in deterministic MDPs, every such function is fully determined by the universal and empty tasks. This makes the logarithmic set of base tasks proposed in the original BTA formulation redundant. Building on this observation, we introduce a goal-set-based composition method that performs logical operations on goal sets and reconstructs composed value functions by selecting slices from the universal and empty value functions. This reduces learning costs for standard BTA and reduces composition time for both BTA and Skill Machines, while preserving policy performance. Experiments across tabular, visual, function-approximation, and continuous-control domains show that learning additional base tasks does not yield better performance. Finally, we study the stochastic setting and provide a counterexample showing that this collapse need not hold, that is, optimal composition may require accounting for exponentially many policies in the number of goals. Code is available at https://github.com/EduardoTerres/GoalSetBTA.