Theoretical foundations for programmatic reinforcement learning

Guruprerana Shabadi, Nathanaël Fijalkow, Théo Matricon

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.

A gridworld environment (a) and its corresponding optimal programmatic policy (b) exhibiting a spiral pattern.

To generate these programs, we propose a two-stage synthesis approach:

  1. 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.
  2. 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.

A complex gridworld scenario illustrating the necessity of programmatic constructs to handle non-positional logic.

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 Until loops 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

Abstract

The field of Reinforcement Learning (RL) is concerned with algorithms for learning optimal policies in unknown stochastic environments. Programmatic RL studies representations of policies as programs, meaning involving higher order constructs such as control loops. Despite attracting a lot of attention at the intersection of the machine learning and formal methods communities, very little is known on the theoretical front about programmatic RL: what are good classes of programmatic policies? How large are optimal programmatic policies? How can we learn them? The goal of this paper is to give first answers to these questions, initiating a theoretical study of programmatic RL.
BibTeX
@misc{shabadi2024theoretical,
  author = {Guruprerana Shabadi and Nathanaël Fijalkow and Théo Matricon},
  title = {{Theoretical foundations for programmatic reinforcement learning}},
  year = {2024},
  eprint = {2402.11650},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2402.11650},
}
Figure