Skip to content
STIMSMITH

Deduction-Guided Reinforcement Learning

Technique WIKI v1 · 7/1/2026

Deduction-Guided Reinforcement Learning is a technique that combines deductive reasoning with reinforcement learning, introduced for the purpose of program synthesis. It was formalized in a 2020 publication by Chen, Wang, Bastani, Dillig, and Feng, which applied the method to synthesizing programs from specifications.

Deduction-Guided Reinforcement Learning

Overview

Deduction-Guided Reinforcement Learning is a technique that combines deductive reasoning (logical, constraint-based inference) with reinforcement learning to guide a learning-based search process. It was introduced in the context of synthesizing programs, where deduction provides structural or logical guidance to a reinforcement learning policy that navigates the space of candidate programs.

Origin and Publication

The technique was formalized in the 2020 paper "Program Synthesis Using Deduction-Guided Reinforcement Learning" by Yanju Chen, Chenglong Wang, Osbert Bastani, Işıl Dillig, and Yu Feng. The work appeared in the Lecture Notes in Computer Science series (pages 587–610) and was assigned the DOI 10.1007/978-3-030-53291-8_30.

Application: Program Synthesis

As evidenced by the paper's title and the related-entity mapping, the principal application domain of Deduction-Guided Reinforcement Learning is Program Synthesis — the task of automatically generating programs from high-level specifications (such as input/output examples, logical constraints, or natural-language intent). In this setting, deductive reasoning is used to prune, constrain, or guide the search, while reinforcement learning provides a learned policy for selecting program construction actions.

Relation to Other Synthesis Approaches

The technique sits at the intersection of:

  • Deductive / constraint-based synthesis, which uses logical reasoning (e.g., SMT solvers, conflict-driven learning) to prune the program space.
  • Learning-based synthesis, which uses statistical learning — including reinforcement learning — to bias program construction.

Earlier and contemporaneous program-synthesis research that the technique can be compared against includes conflict-driven learning approaches (Feng et al., 2018), Datalog synthesis via numerical relaxation (Si et al., 2019), and frameworks that synthesize the most probable program under a specification (Xiong & Wang, 2022). All of these works are catalogued alongside the originating paper in the Genesys reference set.

Evidence Summary

The only direct bibliographic evidence for this technique is a single LNCS citation listing. As such, this article is intentionally conservative and confines its claims to what that citation, together with the provided related-entity mapping, explicitly supports.

LINKED ENTITIES

1 links
Program Synthesis USES

CITATIONS

3 sources
3 citations
[1] Deduction-Guided Reinforcement Learning was formalized in the 2020 paper 'Program Synthesis Using Deduction-Guided Reinforcement Learning' by Yanju Chen, Chenglong Wang, Osbert Bastani, Işıl Dillig, and Yu Feng. Genesys: A Novel Evolutionary Program Synthesis Tool with Continuous Optimization (reference list)
[2] The paper appears in Lecture Notes in Computer Science, pages 587–610, with DOI 10.1007/978-3-030-53291-8_30. Genesys: A Novel Evolutionary Program Synthesis Tool with Continuous Optimization (reference list)
[3] The technique's principal application domain is Program Synthesis, as indicated by the paper title and the USES relation to the Program Synthesis concept. Genesys: A Novel Evolutionary Program Synthesis Tool with Continuous Optimization (reference list)