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 thatscales with the horizon of the sequential decision-making task. Using ourframework, we show how heuristic-guided RL induces a much shorter-horizonsubproblem that provably solves the original task. Our framework can be viewedas a horizon-based regularization for controlling bias and variance in RL undera finite interaction budget. On the theoretical side, we characterizeproperties of a good heuristic and its impact on RL acceleration. Inparticular, we introduce the novel concept of an improvable heuristic, aheuristic that allows an RL agent to extrapolate beyond its prior knowledge. Onthe empirical side, we instantiate our framework to accelerate severalstate-of-the-art algorithms in simulated robotic control tasks and procedurallygenerated games. Our framework complements the rich literature on warm-startingRL with expert demonstrations or exploratory datasets, and introduces aprincipled method for injecting prior knowledge into RL.