Potential Based Reward Shaping for Hierarchical Reinforcement Learning

Yang Gao, Francesca Toni

Reinforcement Learning (RL) agents often struggle with complex, multi-step tasks due to the "curse of dimensionality." As the state space grows, the time required for exploration increases exponentially. Hierarchical Reinforcement Learning (HRL), particularly the MAXQ framework, addresses this by decomposing a large problem into a hierarchy of sub-tasks. However, even within these sub-tasks, agents can spend significant time exploring inefficiently. This paper, presented at IJCAI 2015, introduces PBRS-MAXQ-0, a framework that accelerates learning by integrating Potential-Based Reward Shaping (PBRS) into the MAXQ hierarchy.

The Challenge: Fine-Grained Guidance in Hierarchies

While HRL provides a coarse-grained structure, agents still require guidance to find optimal action sequences within sub-tasks. Previous attempts to provide "hints" often risked changing the agent's optimal policy—a phenomenon known as "reward hacking." The authors sought a method to provide fine-grained advice that speeds up learning without sacrificing the guarantee of convergence to the optimal hierarchical policy.

PBRS-MAXQ-0: Context-Aware Shaping

The proposed PBRS-MAXQ-0 framework combines MAXQ decomposition with Potential-Based Reward Shaping. PBRS is known for its policy invariance, ensuring that additional rewards do not alter the final optimal behavior.

The key innovation lies in the potential function $\Phi(i, s, a)$, which incorporates the parent task $i$, the current state $s$, and the child task $a$. This context-awareness is crucial; for instance, moving toward a specific location might be beneficial for a "Refuel" sub-task but detrimental for a "Deliver Passenger" sub-task. To effectively utilize these shaping rewards during exploration, the authors introduced the BOGLIE (Biased Ordered Greedy in the Limit with Infinite Exploration) policy.

Task hierarchies for the (a) Taxi and (b) Resource Collection domains used in the evaluation.

Experimental Benchmarks

The algorithm was evaluated on two classic RL domains:

  1. Fickle Taxi: A $5 \times 5$ grid where a taxi must manage passenger pickups and drop-offs. The "fickle" variant introduces a 30% chance of destination changes mid-trip.
  2. Resource Collection: A more complex $25 \times 25$ grid world requiring the agent to harvest wood and gold to meet quotas before depositing them at a town hall.

Key Results and Insights

The experiments compared standard MAXQ-0 against PBRS-MAXQ-0 with both "good" (helpful) and "bad" (misleading) heuristics.

  • Accelerated Learning: In both domains, "PBRS-good" reached optimal performance significantly faster than the baseline.
  • Robustness to Misleading Advice: Even when provided with "bad" heuristics—advice that encouraged counterproductive actions—the agent eventually converged to the optimal policy. This demonstrates the theoretical soundness of the approach; bad advice merely delays convergence rather than preventing it.
  • Computational Efficiency: PBRS-MAXQ-0 adds minimal overhead compared to model-based HRL methods, making it a practical choice for complex environments.
Learning performance in the Resource Collection domain. PBRS-good significantly outperforms the baseline, while PBRS-bad eventually converges to the same optimal reward.

Conclusion

PBRS-MAXQ-0 successfully bridges the gap between high-level hierarchical structure and low-level heuristic guidance. By providing a theoretically sound way to inject expert knowledge into the learning process, it offers a robust solution for scaling RL to more complex real-world tasks. Future work may focus on automating the generation of these potential functions and extending the framework to multi-agent settings.

Summary updated

Abstract

Hierarchical Reinforcement Learning (HRL) outperforms many 'flat' Reinforcement Learning (RL) algorithms in some application domains. However, HRL may need longer time to obtain the optimal policy because of its large action space. Potential Based Reward Shaping (PBRS) has been widely used to incorporate heuristics into flat RL algorithms so as to reduce their exploration. In this paper, we investigate the integration of PBRS and HRL, and propose a new algorithm: PBRS-MAXQ- 0. We prove that under certain conditions, PBRS-MAXQ- 0 is guaranteed to converge. Empirical results show that PBRS-MAXQ-0 significantly outperforms MAXQ-0 given good heuristics, and can converge even when given misleading heuristics.
BibTeX
@inproceedings{gao2015potential,
  author = {Yang Gao and Francesca Toni},
  title = {{Potential Based Reward Shaping for Hierarchical Reinforcement Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure