TL;DR
This paper introduces "Symbolic Reward Machines" (SRMs), a novel way to represent reward functions in Reinforcement Learning (RL) that incorporates high-level task knowledge using symbolic logic. They also propose a hierarchical Bayesian approach to automatically learn the specific values within these SRMs from expert demonstrations, significantly improving RL agent performance and sample efficiency on complex tasks.
What Problem Does This Paper Address?
Designing effective reward functions for complex Reinforcement Learning (RL) tasks is notoriously difficult. Poorly designed rewards can lead to inefficient learning or undesirable "reward hacking" behaviors. While "Reward Machines" (RMs) offer a structured way to define rewards using finite-state automata, they can become cumbersome and still require manual assignment of reward values. This paper addresses the challenge of automatically inferring these reward values from expert demonstrations, enabling more interpretable and efficient RL.
Methods
The core innovation is the Symbolic Reward Machine (SRM). SRMs extend traditional RMs by allowing transitions to include symbolic predicates and functions, effectively embedding high-level task logic. This makes reward specification more concise and interpretable.
To learn the "holes" (symbolic values) within these SRMs, the authors propose a hierarchical Bayesian approach. This method leverages expert demonstrations and a generative adversarial framework (similar to GAIL) to train a discriminator that distinguishes expert trajectories from agent trajectories. The key is that the SRM itself acts as the reward function for this discriminator. Because SRMs are not directly differentiable with respect to their symbolic values, a sampler is used to draw candidate instantiations of these values. This approach allows for learning complex, non-Markovian reward structures.
Datasets
The paper evaluates their approach on three Mini-Grid environments:
- DoorKey: An agent needs to pick up a key, unlock a door, and reach a target.
- KeyCorridor: Similar to DoorKey but with more complex navigation and door mechanics.
- ObstructedMaze: A more challenging task involving locked doors, hidden keys, and obstructed paths.
The environments are varied in size and object placement to test generalization.
Key Insights and Ideas
- SRMs offer a powerful abstraction: By using symbolic logic, SRMs can capture complex task structures and human insights more effectively than traditional RMs or simple feature-based rewards.
- Learning reward structure is crucial: The paper demonstrates that automatically inferring the specific values within an SRM from expert data is key to achieving high performance, outperforming manually assigned values.
- Hierarchical Bayesian inference is effective for non-differentiable rewards: The proposed method successfully navigates the challenges of learning symbolic, non-differentiable reward functions by combining generative adversarial learning with Bayesian inference and sampling.
- Generalization is possible: SRMs learned in one environment configuration can be effectively used to train agents in different configurations of the same task, highlighting the robustness of the learned reward structure.
Key Results
- SRMs, when learned using the proposed hierarchical Bayesian approach, significantly improve training efficiency and achieve higher average returns compared to agents trained with default rewards or other Inverse Reinforcement Learning (IRL) baselines (GAIL, GAN-GCL).
- The approach demonstrates high sample efficiency, achieving good performance with as few as one expert demonstration.
- SRMs concretized in smaller environments generalize well to larger and differently configured environments for the same tasks.
- The learned SRMs enable agents to achieve state-of-the-art performance on challenging Mini-Grid tasks.
Limitations and Future Work
- Training Overhead: The current implementation of Algorithm 1 can incur substantial overhead due to sampling and evaluating candidate SRM instantiations. The authors propose a solution to reduce this by evaluating the SRM without hole assignments first.
- Symbolic Constraint Impact: While symbolic constraints are beneficial, removing or weakening them can sometimes lead to comparable performance with more interactions, suggesting a trade-off between constraint complexity and learning speed.
- Future Work: The authors suggest future work will focus on reducing human effort in designing SRMs, implying further automation or more intuitive design tools.
Summary updated