Searching for Programmatic Policies in Semantic Spaces

• URL: http://arxiv.org/abs/2405.05431v2
• Date: Wed, 12 Jun 2024 18:54:02 GMT
• Title: Searching for Programmatic Policies in Semantic Spaces
• Authors: Rubens O. Moraes, Levi H. S. Lelis,
• Abstract summary: We propose an alternative method for synthesizing programmatic policies, where we search within an approximation of the language's semantic space. Our rationale is that the search is more efficient if the algorithm evaluates different agent behaviors as it searches through the space.
• Score: 13.466710708566177
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Syntax-guided synthesis is commonly used to generate programs encoding policies. In this approach, the set of programs, that can be written in a domain-specific language defines the search space, and an algorithm searches within this space for programs that encode strong policies. In this paper, we propose an alternative method for synthesizing programmatic policies, where we search within an approximation of the language's semantic space. We hypothesized that searching in semantic spaces is more sample-efficient compared to syntax-based spaces. Our rationale is that the search is more efficient if the algorithm evaluates different agent behaviors as it searches through the space, a feature often missing in syntax-based spaces. This is because small changes in the syntax of a program often do not result in different agent behaviors. We define semantic spaces by learning a library of programs that present different agent behaviors. Then, we approximate the semantic space by defining a neighborhood function for local search algorithms, where we replace parts of the current candidate program with programs from the library. We evaluated our hypothesis in a real-time strategy game called MicroRTS. Empirical results support our hypothesis that searching in semantic spaces can be more sample-efficient than searching in syntax-based spaces.

Related papers

• Reclaiming the Source of Programmatic Policies: Programmatic versus Latent Spaces [10.654876600946865]
  We show that the programmatic space presents values for the behavior loss similar to those observed in latent spaces. Algorithms searching in the programmatic space significantly outperform those in LEAPS and HPRL.
  arXiv  Detail & Related papers  (2024-10-16T02:10:04Z)
• Efficient Bottom-Up Synthesis for Programs with Local Variables [7.387053183440393]
  Our algorithm can efficiently search programs with local variables. Lifted interpretation provides a mechanism to enumerate all binding contexts for local variables. Our ideas are instantiated in the domain of web automation.
  arXiv  Detail & Related papers  (2023-11-07T04:02:52Z)
• Weakly Supervised Semantic Parsing with Execution-based Spurious Program Filtering [19.96076749160955]
  We propose a domain-agnostic filtering mechanism based on program execution results. We run a majority vote on these representations to identify and filter out programs with significantly different semantics from the other programs.
  arXiv  Detail & Related papers  (2023-11-02T11:45:40Z)
• Tensor Program Optimization with Probabilistic Programs [16.303739951257814]
  This paper introduces MetaSchedule, a domain-specific probabilistic programming language abstraction to construct a rich search space of tensor programs. Our abstraction allows domain experts to analyze the program, and easily propose choices in a modular way to compose program transformation. We also build an end-to-end learning-driven framework to find an optimized program for a given search space.
  arXiv  Detail & Related papers  (2022-05-26T20:20:02Z)
• CrossBeam: Learning to Search in Bottom-Up Program Synthesis [51.37514793318815]
  We propose training a neural model to learn a hands-on search policy for bottom-up synthesis. Our approach, called CrossBeam, uses the neural model to choose how to combine previously-explored programs into new programs. We observe that CrossBeam learns to search efficiently, exploring much smaller portions of the program space compared to the state-of-the-art.
  arXiv  Detail & Related papers  (2022-03-20T04:41:05Z)
• Searching for More Efficient Dynamic Programs [61.79535031840558]
  We describe a set of program transformations, a simple metric for assessing the efficiency of a transformed program, and a search procedure to improve this metric. We show that in practice, automated search can find substantial improvements to the initial program.
  arXiv  Detail & Related papers  (2021-09-14T20:52:55Z)
• Leveraging Language to Learn Program Abstractions and Search Heuristics [66.28391181268645]
  We introduce LAPS (Language for Abstraction and Program Search), a technique for using natural language annotations to guide joint learning of libraries and neurally-guided search models for synthesis. When integrated into a state-of-the-art library learning system (DreamCoder), LAPS produces higher-quality libraries and improves search efficiency and generalization.
  arXiv  Detail & Related papers  (2021-06-18T15:08:47Z)
• Selection-Expansion: A Unifying Framework for Motion-Planning and Diversity Search Algorithms [69.87173070473717]
  We investigate the properties of two diversity search algorithms, the Novelty Search and the Goal Exploration Process algorithms. The relation to MP algorithms reveals that the smoothness, or lack of smoothness of the mapping between the policy parameter space and the outcome space plays a key role in the search efficiency.
  arXiv  Detail & Related papers  (2021-04-10T13:52:27Z)
• CNN-based Spoken Term Detection and Localization without Dynamic Programming [16.322420712725716]
  The proposed algorithm infers whether a term was uttered within a given speech signal or not by predicting the word embeddings of various parts of the speech signal. The algorithm simultaneously predicts all possible locations of the target term and does not need dynamic programming for optimal search.
  arXiv  Detail & Related papers  (2021-03-07T14:50:58Z)
• Representing Partial Programs with Blended Abstract Semantics [62.20775388513027]
  We introduce a technique for representing partially written programs in a program synthesis engine. We learn an approximate execution model implemented as a modular neural network. We show that these hybrid neuro-symbolic representations enable execution-guided synthesizers to use more powerful language constructs.
  arXiv  Detail & Related papers  (2020-12-23T20:40:18Z)
• Accelerating Text Mining Using Domain-Specific Stop Word Lists [57.76576681191192]
  We present a novel approach for the automatic extraction of domain-specific words called the hyperplane-based approach. The hyperplane-based approach can significantly reduce text dimensionality by eliminating irrelevant features. Results indicate that the hyperplane-based approach can reduce the dimensionality of the corpus by 90% and outperforms mutual information.
  arXiv  Detail & Related papers  (2020-11-18T17:42:32Z)

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.