mlsanityData to 14 Oct 2026

Programmatic Reinforcement Learning: Navigating Gridworlds

arXiv 2402.11650 ↗First posted 18 Feb 2024cs.LG cs.LO cs.PLcited by 1

On the map: Deep reinforcement learning methods → Deep RL algorithms and representations

Abstract (arXiv)

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. Considering a class of gridworld environments, we define a class of programmatic policies. Our main contributions are to place upper bounds on the size of optimal programmatic policies, and to construct an algorithm for synthesizing them. These theoretical findings are complemented by a prototype implementation of the algorithm.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods. First posted on arXiv 18 Feb 2024.

Builds on

0 of 0 references.

No references here yet.

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025Simplicity Lies in the Eye of the Beholder: A Strategic Perspective on Controllers in Reactive Synthesiscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2019Imitation-Projected Programmatic Reinforcement Learning ↗
  2. 2023Understanding Reinforcement Learning Algorithms: The Progress from Basic Q-learning to Proximal Policy Optimization
  3. 2024Efficient Exploration in Deep Reinforcement Learning: A Novel Bayesian Actor-Critic Algorithm
  4. 2024A Comprehensive Survey of Reinforcement Learning: From Algorithms to Practical Challenges
  5. 2026Mathematical methods of reinforcement learning
  6. 2024Introduction to Reinforcement Learning
  7. 2026Reinforcement Learning: From Algorithms To Foundation Models
  8. 2024Synthesizing Programmatic Reinforcement Learning Policies with Large Language Model Guided Search