Abstract
Reward machines inform reinforcement learning agents about the reward structure of the environment and often drastically speed up the learning process. However, reward machines only accept Boolean features such as robot-reached-gold. Consequently, many inherently numeric tasks cannot profit from the guidance offered by reward machines. To address this gap, we aim to extend reward machines with numeric features such as distance-to-gold. For this, we present two types of reward machines: numeric-Boolean and numeric. In a numeric-Boolean reward machine, distance-to-gold is emulated by two Boolean features distance-to-gold-decreased and robot-reached-gold. In a numeric reward machine, distance-to-gold is used directly alongside the Boolean feature robot-reached-gold. We compare our new approaches to a baseline reward machine in the Craft domain, where the numeric feature is the agent-to-target distance. We use cross-product Q-learning, Q-learning with counter-factual experiences, and the options framework for learning. Our experimental results show that our new approaches significantly outperform the baseline approach. Extending reward machines with numeric features opens up new possibilities of using reward machines in inherently numeric tasks.
Introduction
Reinforcement Learning (RL) agents often struggle with "sparse rewards," where feedback is infrequent and delayed. Reward Machines (RMs) address this by providing a high-level automaton that tracks sub-goal progress. However, traditional RMs are limited to Boolean logic (e.g., "Has the agent reached the goal?"). This binary view ignores continuous information, such as the distance to a target, which could provide a much denser and more informative signal for learning.
Methodology: Extending Reward Machines
To leverage numeric information, we propose two extensions to the RM framework:
- Numeric-Boolean RMs: These bridge the gap by emulating numeric features using Boolean triggers like
distance-decreasedandat-target. This allows the RM to provide incremental rewards as the agent approaches a goal. - Numeric RMs: These directly incorporate numeric features into the reward function. For instance, the RM can output a reward of $-d$ (where $d$ is the distance to the current sub-goal) at each step. This provides a continuous signal that naturally guides the agent toward the target.
We integrated these RMs into three learning frameworks: Q-learning over the cross-product (QRM), Counterfactual Experience (CRM), and Hierarchical RL (HRM).
Experimental Setup
We evaluated these approaches in the Craft domain, a grid-world environment. Tasks involved visiting objects a, b, and c in sequence. We tested two map configurations: 1a1b1c (one of each object) and 2a2b2c (two of each object). The latter requires the agent to intelligently select the nearest instance of a target object.
Results and Analysis
Our experimental results demonstrate that Numeric RMs significantly accelerate convergence compared to Boolean baselines. In complex sequential tasks like a-b-c, methods using Numeric RMs reached optimal performance much faster.
Key findings include:
- CRM + Numeric Efficiency: The combination of Counterfactual Experience and Numeric RMs (
crm-num) was particularly effective, often finding optimal policies in a fraction of the steps required by other methods. - Robustness of Numeric RMs: Unlike Numeric-Boolean RMs, which require careful tuning of intermediate rewards to avoid sub-optimal "shortest-path traps," Numeric RMs using $-d$ as a reward are mathematically guaranteed to find the shortest path in single-target tasks.
- Tie-Breaking: In maps with multiple target instances (
2a2b2c), Numeric RMs helped agents distinguish between targets based on proximity, a task where Boolean methods struggled.
Conclusion
Extending Reward Machines with numeric features provides a powerful mechanism for guiding RL agents in inherently numeric environments. While Numeric-Boolean RMs offer a useful bridge, direct Numeric RMs provide a more robust and efficient signal. Future work will focus on extending these methods to continuous state spaces and high-dimensional inputs.
Reference: Levina, K., Pappas, N., Karapantelakis, A., Feljan, A. V., & Seipp, J. (2024). Numeric Reward Machines. arXiv:2404.19370v1 [cs.AI].
Summary updated