Dynamic Automaton-Guided Reward Shaping for Monte Carlo Tree Search

Alvaro Velasquez, Brett Bissey, Lior Barak, Andre Beckus, Ismail Alkhouri, Daniel Melcer, George K. Atia

Introduction

Reinforcement learning (RL) often struggles with the "sparse reward" problem, where an agent only receives feedback at the completion of a complex task. Without intermediate guidance, agents may explore millions of states before accidentally reaching a goal. While manual reward shaping can provide "breadcrumbs," it is labor-intensive and prone to "reward hacking"—where agents exploit loopholes to gain rewards without fulfilling the actual objective. Furthermore, traditional RL agents often fail to transfer knowledge between environments with different physical layouts but identical logical goals.

This paper introduces MCTSA, a framework that integrates Monte Carlo Tree Search (MCTS) with formal automata to provide dynamic reward shaping. By representing high-level goals through Finite Automata, the researchers developed a mechanism that guides agents through complex tasks and enables efficient knowledge transfer across varying environment scales.

Methodology: Automaton-Guided Reward Shaping (AGRS)

The core of the MCTSA approach lies in decoupling the logical goal from the physical environment through a multi-step process:

  1. Goal Representation via LTLf: Complex, multi-step objectives (e.g., "Collect wood, then visit the factory, then return home") are defined using Linear Temporal Logic (LTLf). This logic is converted into a Deterministic Finite Automaton (DFA), where nodes represent the progress of the mission.
  2. Dynamic Shaping: Unlike static reward functions, AGRS calculates the empirical expected value of transitions within the automaton. As the agent explores paths during MCTS simulations, it tracks which automaton transitions lead to successful outcomes in the specific environment.
  3. The MCTSA Algorithm: The standard MCTS selection policy is modified to include a new term, $Y$, representing the AGRS value. The selection formula balances the action value ($Q$), an exploration bonus ($U$), and the progress toward an accepting state in the automaton ($Y$).
Mapping environment states to automaton transitions for goal-oriented guidance.

Experimental Setup and Results

The researchers evaluated MCTSA in randomized grid-world environments, such as Blind Craftsman (a multi-stage crafting task) and Treasure Pit (a sequential collection task). The integration of automaton-based guidance yielded significant performance gains:

  • Superior Sample Efficiency: In the "Blind Craftsman" task, MCTSA reached a near 100% win rate significantly faster than the vanilla MCTS baseline.
  • Performance under Constraints: MCTSA proved robust even with low computational budgets. In tasks where the agent was limited to few expansions per move, MCTSA maintained a reliable policy while vanilla MCTS failed to learn.
  • Accelerated Transfer Learning: By transferring learned automaton transition values from a 10x10 grid to a 25x25 grid, agents reached high performance levels in half the time required for training from scratch.
Comparison of win rates over play steps between MCTS with automaton-guided reward shaping and the vanilla baseline.

Key Insights and Future Work

The most striking insight is that the "value" of a goal transition (e.g., how beneficial it is to pick up wood) is often invariant to map size. This abstraction allows the agent to learn the "logic" of the task separately from the "physics" of the environment.

While currently dependent on human-provided LTLf formulas, future work aims to automate goal discovery and extend the framework to continuous domains like robotics. By making reward shaping dynamic and goal-oriented, MCTSA provides a scalable path toward solving complex, long-horizon tasks in reinforcement learning.

Summary updated

Abstract

Reinforcement learning and planning have been revolutionized in recent years, due in part to the mass adoption of deep convolutional neural networks and the resurgence of powerful methods to refine decision-making policies. However, the problem of sparse reward signals and their representation remains pervasive in many domains. While various rewardshaping mechanisms and imitation learning approaches have been proposed to mitigate this problem, the use of humanaided artificial rewards introduces human error, sub-optimal behavior, and a greater propensity for reward hacking. In this paper, we mitigate this by representing objectives as automata in order to define novel reward shaping functions over this structured representation. In doing so, we address the sparse rewards problem within a novel implementation of Monte Carlo Tree Search (MCTS) by proposing a reward shaping function which is updated dynamically to capture statistics on the utility of each automaton transition as it pertains to satisfying the goal of the agent. We further demonstrate that such automaton-guided reward shaping can be utilized to facilitate transfer learning between different environments when the objective is the same.
BibTeX
@inproceedings{velasquez2021dynamic,
  author = {Alvaro Velasquez and Brett Bissey and Lior Barak and Andre Beckus and Ismail Alkhouri and Daniel Melcer and George K. Atia},
  title = {{Dynamic Automaton-Guided Reward Shaping for Monte Carlo Tree Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i13.17427},
}
Figure