A Hierarchical Bayesian Approach to Inverse Reinforcement Learning with Symbolic Reward Machines

Weichao Zhou, Wenchao Li

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

Abstract

A misspecified reward can degrade sample efficiency and induce undesired behaviors in reinforcement learning (RL) problems. We propose symbolic reward machines for incorporating high-level task knowledge when specifying the reward signals. Symbolic reward machines augment existing reward machine formalism by allowing transitions to carry predicates and symbolic reward outputs. This formalism lends itself well to inverse reinforcement learning, whereby the key challenge is determining appropriate assignments to the symbolic values from a few expert demonstrations. We propose a hierarchical Bayesian approach for inferring the most likely assignments such that the concretized reward machine can discriminate expert demonstrated trajectories from other trajectories with high accuracy. Experimental results show that learned reward machines can significantly improve training efficiency for complex RL tasks and generalize well across different task environment configurations.
BibTeX
@inproceedings{zhou2022hierarchical,
  author = {Weichao Zhou and Wenchao Li},
  title = {{A Hierarchical Bayesian Approach to Inverse Reinforcement Learning with Symbolic Reward Machines}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=C1z-KQQDNwY},
}
Figure