Heuristic-Guided Reinforcement Learning

Ching-An Cheng, Andrey Kolobov, Adith Swaminathan

Abstract

We provide a framework for accelerating reinforcement learning (RL) algorithms by heuristics constructed from domain knowledge or offline data. Tabula rasa RL algorithms require environment interactions or computation that scales with the horizon of the sequential decision-making task. Using our framework, we show how heuristic-guided RL induces a much shorter-horizon subproblem that provably solves the original task. Our framework can be viewed as a horizon-based regularization for controlling bias and variance in RL under a finite interaction budget. On the theoretical side, we characterize properties of a good heuristic and its impact on RL acceleration. In particular, we introduce the novel concept of an improvable heuristic, a heuristic that allows an RL agent to extrapolate beyond its prior knowledge. On the empirical side, we instantiate our framework to accelerate several state-of-the-art algorithms in simulated robotic control tasks and procedurally generated games. Our framework complements the rich literature on warm-starting RL with expert demonstrations or exploratory datasets, and introduces a principled method for injecting prior knowledge into RL.

Introduction: The Curse of the Horizon

A major bottleneck in reinforcement learning is the "curse of the horizon." In complex environments like Dota 2 or StarCraft II, agents may take thousands of steps before receiving a meaningful reward signal. This long delay makes credit assignment—identifying which specific actions led to a successful outcome—statistically and computationally difficult. Consequently, sample complexity often grows quadratically or worse with the task horizon.

While common approaches involve "warm-starting" agents with human demonstrations, these methods do not fundamentally alter the difficulty of the long-horizon Markov Decision Process (MDP). This research proposes Heuristic-Guided Reinforcement Learning (HuRL), a framework that uses a heuristic function—a guess of the optimal value function—to transform a long-term problem into a sequence of significantly easier, short-term subproblems.

Methods: Horizon-Based Regularization

HuRL treats heuristics as a form of horizon-based regularization. Given an MDP with a discount factor $\gamma$ and a heuristic function $h(s)$, HuRL solves a modified MDP characterized by reward reshaping and horizon shortening:

  1. Reward Reshaping: The new reward is defined as $\tilde{r}(s, a) = r(s, a) + (1 - \lambda)\gamma \mathbb{E}[h(s')]$.
  2. Horizon Shortening: The effective discount factor is reduced to $\tilde{\gamma} = \lambda\gamma$.
Visualizing value heatmaps (a), policy behaviors (b), and the impact of heuristic quality and $\lambda$ on the value function (c).

Here, $\lambda \in [0, 1]$ acts as a mixing coefficient. A small $\lambda$ creates a short-horizon problem relying heavily on the heuristic, while increasing $\lambda$ toward 1 transitions the agent back to the original long-horizon task. This mechanism creates a natural learning curriculum.

Key Insights: Bias, Variance, and Pessimism

The framework's effectiveness stems from a fundamental bias-variance trade-off. Shortening the horizon reduces the variance of the learning signal, accelerating convergence. However, an inaccurate heuristic introduces bias. HuRL manages this by dynamically increasing $\lambda$ over time.

Crucially, the authors find that pessimistic heuristics (those that never overestimate the true value) are superior to optimistic ones. Such heuristics allow the agent to "extrapolate" and discover policies that outperform the heuristic itself. This leads to the concept of an improvable heuristic—one that is lower than its own Bellman backup—which theoretically guarantees lower bias in the HuRL framework.

Empirical Results

The authors evaluated HuRL on MuJoCo robotic control tasks and the Procgen game suite. Heuristics were derived from domain knowledge or trained on offline data from mediocre policies.

  • Performance Gains: In MuJoCo, HuRL achieved optimal performance significantly faster than standard Soft Actor-Critic (SAC) or Potential-Based Reward Shaping (PBRS). In sparse-reward tasks where standard RL failed, HuRL succeeded efficiently.
  • Robustness: In the Procgen suite, HuRL improved performance in half of the 16 games and matched state-of-the-art PPO in the others, even with "naive" heuristics generated from mixed-quality offline data.
  • Ablation Studies: Results confirmed that performance gains were specifically due to horizon shortening rather than just additional data. Prematurely increasing $\lambda$ (maintaining a long horizon) significantly slowed learning.

Conclusion

HuRL provides a principled method for injecting prior knowledge into RL by effectively shortening the task horizon. While robust, the framework's performance still depends on heuristic quality and the $\lambda$-scheduling. Future research may focus on adaptive $\lambda$-tuning and more scalable methods for constructing pessimistic heuristics from high-dimensional data like pixels.

Summary updated

Abstract

We provide a framework for accelerating reinforcement learning (RL) algorithms by heuristics constructed from domain knowledge or offline data. Tabula rasa RL algorithms require environment interactions or computation that scales with the horizon of the sequential decision-making task. Using our framework, we show how heuristic-guided RL induces a much shorter-horizon subproblem that provably solves the original task. Our framework can be viewed as a horizon-based regularization for controlling bias and variance in RL under a finite interaction budget. On the theoretical side, we characterize properties of a good heuristic and its impact on RL acceleration. In particular, we introduce the novel concept of an improvable heuristic, a heuristic that allows an RL agent to extrapolate beyond its prior knowledge. On the empirical side, we instantiate our framework to accelerate several state-of-the-art algorithms in simulated robotic control tasks and procedurally generated games. Our framework complements the rich literature on warm-starting RL with expert demonstrations or exploratory datasets, and introduces a principled method for injecting prior knowledge into RL.
BibTeX
@inproceedings{cheng2021heuristic,
  author = {Ching-An Cheng and Andrey Kolobov and Adith Swaminathan},
  title = {{Heuristic-Guided Reinforcement Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=HipwnJKnp3},
}
Figure