Heuristic-Guided Reinforcement Learning

Ching-An Cheng, Andrey Kolobov, Adith Swaminathan

TL;DR

Heuristic-Guided Reinforcement Learning (HuRL) is a framework designed to accelerate RL by using prior knowledge to effectively shorten the decision-making horizon. By blending a heuristic value function into the reward and lowering the discount factor, HuRL creates a sequence of easier subproblems that guide the agent toward the optimal policy much faster than standard "tabula rasa" methods.

The Challenge of Long-Horizon Tasks

Reinforcement Learning (RL) has achieved remarkable feats, but it often requires a staggering amount of data and compute. A primary culprit is the long-horizon nature of many tasks. When an agent has to make thousands of decisions before seeing a meaningful reward, "credit assignment"—figuring out which specific action led to a later success—becomes a statistical nightmare.

The sample complexity of RL grows quadratically (or worse) with the horizon. While researchers often use "warm-starting" (initializing with expert demonstrations) to speed up training, these methods do not fundamentally change the difficulty of the long-term credit assignment problem itself.

The HuRL Framework

To address this, the authors introduce HuRL, which treats prior knowledge (heuristics) as a tool for horizon-based regularization.

The core idea is to solve a modified Markov Decision Process (MDP) where the horizon is artificially shortened. Given an original MDP and a heuristic function $h(s)$ (a guess of the optimal value function), HuRL defines a reshaped reward $\tilde{r}$ and a smaller discount factor $\tilde{\gamma}$:

  1. Reward Reshaping: $\tilde{r}(s, a) := r(s, a) + (1 - \lambda)\gamma \mathbb{E}_{s' \sim P(\cdot|s,a)}[h(s')]$
  2. Discount Reduction: $\tilde{\gamma} := \lambda\gamma$

Here, $\lambda \in [0, 1]$ is a mixing coefficient. When $\lambda$ is small, the agent faces a very short-horizon problem heavily guided by the heuristic. As training progresses, HuRL uses a curriculum where $\lambda$ gradually increases to 1, eventually returning the agent to the original long-horizon task.

A toy example illustrating how a good heuristic allows HuRL to find the optimal policy even with a very short horizon (small $\lambda$), whereas a bad heuristic requires a much larger $\lambda$.

Key Insights

  • Bias-Variance Trade-off: HuRL views the horizon as a regularization parameter. A shorter horizon (small $\lambda$) reduces the variance of the learning signal, making it easier to learn. However, it introduces bias if the heuristic is imperfect.
  • Pessimism is a Virtue: In a surprising twist for those familiar with A search, the authors show that pessimistic heuristics (those that underestimate the true value) are actually better for RL. They introduce the concept of an improvable heuristic*, which allows the agent to extrapolate and improve upon its prior knowledge rather than being trapped by it.
  • Superiority over PBRS: Unlike Potential-Based Reward Shaping (PBRS), which keeps the original discount factor, HuRL actually shortens the effective horizon. This makes the credit assignment problem fundamentally easier for the underlying RL algorithm.

Empirical Results

The framework was evaluated on several standard and modified benchmarks, including MuJoCo Robotics, a custom Sparse-Reacher task, and Procgen Games. Heuristics were derived from engineered domain knowledge and offline data from previously collected behavioral policies.

The empirical results demonstrate that HuRL significantly outperforms standard RL baselines and PBRS in terms of learning speed and final performance:

  • Sparse Rewards: In the Sparse-Reacher task, standard SAC and PBRS failed to learn, while HuRL converged rapidly to the optimal performance.
  • MuJoCo Benchmarks: HuRL (using Monte-Carlo heuristics) showed much faster convergence across various robotics tasks. For example, in the Humanoid-v2 environment, HuRL reached high return levels significantly earlier than vanilla SAC or SAC with behavioral cloning warm-starts.
  • Ablation Studies: The authors confirmed that the speedup is specifically due to horizon shortening. Increasing $\lambda$ too early—making the problem "harder" too fast—leads to a performance drop.

Limitations and Future Work

While highly effective, HuRL has a few limitations. First, although the $\lambda \to 1$ curriculum makes HuRL robust, a very poor heuristic can still slow down initial learning. Second, the current mixing coefficient schedule requires manual tuning; future work could involve adaptively tuning $\lambda$ based on the agent's performance or heuristic quality. Finally, constructing high-quality pessimistic heuristics from raw, high-dimensional offline data remains an ongoing challenge tied to the broader progress of the offline RL field.

Summary updated

Abstract

We provide a framework to accelerate reinforcement learning (RL) algorithms by heuristics that are constructed by 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 sub-problem 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. In theory, we characterize the properties of a good heuristic and the resulting impact on RL acceleration. In particular, we introduce the novel concept of an improvable heuristic that can allow any RL agent to conservatively extrapolate beyond its prior knowledge. In practice, 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 using expert demonstrations or exploratory data-sets, and creates a unified channel to inject 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