💻 computer science

Sample-efficient Neuro-symbolic Proximal Policy Optimization

This paper proposes a sample-efficient neuro-symbolic extension of Proximal Policy Optimization (PPO) that leverages partial logical policy specifications to guide learning in complex, sparse-reward environments, demonstrating superior performance over standard PPO and Reward Machine baselines through two distinct integration strategies.

Original authors: Simone Murari, Celeste Veronese, Daniele Meli

Published 2026-04-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Simone Murari, Celeste Veronese, Daniele Meli

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a robot to navigate a giant, confusing maze. The robot is very smart (it uses "Deep Reinforcement Learning"), but it learns by trial and error. It has to bump into walls, try dead ends, and wait a very long time to get a single "good job" reward. If the maze is huge or the rewards are rare, the robot might never figure it out, or it would take millions of tries.

This paper proposes a way to give the robot a cheat sheet made of simple logic rules, without forcing it to follow those rules blindly. The authors call this a "neuro-symbolic" approach, which is just a fancy way of saying they are mixing the robot's "brain" (neural networks) with a "rulebook" (symbolic logic).

Here is how they did it, using two different methods:

The Two Methods: The "Nudge" and the "Coach"

The researchers took an existing, popular learning algorithm called PPO (Proximal Policy Optimization) and added their logic rules in two different ways.

1. H-PPO-Product: The "Nudge" (Sampling Bias)
Think of this as a friendly guide standing next to the robot at every crossroads.

How it works: When the robot is about to pick a path, the guide says, "Hey, based on the rules we know, this path looks promising."
The trick: The guide doesn't force the robot to take that path. Instead, it just makes that path slightly more likely to be chosen. It's like adding a little weight to the scale.
The fade-out: At the beginning of training, the guide is very loud and helpful. But as the robot learns more on its own, the guide slowly whispers less and less until it disappears completely. This ensures the robot learns to explore on its own eventually, rather than just following orders forever.
Best for: Getting the robot unstuck in huge, empty mazes where it needs to find any good path quickly.

2. H-PPO-SymLoss: The "Coach" (Loss Regularization)
Think of this as a strict coach reviewing the robot's homework after it finishes a run.

How it works: The robot tries to solve the maze. Afterward, the coach looks at the robot's choices and says, "You did okay, but remember the rule: 'If you see a red door, don't open it yet.' You violated that rule, so I'm going to add a small penalty to your score."
The trick: This penalty is added to the robot's learning math. It gently pushes the robot's brain to adjust its internal settings so it makes fewer "rule-breaking" mistakes in the future.
Best for: Fine-tuning the robot once it has already started learning. It helps the robot become very precise and efficient, but it doesn't help much when the robot is completely lost at the start.

The Experiments: Three Different Mazes

The team tested these methods on three different types of "mazes" (computer simulations):

DoorKey: A grid world where the robot must find a specific key to open a specific door.
- Result: The "Nudge" method was amazing here. In the hardest versions (big grids, many keys), the standard robot got stuck, but the "Nudge" robot found the solution quickly. The "Coach" method was slower to start but eventually caught up.
OfficeWorld: A grid with offices, mail, coffee, and plants. The robot has to visit places in a specific order (e.g., get coffee, then mail) without hitting plants.
- Result: The "Coach" method shined here. Once the robot started learning, the "Coach" helped it perfect its routine, achieving the highest scores. The "Nudge" was fast at the start but got stuck at a lower score later on.
WaterWorld: A continuous space with moving balls of different colors. The robot must hit them in a specific color sequence.
- Result: This was the hardest test. The "Nudge" method was the only one that could successfully navigate the complex sequences. The "Coach" method actually struggled here because the rules were too restrictive for the robot to figure out the complex dance on its own.

The Big Takeaway

The main point of the paper is that you don't need to be a perfect expert to help a robot learn. The authors showed that even if the "rulebook" they gave the robot was imperfect or only learned from easy versions of the game, it still helped the robot learn the hard versions much faster.

If you need to get moving fast in a big, empty space: Use the Nudge (H-PPO-Product).
If you need to polish the performance and get the highest score: Use the Coach (H-PPO-SymLoss).

By combining logic rules with standard AI learning, they made the robot learn faster, use fewer tries (samples), and solve problems that standard robots usually give up on. They did this without needing to constantly tweak the robot's settings every time the game got harder.

1. Problem Statement

Deep Reinforcement Learning (DRL), particularly algorithms like Proximal Policy Optimization (PPO), faces significant challenges in sparse-reward environments with long planning horizons and multiple sub-goals.

Sample Inefficiency: Agents require massive amounts of interaction data to converge, making training costly and slow.
Black-Box Nature: Neural policies lack interpretability and formal guarantees.
Limitations of Existing Solutions:
- Reward Shaping (e.g., Reward Machines): Often computationally expensive and highly sensitive to inaccurate heuristics; poor heuristics can degrade performance.
- Purely Neural Approaches: Lack mechanisms to integrate human-readable domain rules directly.
- Purely Symbolic Approaches: Struggle to scale to complex domains due to the difficulty of defining the policy search space accurately.

The authors propose a neuro-symbolic framework that transfers partial logical policy specifications learned in simple instances to guide learning in more complex, challenging settings, thereby improving sample efficiency without requiring hyperparameter retuning.

2. Methodology

The core innovation is a neuro-symbolic extension of PPO that utilizes a Symbolic Policy ( $\pi_{sym}$ ). This policy is a set of logical rules (Horn clauses) mapping environmental features (predicates) to action terms. An online reasoning mechanism translates raw observations into high-level logical predicates, which are evaluated against $\pi_{sym}$ to deduce promising actions.

The paper introduces two distinct integration strategies to inject this logical guidance into the PPO loop:

A. H-PPO-Product (Action-Level Bias)

Mechanism: Modifies the action sampling distribution during the training phase.
Implementation:
- At each time step, the neural policy's action probabilities are reweighted based on whether an action is logically entailed by $\pi_{sym}$ .
- A reweighting term $m_t(a, s)$ increases the probability of logically suggested actions by a factor controlled by a confidence parameter $\lambda$ and an annealing factor $\epsilon_t$ .
- $\epsilon_t$ follows a linear decay schedule, starting high to encourage exploration guided by logic and decaying to zero as training progresses.
Goal: To bias early-stage exploration toward logically sound trajectories, allowing the agent to ignore imperfect symbolic suggestions as the neural policy learns the true environment dynamics.

B. H-PPO-SymLoss (Optimization-Level Regularization)

Mechanism: Augments the PPO loss function with a symbolic regularization term.
Implementation:
- Constructs a reference policy $\pi_{ref}$ based on the symbolic indicator, assigning higher probability mass to logically entailed actions.
- Calculates a ratio $\rho^{sym}_t$ between the current neural policy and this symbolic reference policy (replacing the standard $\pi_{old}$ in the ratio for this specific term).
- Adds a symbolic auxiliary loss $L_{sym}$ (structured similarly to the clipped PPO surrogate) to the total loss function, weighted by a parameter $\Theta$ .
- Like H-PPO-Product, the weight $\Theta$ can be annealed over time.
Goal: To act as a regularizer that aligns the neural policy with logical constraints during optimization, preventing the policy from deviating into sub-optimal regions even if the symbolic rules are imperfect.

3. Key Contributions

Neuro-Symbolic PPO Framework: A novel approach that leverages partial logical rules to guide PPO agents, utilizing either sampling biases (H-PPO-Product) or optimization penalties (H-PPO-SymLoss).
Robustness to Imperfect Knowledge: The methods are designed to work with logical rules induced from simple tasks and transferred to harder ones, even when those rules are incomplete or imperfect.
No Hyperparameter Retuning: The framework allows scaling to larger, more complex domains without re-tuning PPO hyperparameters, as the symbolic guidance adapts the learning process automatically.
Empirical Validation: Extensive evaluation across three standard gridworld benchmarks (DoorKey, OfficeWorld, WaterWorld) demonstrating superior performance over vanilla PPO and Reward Machine baselines.

4. Experimental Results

The authors evaluated their methods on three benchmarks with varying complexity (grid size, number of keys, sequence length):

DoorKey (Navigation with Keys/Doors):
- H-PPO-Product excelled as an exploration driver, achieving the fastest convergence and highest returns, especially in the most challenging 16x16 grid with 4 keys.
- H-PPO-SymLoss reached high returns but converged more slowly.
- Reward Machine (RM) baseline failed completely in the 4-key setting (zero return), highlighting the fragility of reward shaping in complex sparse-reward tasks.
OfficeWorld (Sequential Sub-goals):
- H-PPO-Product showed rapid initial learning but plateaued at a slightly lower return in complex tasks (e.g., DeliverCoffeeAndMail).
- H-PPO-SymLoss started slower but acted as a powerful policy regularizer, ultimately achieving the highest final returns by shaping the policy more effectively in the long run.
WaterWorld (Continuous 2D Physics/Sequences):
- In complex sequence tasks (e.g., RedGreenAndBlueCyanAndMagentaYellow), H-PPO-Product was the only method to successfully navigate the sparse-reward space and reach high returns.
- H-PPO-SymLoss struggled here, confirming that its strength lies in policy consolidation rather than initiating complex exploration sequences from scratch.

Summary of Performance:

H-PPO-Product: Best for exploration in sparse, long-horizon tasks.
H-PPO-SymLoss: Best for policy refinement and maximizing final returns in tasks where some exploration has already occurred.
Both methods consistently outperformed standard PPO and Reward Machines.

5. Significance

This paper addresses a critical bottleneck in DRL: sample efficiency in complex, sparse-reward domains. By integrating symbolic reasoning directly into the PPO algorithmic structure (rather than just as a reward shaper), the authors demonstrate that:

Logical priors can significantly accelerate learning without sacrificing the flexibility of neural networks.
Transfer learning of logical rules from simple to complex tasks is viable and effective.
Different integration strategies (sampling bias vs. loss regularization) serve distinct roles, offering a toolkit for practitioners to choose the right approach based on whether they need better exploration or better policy convergence.

The work bridges the gap between the interpretability of symbolic AI and the scalability of Deep RL, paving the way for more robust and generalizable agents in real-world applications.