  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.
