Programmatic Reinforcement Learning: Navigating Gridworlds

• URL: http://arxiv.org/abs/2402.11650v2
• Date: Fri, 10 Jan 2025 09:44:48 GMT
• Title: Programmatic Reinforcement Learning: Navigating Gridworlds
• Authors: Guruprerana Shabadi, Nathanaël Fijalkow, Théo Matricon,
• Abstract summary: Programmatic RL studies representations of policies as programs, meaning involving higher order constructs such as control loops. Our main contributions are to place upper bounds on the size of optimal programmatic policies, and to construct an algorithm for them. These theoretical findings are complemented by a prototype implementation of the algorithm.
• Score: 1.956739480860805
• License:
• 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. 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.

Related papers

• Offline Imitation Learning from Multiple Baselines with Applications to Compiler Optimization [17.729842629392742]
  We study a Reinforcement Learning problem in which we are given a set of trajectories collected with K baseline policies. The goal is to learn a policy which performs as well as the best combination of baselines on the entire state space.
  arXiv  Detail & Related papers  (2024-03-28T14:34:02Z)
• The Definitive Guide to Policy Gradients in Deep Reinforcement Learning: Theory, Algorithms and Implementations [0.0]
  In recent years, various powerful policy gradient algorithms have been proposed in deep reinforcement learning. We provide a holistic overview of on-policy policy gradient algorithms to facilitate the understanding of both their theoretical foundations and their practical implementations.
  arXiv  Detail & Related papers  (2024-01-24T18:56:53Z)
• Program Machine Policy: Addressing Long-Horizon Tasks by Integrating Program Synthesis and State Machines [7.159109885159399]
  Program Machine Policy (POMP) bridges the advantages of programmatic RL and state machine policies. We introduce a method that can retrieve a set of effective, diverse, and compatible programs. Our proposed framework outperforms programmatic RL and deep RL baselines on various tasks.
  arXiv  Detail & Related papers  (2023-11-27T16:06:39Z)
• Hierarchical Programmatic Reinforcement Learning via Learning to Compose Programs [58.94569213396991]
  We propose a hierarchical programmatic reinforcement learning framework to produce program policies. By learning to compose programs, our proposed framework can produce program policies that describe out-of-distributionally complex behaviors. The experimental results in the Karel domain show that our proposed framework outperforms baselines.
  arXiv  Detail & Related papers  (2023-01-30T14:50:46Z)
• Is Reinforcement Learning (Not) for Natural Language Processing?: Benchmarks, Baselines, and Building Blocks for Natural Language Policy Optimization [73.74371798168642]
  We introduce an open-source modular library, RL4LMs, for optimizing language generators with reinforcement learning. Next, we present the GRUE benchmark, a set of 6 language generation tasks which are supervised not by target strings, but by reward functions. Finally, we introduce an easy-to-use, performant RL algorithm, NLPO, that learns to effectively reduce the action space in language generation.
  arXiv  Detail & Related papers  (2022-10-03T21:38:29Z)
• Policy Gradient for Reinforcement Learning with General Utilities [50.65940899590487]
  In Reinforcement Learning (RL), the goal of agents is to discover an optimal policy that maximizes the expected cumulative rewards. Many supervised and unsupervised RL problems are not covered in the Linear RL framework. We derive the policy gradient theorem for RL with general utilities.
  arXiv  Detail & Related papers  (2022-10-03T14:57:46Z)
• Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation [107.54516740713969]
  We study human-in-the-loop reinforcement learning (RL) with trajectory preferences. Instead of receiving a numeric reward at each step, the agent only receives preferences over trajectory pairs from a human overseer. We propose the first optimistic model-based algorithm for PbRL with general function approximation.
  arXiv  Detail & Related papers  (2022-05-23T09:03:24Z)
• Jump-Start Reinforcement Learning [68.82380421479675]
  We present a meta algorithm that can use offline data, demonstrations, or a pre-existing policy to initialize an RL policy. In particular, we propose Jump-Start Reinforcement Learning (JSRL), an algorithm that employs two policies to solve tasks. We show via experiments that JSRL is able to significantly outperform existing imitation and reinforcement learning algorithms.
  arXiv  Detail & Related papers  (2022-04-05T17:25:22Z)
• Learning to Synthesize Programs as Interpretable and Generalizable Policies [25.258598215642067]
  We present a framework that learns to synthesize a program, which details the procedure to solve a task in a flexible and expressive manner. Experimental results demonstrate that the proposed framework not only learns to reliably synthesize task-solving programs but also outperforms DRL and program synthesis baselines.
  arXiv  Detail & Related papers  (2021-08-31T07:03:06Z)
• Discovering Reinforcement Learning Algorithms [53.72358280495428]
  Reinforcement learning algorithms update an agent's parameters according to one of several possible rules. This paper introduces a new meta-learning approach that discovers an entire update rule. It includes both 'what to predict' (e.g. value functions) and 'how to learn from it' by interacting with a set of environments.
  arXiv  Detail & Related papers  (2020-07-17T07:38:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.