Abstract
Reinforcement Learning (RL) has traditionally relied on neural networks to represent optimal policies in stochastic environments. While effective, these "black-box" models lack interpretability and formal verifiability. This paper initiates a theoretical study of Programmatic Reinforcement Learning (PRL), which represents policies as human-readable programs using higher-order constructs like control loops. We introduce a "Subgoal DSL" and a synthesis algorithm, proving that optimal programmatic policies are not only guaranteed to exist in complex gridworlds but are also polynomially bounded in size.
Introduction
The intersection of machine learning and formal methods has sparked significant interest in programmatic policies. Unlike neural weights, programs are structured, modular, and amenable to verification. However, the field has lacked rigorous answers to fundamental questions: Can a simple program always represent an optimal policy? How large must such a program be? We address these questions within the context of 2D gridworld environments with continuous state spaces and polygonal regions.
Methodology: The Subgoal DSL and Synthesis
We define a Subgoal DSL designed for navigation tasks. The language utilizes Do Until loops and From -> Target instructions to guide an agent through a sequence of geometric subgoals.
To generate these programs, we propose a two-stage synthesis approach:
- The Backward Algorithm: Starting from the goal, this algorithm performs a breadth-first search to construct a "tree of shortest paths," identifying the minimum moves required for every reachable state.
- Policy Synthesis: This algorithm compresses the shortest-path tree into programmatic blocks. By identifying repetitive geometric patterns—such as the spiraling behavior seen in complex mazes—it represents the policy using the DSL's control structures rather than an exhaustive list of state-action pairs.
Benchmarks and Empirical Validation
Our approach was evaluated on a suite of 17 benchmarks, including "The Spiral" and the "Double Pass Triangle." The latter is particularly significant as it requires an agent to perform different actions in the same region at different times, a task that traditional memoryless (positional) policies cannot solve without additional state information.
Empirical results show that policy size scales almost linearly with environment complexity. For instance, a benchmark with over 500 regions resulted in a policy of approximately 576 KB, which is remarkably compact compared to the memory footprint of a deep neural network.
Key Theoretical Insights
- Guaranteed Optimality (Theorem 1): We prove that our synthesis algorithm always produces a policy that reaches the target in the minimum number of moves possible.
- Polynomial Succinctness (Theorem 2): A major contribution is the proof that the size of the synthesized programmatic policy is $O(|Regions|^4)$. This ensures that programmatic representations remain manageable even as the environment grows, avoiding the exponential state-space explosion.
- Loops as Compression: The study demonstrates that
Do Untilloops are not just a convenience but a powerful tool for compressing complex navigation logic into succinct, verifiable code.
Conclusion and Future Work
This work establishes the first theoretical foundations for PRL in gridworlds. While we have solved the synthesis problem for known maps, the next frontier is learning: discovering these programmatic subgoals in unknown environments through exploration. Additionally, extending these guarantees to 3D spaces and higher-dimensional continuous environments remains an open challenge for the field.
Summary updated