keyword
finite automaton
A finite automaton is an abstract mathematical model of computation used to process sequences of inputs through a limited number of internal states. It is formally defined by a finite set of states, an input alphabet, a transition function specifying how the system moves between states based on each incoming symbol, a designated start state, and a set of accepting or final states. Depending on whether the next state is uniquely determined by the current state and input, an automaton is classified as deterministic or nondeterministic. Because they possess no auxiliary memory beyond their current state, finite automata recognize regular languages and are widely applied in pattern matching, lexical analysis, protocol specification, and the formal verification of sequential systems.
2 items
The Illusion of State in State-Space Models
William Merrill, Jackson Petty, Ashish Sabharwal
Why you should read this
Proves that popular state-space models like S4 and Mamba share the same fundamental expressive limitations as transformers for sequential state tracking, while identifying a minimal architectural modification to overcome this barrier.
State-space models (SSMs) have emerged as a potential alternative to transformers. One theoretical weakness of transformers is that they cannot express certain kinds of sequential computation and state tracking (Merrill & Sabharwal, 2023a), which SSMs are explicitly designed to address via their close architectural similarity to recurrent neural networks. But do SSMs truly have an advantage (over transformers) in expressive power for state tracking? Surprisingly, the answer is no. Our analysis reveals that the expressive power of S4, Mamba, and related SSMs is limited very similarly to transformers (within TC⁰), meaning these SSMs cannot solve simple state-tracking problems like permutation composition and consequently are provably unable to accurately track chess moves with certain notation, evaluate code, or track entities in a long narrative. To supplement our formal analysis, we report experiments showing that S4 and Mamba indeed struggle with state tracking. Thus, despite their recurrent formulation, the “state” in common SSMs is an illusion: S4, Mamba, and related models have similar expressiveness limitations to non-recurrent models like transformers, which may fundamentally limit their ability to solve real-world state-tracking problems. Moreover, we show that only a minimal change allows SSMs to express and learn state tracking, motivating the development of new, more expressive SSM architectures.
Added
2026-10-01
Automaton-Guided Curriculum Generation for Reinforcement Learning Agents
Yash Shukla, Abhishek Kulkarni, Robert Wright, Alvaro Velasquez, Jivko Sinapov
Why you should read this
Demonstrates how to automatically generate efficient learning sequences for complex multi-step tasks by leveraging formal automaton representations, achieving dramatically faster training than existing curriculum learning approaches.
Despite advances in Reinforcement Learning, many sequential decision making tasks remain prohibitively expensive and impractical to learn. Recently, approaches that automatically generate reward functions from logical task specifications have been proposed to mitigate this issue; however, they scale poorly on long-horizon tasks (i.e., tasks where the agent needs to perform a series of correct actions to reach the goal state, considering future transitions while choosing an action). Employing a curriculum (a sequence of increasingly complex tasks) further improves the learning speed of the agent by sequencing intermediate tasks suited to the learning capacity of the agent. However, generating curricula from the logical specification still remains an unsolved problem. To this end, we propose AGCL, Automaton-guided Curriculum Learning, a novel method for automatically generating curricula for the target task in the form of Directed Acyclic Graphs (DAGs). AGCL encodes the specification in the form of a deterministic finite automaton (DFA), and then uses the DFA along with the Object-Oriented MDP (OOMDP) representation to generate a curriculum as a DAG, where the vertices correspond to tasks, and edges correspond to the direction of knowledge transfer. Experiments in gridworld and physics-based simulated robotics domains show that the curricula produced by AGCL achieve improved time-to-threshold performance on a complex sequential decision-making problem relative to state-of-the-art curriculum learning (e.g, teacher-student, self-play) and automaton-guided reinforcement learning baselines (e.g, Q-Learning for Reward Machines). Further, we demonstrate that AGCL performs well even in the presence of noise in the task's OOMDP description, and also when distractor objects are present that are not modeled in the logical specification of the tasks' objectives.
Added
2026-02-21