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.
Experimental Benchmarks
The algorithm was evaluated on two classic RL domains:
- 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.
- 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.
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