Heuristic-Guided Reinforcement Learning
Year: 2022

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.

heading: 1 Introduction
text: Many recent empirical successes of reinforcement learning (RL) require solving problems with very long decision-making horizons. OpenAI Five [1] used episodes that were 20000 timesteps on average, while AlphaStar [2] used roughly 5000 timesteps. Long-term credit assignment is a very challenging statistical problem, with the sample complexity growing quadratically (or worse) with the horizon [3]. Long horizons (or, equivalently, large discount factors) also increase RL’s computational burden, leading to slow optimization convergence [4]. This makes RL algorithms require prohibitively large amounts of interactions and compute: even with tuned hyperparameters, AlphaStar needed over 108 samples and OpenAI Five needed over 107 PFLOPS of compute.
A popular approach to mitigate the statistical and computational issues of tabula rasa RL methods is to warm-start or regularize learning with prior knowledge [1, 2, 5–10]. For instance, AlphaStar learned a policy and value function from human demonstrations and regularized the RL agent using imitation learning (IL). AWAC [9] warm-started a policy using batch policy optimization on exploratory datasets. While these approaches have been effective in different domains, none of them explicitly address RL’s complexity dependence on horizon.
In this paper, we propose a complementary regularization technique that relies on heuristic value functions, or heuristics1 for short, to effectively shorten the problem horizon faced by an online RL agent for fast learning. We call this approach Heuristic-Guided Reinforcement Learning (HuRL). The core idea is simple: given a Markov decision process (MDP) M = (S,A, P, r, γ) and a heuristic h : S → R, we select a mixing coefficient λ ∈ [0, 1] and have the agent solve a new MDP M̃ = (S,A, P, r̃, γ̃) with a reshaped reward and a smaller discount (i.e. a shorter horizon):
r̃(s, a) := r(s, a) + (1− λ)γEs′∼P (·|s,a)[h(s′)] and γ̃ := λγ. (1) 1We borrow this terminology from the planning literature to refer to guesses of V ∗ in an MDP [11].
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
HuRL effectively introduces horizon-based regularization that determines whether long-term value information should come from collected experiences or the heuristic. By modulating the effective horizon via λ, we trade off the bias and the complexity of solving the reshaped MDP. HuRL with λ = 1 recovers the original problem and with λ = 0 creates an easier contextual bandit problem [12].
A heuristic h in HuRL represents a prior guess of the desired long-term return of states, which ideally is the optimal value function V ∗ of the unknown MDPM. When the heuristic h captures the state ordering of V ∗ well, conceptually, it becomes possible to make good long-term decisions by short-horizon planning or even acting greedily. How do we construct a good heuristic? In the planning literature, this is typically achieved by solving a relaxation of the original problem [13– 15]. Alternatively, one can learn it from batch data collected by exploratory behavioral policies (as in offline RL [16]) or from expert policies (as in IL [17]).2 For some dense reward problems, a zero heuristic can be effective in reducing RL complexity, as exploited by the guidance discount framework [18–23]. In this paper, we view heuristics as a unified representation of various forms of prior knowledge, such as expert demonstrations, exploratory datasets, and engineered guidance.
Although the use of heuristics to accelerate search has been popular in planning and control algorithms, e.g., A* [24], MCTS [25], and MPC [7, 26–28], its theory is less developed for settings where the MDP is unknown. The closest work in RL is potential-based reward shaping (PBRS) [29], which reshapes the reward into r̄(s, a) = r(s, a)+γEs′|s,a[h(s′)]−h(s) while keeping the original discount. PBRS can use any heuristic to reshape the reward while preserving the ordering of policies. However, giving PBRS rewards to an RL algorithm does not necessarily lead to faster learning, because the base RL algorithm would still seek to explore to resolve long-term credit assignment. HuRL allows common RL algorithms to leverage the short-horizon potential provided by a heuristic to learn faster.
In this work, we provide a theoretical foundation of HuRL to enable adopting heuristics and horizon reduction for accelerating RL, combining advances from the PBRS and the guidance discount literatures. On the theoretical side, we derive a bias-variance decomposition of HuRL’s horizon-based regularization in order to characterize the solution quality as a function of λ and h. Using this insight, we provide sufficient conditions for achieving an effective trade-off, including properties required of a base RL algorithm that solves the reshaped MDP M̃λ. Furthermore, we define the novel concept of an improvable heuristic and prove that good heuristics for HuRL can be constructed from data using existing pessimistic offline RL algorithms (such as pessimistic value iteration [30, 31]).
The effectiveness of HuRL depends on the heuristic quality, so we design HuRL to employ a sequence of mixing coefficients (i.e. λs) that increases as the agent gathers more data from the environment. Such a strategy induces a learning curriculum that enables HuRL to remain robust to non-ideal heuristics. HuRL starts off by guiding the agent’s search direction with a heuristic. As the agent becomes more experienced, it gradually removes the guidance and lets the agent directly optimize the true long-term return. We empirically validate HuRL in MuJoCo [32] robotics control problems and Procgen games [33] with various heuristics and base RL algorithms. The experimental results demonstrate the versatility and effectiveness of HuRL in accelerating RL algorithms.

heading: 2 Preliminaries

heading: 2.1 Notation
text: We focus on discounted infinite-horizon Markov Decision Processes (MDPs) for ease of exposition. The technique proposed here can be extended to other MDP settings.3 A discounted infinite-horizon MDP is denoted as a 5-tupleM = (S,A, P, r, γ), where S is the state space, A is the action space, P (s′|s, a) is the transition dynamics, r(s, a) is the reward function, and γ ∈ [0, 1) is the discount factor. Without loss of generality, we assume r : S×A → [0, 1]. We allow the state and action spaces S and A to be either discrete or continuous. Let ∆(·) denote the space of probability distributions. A decision-making policy π is a conditional distribution π : S → ∆(A), which can be deterministic. We define some shorthand for writing expectations: For a state distribution d ∈ ∆(S) and a function V : S → R, we define V (d) := Es∼d[V (s)]; similarly, for a policy π and a function Q : S ×A → R, we define Q(s, π) := Ea∼π(·|s)[Q(s, a)]. Lastly, we define Es′|s,a := Es′∼P (·|s,a).
2We consider the RL setting for imitation where we suppose the rewards of expert trajectories are available. 3The results here can be readily applied to finite-horizon MDPs; for other infinite-horizon MDPs, we need
further, e.g., mixing assumptions for limits to exist.
Central to solving MDPs are the concepts of value functions and average distributions. For a policy π, we define its state value function V π as V π(s) := Eρπs [ ∑∞ t=0 γ
tr(st, at)] , where ρπs denotes the trajectory distribution of s0, a0, s1, . . . induced by running π starting from s0 = s. We define the state-action value function (or the Q-function) as Qπ(s, a) := r(s, a) + γEs′|s,a[V π(s′)]. We denote the optimal policy as π∗ and its state value function as V ∗ := V π ∗ . Under the assumption that rewards are in [0, 1], we have V π(s), Qπ(s, a) ∈ [0, 11−γ ] for all π, s ∈ S, and a ∈ A. We denote the initial state distribution of interest as d0 ∈ ∆(S) and the state distribution of policy π at time t as dπt , with d π 0 = d0. Given d0, we define the average state distribution of a policy π as
dπ := (1− γ) ∑∞ t=0 γ tdπt . With a slight abuse of notation, we also write d π(s, a) := dπ(s)π(a|s).

heading: 2.2 Setup: Reinforcement Learning with Heuristics
text: We consider RL with prior knowledge expressed in the form of a heuristic value function. The goal is to find a policy π that has high return through interactions with an unknown MDPM, i.e., maxπ V
π(d0). While the agent here does not fully knowM, we suppose that, before interactions start the agent is provided with a heuristic h : S → R which the agent can query throughout learning. The heuristic h represents a prior guess of the optimal value function V ∗ ofM. Common sources of heuristics are domain knowledge as typically employed in planning, and logged data collected by exploratory or by expert behavioral policies. In the latter, a heuristic guess of V ∗ can be computed from the data by offline RL algorithms. For instance, when we have trajectories of an expert behavioral policy, Monte-Carlo regression estimate of the observed returns may be a good guess of V ∗.
Using heuristics to solve MDP problems has been popular in planning and control, but its usage is rather limited in RL. The closest provable technique in RL is PBRS [29], where the reward is modified into r(s, a) := r(s, a) + γEs′|s,a[h(s′)] − h(s). It can be shown that this transformation does not introduce bias into the policy ordering, and therefore solving the new MDPM := (S,A, P, r, γ) would yield the same optimal policy π∗ ofM. Conceptually when the heuristic is the optimal value function h = V ∗, the agent should be able to find the optimal policy π∗ ofM by acting myopically, as V ∗ already contains all necessary long-term information for good decision making. However, running an RL algorithm with the PBRS reward (i.e. solvingM := (S,A, P, r, γ)) does not take advantage of this shortcut. To make learning efficient, we need to also let the base RL algorithm know that acting greedily (i.e., using a smaller discount) with the shaped reward can yield good policies. An intuitive idea is to run the RL algorithm to maximize V π
λ(d0), where V π
λ denotes the value function of π in an MDPMλ := (S,A, P, r, λγ) for some λ ∈ [0, 1]. However this does not always work. For example, when λ = 0, maxπ V π
λ(d0) only optimizes for the initial states d0, but obviously the agent is going to encounter other states in M. We next propose a provably correct version, HuRL, to leverage this short-horizon insight.

heading: 3 Heuristic-Guided Reinforcement Learning
text: We propose a general framework, HuRL, for leveraging heuristics to accelerate RL. In contrast to tabula rasa RL algorithms that attempt to directly solve the long-horizon MDPM, HuRL uses a heuristic to guide the agent in solving a sequence of short-horizon MDPs so as to amortize the complexity of long-term credit assignment. In effect, HuRL creates a heuristic-based learning curriculum to help the agent learn faster.

heading: 3.1 Algorithm
text: HuRL takes a reduction-based approach to realize the idea of heuristic guidance. As summarized in Algorithm 1, HuRL takes a heuristic h : S → R and a base RL algorithm L as input, and outputs an approximately optimal policy for the original MDPM. During training, HuRL iteratively runs the base algorithm L to collect data from the MDPM and then uses the heuristic h to modify the agent’s collected experiences. Namely, in iteration n, the agent interacts with the original MDPM and saves the raw transition tuples4 Dn = {(s, a, r, s′)} (line 2). HuRL then defines a reshaped MDP M̃n := (S,A, P, r̃n, γ̃n) (line 3) by changing the rewards and lowering the discount factor:
r̃n(s, a) := r(s, a) + (1− λn)γEs′|s,a[h(s′)] and γ̃n := λnγ, (2) 4If L learns only with trajectories, we transform each tuple and assemble them to get the modified trajectory.
Algorithm 1 Heuristic-Guided Reinforcement Learning (HuRL) Require: MDPM = (S,A, P, r, γ), RL algorithm L, heuristic h, mixing coefficients {λn}.
1: for n = 1, . . . , N do 2: Dn ← L.CollectData(M) 3: Get λn from {λn} and construct M̃n = (S,A, P, r̃n, γ̃n) according to (2) using h and λn 4: πn ← L.Train(Dn, M̃n) 5: end for 6: return πN
where λn ∈ [0, 1] is the mixing coefficient. The new discount γ̃n effectively gives M̃n a shorter horizon thanM’s, while the heuristic h is blended into the new reward in (2) to account for the missing long-term information. We call γ̃n = λnγ in (2) the guidance discount to be consistent with prior literature [20], which can be viewed in terms of our framework as using a zero heuristic. In the last step (line 4), HuRL calls the base algorithm L to perform updates with respect to the reshaped MDP M̃n. This is realized by 1) setting the discount factor used in L to γ̃n, and 2) setting the sampled reward to r+ (γ − γ̃n)h(s′) for every transition tuple (s, a, r, s′) collected fromM. We remark that the base algorithm L in line 2 always collects trajectories of lengths proportional to the original discount γ, while internally the optimization is done with a lower discount γ̃n in line 4.
Over the course of training, HuRL repeats the above steps with a sequence of increasing mixing coefficients {λn}. From (2) we see that as the agent interacts with the environment, the effects of the heuristic in MDP reshaping decrease and the effective horizon of the reshaped MDP increases.

heading: 3.2 HuRL as Horizon-based Regularization
text: We can think of HuRL as introducing a horizon-based regularization for RL, where the regularization center is defined by the heuristic and its strength diminishes as the mixing coefficient increases. As the agent collects more experiences, HuRL gradually removes the effects of regularization and the agent eventually optimizes for the original MDP.
HuRL’s regularization is designed to reduce learning variance, similar to the role of regularization in supervised learning. Unlike the typical weight decay imposed on function approximators (such as the agent’s policy or value networks), our proposed regularization leverages the structure of MDPs to regulate the complexity of the MDP the agent faces, which scales with the MDP’s discount factor (or, equivalently, the horizon). When the guidance discount γ̃n is lower than the original discount γ (i.e. λn < 1), the reshaped MDP M̃n given by (2) has a shorter horizon and requires fewer samples to solve. However, the reduced complexity comes at the cost of bias, because the agent is now incentivized toward maximizing the performance with respect to the heuristic rather than the original long-term returns ofM. In the extreme case of λn = 0, HuRL would solve a zero-horizon contextual bandit problem with contexts (i.e. states) sampled from dπ ofM.

heading: 3.3 A Toy Example
text: We illustrate this idea in a chain MDP environment in Fig. 1. The optimal policy π∗ for this MDP’s original γ = 0.9 always picks action→, as shown in Fig. 1b-(1), giving the optimal value V ∗ in Fig. 1a-(2). Suppose we used a smaller guidance discount γ̃ = 0.5γ to accelerate learning. This is equivalent to HuRL with a zero heuristic h = 0 and λ = 0.5. Solving this reshaped MDP yields a policy π̃∗ that acts very myopically in the original MDP, as shown in Fig. 1b-(2); the value function of π̃∗ in the original MDP is visualized in Fig. 1a-(4).
Now, suppose we use Fig. 1a-(4) as a heuristic in HuRL instead of h = 0. This is a bad choice of heuristic (Bad h) as it introduces a large bias with respect to V ∗ (cf. Fig. 1a-(2)). On the other hand, we can roll out a random policy in the original MDP and use its value function as the heuristic (Good h), shown in Fig. 1a-(3). Though the random policy has an even lower return at the initial state s = 3, it gives a better heuristic because this heuristic shares the same trend as V ∗ in Fig. 1a-(1). HuRL run with Good h and Bad h yields policies in Fig. 1b-(3,4), and the quality of the resulting solutions in the original MDP, V π̃ ∗
λ (d0), is reported in Fig. 1c for different λ. Observe that HuRL with a good heuristic can achieve V ∗(d0) with a much smaller horizon λ ≤ 0.5. Using a bad h does not lead to π∗ at all when λ = 0.5 (Fig. 1b-(4)) but is guaranteed to do so when λ converges to 1. (Fig. 1b-(5)).

heading: 4 Theoretical Analysis
text: When can HuRL accelerate learning? Similar to typical regularization techniques, the horizon-based regularization of HuRL leads to a bias-variance decomposition that can be optimized for better finite-sample performance compared to directly solving the original MDP. However, a non-trivial trade-off is possible only when the regularization can bias the learning toward a good direction. In HuRL’s case this is determined by the heuristic, which resembles a prior we encode into learning.
In this section we provide HuRL’s theoretical foundation. We first describe the bias-variance trade-off induced by HuRL. Then we show how suboptimality in solving the reshaped MDP translates into performance in the original MDP, and identify the assumptions HuRL needs the base RL algorithm to satisfy. In addition, we explain how HuRL relates to PBRS, and characterize the quality of heuristics and sufficient conditions for constructing good heuristics from batch data using offline RL.
For clarity, we will focus on the reshaped MDP M̃ = (S,A, P, r̃, γ̃) for a fixed λ ∈ [0, 1], where r̃, γ̃ are defined in (1). We can view this MDP as the one in a single iteration of HuRL. For a policy π, we denote its state value function in M̃ as Ṽ π , and the optimal policy and value function of M̃ as π̃∗ and Ṽ ∗, respectively. The missing proofs of the results from this section can be found in Appendix A.

heading: 4.1 Short-Horizon Reduction: Performance Decomposition
text: Our main result is a performance decomposition, which characterizes how a heuristic h and suboptimality in solving the reshaped MDP M̃ relate to performance in the original MDPM. Theorem 4.1. For any policy π, heuristic f : S → R, and mixing coefficient λ ∈ [0, 1],
V ∗(d0)− V π(d0) = Regret(h, λ, π) + Bias(h, λ, π)
where we define Regret(h, λ, π) := λ ( Ṽ ∗(d0)− Ṽ π(d0) ) +
1− λ 1− γ
( Ṽ ∗(dπ)− Ṽ π(dπ) ) (3)
Bias(h, λ, π) := ( V ∗(d0)− Ṽ ∗(d0) ) + γ(1− λ)
1− γ Es,a∼dπEs′|s,a
[ h(s′)− Ṽ ∗(s′) ] (4)
Furthermore, ∀b ∈ R, Bias(h, λ, π) = Bias(h+ b, λ, π) and Regret(h, λ, π) = Regret(h+ b, λ, π).
The theorem shows that suboptimality of a policy π in the original MDPM can be decomposed into 1) a bias term due to solving a reshaped MDP M̃ instead of the original MDPM, and 2) a regret term (i.e. the learning variance) due to π being suboptimal in the reshaped MDP M̃. Moreover, it shows that heuristics are equivalent up to constant offsets. In other words, only the relative ordering between states that a heuristic induces matters in learning, not the absolute values.
Balancing the two terms trades off bias and variance in learning. Using a smaller λ replaces the long-term information with the heuristic and make the horizon of the reshaped MDP M̃ shorter. Therefore, given a finite interaction budget, the regret term in (3) can be more easily minimized, though the bias term in (4) can potentially be large if the heuristic is bad. On the contrary, with λ = 1, the bias is completely removed, as the agent solves the original MDPM directly.

heading: 4.2 Regret, Algorithm Requirement, and Relationship with PBRS
text: The regret term in (3) characterizes the performance gap due to π being suboptimal in the reshaped MDP M̃, because Regret(h, λ, π̃∗) = 0 for any h and λ. For learning, we need the base RL algorithm L to find a policy π such that the regret term in (3) is small. By the definition in (3), the base RL algorithm L is required not only to find a policy π such that Ṽ ∗(s) − Ṽ π(s) is small for states from d0, but also for states π visits when rolling out in the original MDPM. In other words, it is insufficient for the base RL algorithm to only optimize for Ṽ π(d0) (the performance in the reshaped MDP with respect to the initial state distribution; see Section 2.2). For example, suppose λ = 0 and d0 concentrates on a single state s0. Then maximizing Ṽ π(d0) alone would only optimize π(·|s0) and the policy π need not know how to act in other parts of the state space. To use HuRL, we need the base algorithm to learn a policy π that has small action gaps in the reshaped MDP M̃ but along trajectories in the original MDPM, as we show below. This property is satisfied by off-policy RL algorithms such as Q-learning [34]. Proposition 4.1. For any policy π, heuristic f : S → R and mixing coefficient λ ∈ [0, 1],
Regret(h, λ, π) = −Eρπ(d0) [∑∞ t=0 γ tÃ∗(st, at) ] where ρπ(d0) denotes the trajectory distribution of running π from d0, and Ã∗(s, a) = r̃(s, a) + γ̃Es′|s,a[Ṽ ∗(s′)]− Ṽ ∗(s) ≤ 0 is the action gap with respect to the optimal policy π̃∗ of M̃.
Another way to comprehend the regret term is through studying its dependency on λ. When λ = 1, Regret(h, 0, π) = V ∗(d0)−V π(d0), which is identical to the policy regret inM for a fixed initial distribution d0. On the other hand, when λ = 0, Regret(h, 0, π) = maxπ′ 11−γEs∼dπ [r̃(s, π
′)−r̃(s, π)], which is the regret of a non-stationary contextual bandit problem where the context distribution is dπ (the average state distribution of π). In general, for λ ∈ (0, 1), the regret notion mixes a short-horizon non-stationary problem and a long-horizon stationary problem.
One natural question is whether the reshaped MDP M̃ has a more complicated and larger value landscape than the original MDPM, because these characteristics may affect the regret rate of a base algorithm. We show that M̃ preserves the value bounds and linearity of the original MDP. Proposition 4.2. Reshaping the MDP as in (1) preserves the following characteristics: 1) If h(s) ∈ [0, 11−γ ], then Ṽ
π(s) ∈ [0, 11−γ ] for all π and s ∈ S. 2) If M̃ is a linear MDP with feature vector φ(s, a) (i.e. r(s, a) and Es′|s,a[g(s′)] for any g can be linearly parametrized in φ(s, a)), then M̃ is also a linear MDP with feature vector φ(s, a).
On the contrary, the MDPMλ := (S,A, P, r, λγ) in Section 2.2 does not have these properties. We can show thatMλ is equivalent to M̃ up to a PBRS transformation (i.e., r̄(s, a) = r̃(s, a) + γ̃Es′|s,a[h(s′)]−h(s)). Thus, HuRL incorporates guidance discount into PBRS with nicer properties.

heading: 4.3 Bias and Heuristic Quality
text: The bias term in (4) characterizes suboptimality due to using a heuristic h in place of long-term state values inM. What is the best heuristic in this case? From the definition of the bias term in (4), we see that the ideal heuristic is the optimal value V ∗, as Bias(V ∗, λ, π) = 0 for all λ ∈ [0, 1]. By continuity, we can expect that if h deviates from V ∗ a little, then the bias is small.
Corollary 4.1. If infb∈R ‖h+ b− V ∗‖∞ ≤ , then Bias(h, λ, π) ≤ (1−λγ) 2
(1−γ)2 .
To better understand how the heuristic h affects the bias, we derive an upper bound on the bias by replacing the first term in (4) with an upper bound that depends only on π∗.
Proposition 4.3. For g : S → R and η ∈ [0, 1], define C(π, g, η) := Eρπ(d0) [∑∞ t=1 η t−1g(st) ] . Then Bias(h, λ, π) ≤ (1− λ)γ(C(π∗, V ∗ − h, λγ) + C(π, h− Ṽ ∗, γ)).
In Proposition 4.3, the term (1− λ)γC(π∗, V ∗ − h, λγ) is the underestimation error of the heuristic h under the states visited by the optimal policy π∗ in the original MDPM. Therefore, to minimize the first term in the bias, we would want the heuristic h to be large along the paths that π∗ generates.
However, Proposition 4.3 also discourages the heuristic from being arbitrarily large, because the second term in the bias in (4) (or, equivalently, the second term in Proposition 4.3) incentivizes the heuristic to underestimate the optimal value of the reshaped MDP Ṽ ∗. More precisely, the second term requires the heuristic to obey some form of spatial consistency. A quick intuition is the observation that if h(s) = V π ′ (s) for some π′ or h(s) = 0, then h(s) ≤ Ṽ ∗(s) for all s ∈ S. More generally, we show that if the heuristic is improvable with respect to the original MDPM (i.e. the heuristic value is lower than that of the max of Bellman backup), then h(s) ≤ Ṽ ∗(s). By Proposition 4.3, learning with an improvable heuristic in HuRL has a much smaller bias. Definition 4.1. Define the Bellman operator (Bh)(s, a) := r(s, a) + γEs′|s,a[h(s′)]. A heuristic function h : S → R is said to be improvable with respect to an MDPM if maxa(Bh)(s, a) ≥ h(s).
Proposition 4.4. If h is improvable with respect toM, then Ṽ ∗(s) ≥ h(s), for all λ ∈ [0, 1].

heading: 4.4 Pessimistic Heuristics are Good Heuristics
text: While Corollary 4.1 shows that HuRL can handle an imperfect heuristic, this result is not ideal. The corollary depends on the `∞ approximation error, which can be difficult to control in large state spaces. Here we provide a more refined sufficient condition of good heuristics. We show that the concept of pessimism in the face of uncertainty provides a finer mechanism for controlling the approximation error of a heuristic and would allow us to remove the `∞-type error. This result is useful for constructing heuristics from data that does not have sufficient support.
From Proposition 4.3 we see that the source of the `∞ error is the second term in the bias upper bound, as it depends on the states that the agent’s policy visits which can change during learning. To remove this dependency, we can use improvable heuristics (see Proposition 4.4), as they satisfy h(s) ≤ Ṽ ∗(s). Below we show that Bellman-consistent pessimism yields improvable heuristics. Proposition 4.5. Suppose h(s) = Q(s, π′) for some policy π′ and function Q : S × A → R such that Q(s, a) ≤ (Bh)(s, a), ∀s ∈ S, a ∈ A. Then h is improvable and f(s) ≤ V π′(s) for all s ∈ S.
The Bellman-consistent pessimism in Proposition 4.5 essentially says that h is pessimistic with respect to the Bellman backup. This condition has been used as the foundation for designing pessimistic off-policy RL algorithms, such as pessimistic value iteration [30] and algorithms based on pessimistic absorbing MDPs [31]. In other words, these pessimistic algorithms can be used to construct good heuristics with small bias in Proposition 4.3 from offline data. With such a heuristic, the bias upper bound would be simply Bias(h, λ, π) ≤ (1− λ)γC(π∗, V ∗ − h, λγ). Therefore, as long as enough batch data are sampled from a distribution that covers states that π∗ visits, these pessimistic algorithms can construct good heuristics with nearly zero bias for HuRL with high probability.

heading: 5 Experiments
text: We validate our framework HuRL experimentally in MuJoCo (commercial license) [32] robotics control problems and Procgen games (MIT License) [33], where soft actor critic (SAC) [35] and proximal policy optimization (PPO) [36] were used as the base RL algorithms, respectively5. The goal is to study whether HuRL can accelerate learning by shortening the horizon with heuristics. In particular, we conduct studies to investigate the effects of different heuristics and mixing coefficients. Since the main focus here is on the possibility of leveraging a given heuristic to accelerate RL algorithms, in these experiments we used vanilla techniques to construct heuristics for HuRL. Experimentally studying the design of heuristics for a domain or a batch of data is beyond the scope of the current paper but are important future research directions. For space limitation, here we report only the results of the MuJoCo experiments. The results on Procgen games along with other experimental details can also be found in Appendix C.
5Code to replicate all experiments is available at https://github.com/microsoft/HuRL.

heading: 5.1 Setup
text: We consider four MuJoCo environments with dense rewards (Hopper-v2, HalfCheetah-v2, Humanoidv2, and Swimmer-v2) and a sparse reward version of Reacher-v2 (denoted as Sparse-Reacher-v2)6. We design the experiments to simulate two learning scenarios. First, we use Sparse-Reacher-v2 to simulate the setting where an engineered heuristic based on domain knowledge is available; since this is a goal reaching task, we designed a heuristic h(s) = r(s, a)− 100‖e(s)− g(s)‖, where e(s) and g(s) denote the robot’s end-effector position and the goal position, respectively. Second, we use the dense reward environments to model scenarios where a batch of data collected by multiple behavioral policies is available before learning, and a heuristic is constructed by an offline policy evaluation algorithm from the batch data (see Appendix C.1 for details). In brief, we generated these behavioral policies by running SAC from scratch and saved the intermediate policies generated in training. We then use least-squares regression to fit a neural network to predict empirical Monte-Carlo returns of the trajectories in the sampled batch of data. We also use behavior cloning (BC) to warm-start all RL agents based on the same batch dataset in the dense reward experiments.
The base RL algorithm here, SAC, is based on the standard implementation in Garage (MIT License) [37]. The policy and value networks are fully connected independent neural networks. The policy is Tanh-Gaussian and the value network has a linear head.
Algorithms. We compare the performance of different algorithms below. 1) BC 2) SAC 3) SAC with BC warm start (SAC w/ BC) 4) HuRL with the engineered heuristic (HuRL) 5) HuRL with a zero heuristic and BC warm start (HuRL-zero) 6) HuRL with the Monte-Carlo heuristic and BC warm start (HuRL-MC) 7) SAC with PBRS reward (and BC warm start, if applicable) (PBRS). For the HuRL algorithms, the mixing coefficient was scheduled as λn = λ0 + (1− λ0)cω tanh(ω(n− 1)), for n = 1, . . . , N , where λ0 ∈ [0, 1], ω > 0 controls the increasing rate, and cω is a normalization constant such that λ∞ = 1 and λn ∈ [0, 1]. We chose these algorithms to study the effect of each additional warm-start component (BC and heuristics) added on top of vanilla SAC. HuRL-zero is SAC w/ BC but with an extra λ schedule above that further lowers the discount, whereas SAC and SAC w/ BC keep a constant discount factor.
Evaluation and Hyperparameters. In each iteration, the RL agent has a fixed sample budget for environment interactions, and its performance is measured in terms of undiscounted cumulative returns of the deterministic mean policy extracted from SAC. The hyperparameters used in the algorithms above were selected as follows. First, the learning rates and the discount factor of the base RL algorithm, SAC, were tuned for each environment. The tuned discount factor was used as the discount factor γ of the original MDPM. Fixing the hyperparameters above, we additionally tune λ0 and ω for the λ schedule of HuRL for each environment and each heuristic. Finally, after all these hyperparameters were fixed, we conducted additional testing runs with 30 different random seeds and report their statistics here. Sources of randomness included the data collection process of the behavioral policies, training the heuristics from batch data, BC, and online RL. However, the behavioral policies were fixed across all testing runs. We chose this hyperparameter tuning procedure to make sure that the baselines (i.e. SAC) compared in these experiments are their best versions.

heading: 5.2 Results Summary
text: Fig. 2 shows the results on the MuJoCo environments. Overall, we see that HuRL is able to leverage engineered and learned heuristics to significantly improve the learning efficiency. This trend is consistent across all environments that we tested on.
For the sparse-reward experiments, we see that SAC and PBRS struggle to learn, while HuRL is able to converge to the optimal performance much faster. For the dense reward experiments, similarly HuRL-MC converges much faster, though the gain in HalfCheetah-v2 is minor and it might have converged to a worse local maximum in Swimmer-v2. In addition, we see that warm-starting SAC using BC (i.e. SAC w/ BC) can improve the learning efficiency compared with the vanilla SAC, but using BC alone does not result in a good policy. Lastly, we see that using the zero heuristic (HuRL-zero) with extra λ-scheduling does not further improve the performance of SAC w/ BC. This comparison verifies that the learned Monte-Carlo heuristic provides non-trivial information.
Interestingly, we see that applying PBRS to SAC leads to even worse performance than running SAC with the original reward. There are two reasons why SAC+PBRS is less desirable than SAC+HuRL
6The reward is zero at the goal and −1 otherwise.
as we discussed before: 1) PBRS changes the reward/value scales in the induced MDP, and popular RL algorithms like SAC are very sensitive to such changes. In contrast, HuRL induces values on the same scale as we show in Proposition 4.2. 2) In HuRL, we are effectively providing the algorithm some more side-information to let SAC shorten the horizon when the heuristic is good.
The results in Fig. 2 also have another notable aspect. Because the datasets used in the dense reward experiments contain trajectories collected by a range of policies, it is likely that BC suffers from disagreement in action selection among different policies. Nonetheless, training a heuristic using a basic Monte-Carlo regression seems to be less sensitive to these conflicts and still results in a helpful heuristic for HuRL. One explanation can be that heuristics are only functions of states, not of states and actions, and therefore the conflicts are minor. Another plausible explanation is that HuRL only uses the heuristic to guide learning, and does not completely rely on it to make decisions Thus, HuRL can be more robust to the heuristic quality, or, equivalently, to the quality of prior knowledge.

heading: 5.3 Ablation: Effects of Horizon Shortening
text: To further verify that the acceleration in Fig. 2 is indeed due to horizon shortening, we conducted an ablation study for HuRL-MC on Hopper-v2, whose results are presented in Fig. 2f. HuRLMC’s best λ-schedule hyperparameters on Hopper-v2, which are reflected in its performance in the aforementioned Fig. 2c, induced a near-constant schedule at λ = 0.95; to obtain the curves in Fig. 2f, we ran HuRL-MC with constant-λ schedules for several more λ values. Fig. 2f shows that increasing λ above 0.98 leads to a performance drop. Since using a large λ decreases bias and makes the reshaped MDP more similar to the original MDP, we conclude that the increased learning speed on Hopper-v2 is due to HuRL’s horizon shortening (coupled with the guidance provided by its heuristic).

heading: 6 Related Work
text: Discount regularization. The horizon-truncation idea can be traced back to Blackwell optimality in the known MDP setting [18]. Reducing the discount factor amounts to running HuRL with a zero heuristic. Petrik and Scherrer [19], Jiang et al. [20, 21] study the MDP setting; Chen et al. [22] study POMDPs. Amit et al. [23] focus on discount regularization for Temporal Difference (TD) methods, while Van Seijen et al. [6] use a logarithmic mapping to lower the discount for online RL.
Reward shaping. Reward shaping has a long history in RL, from the seminal PBRS work [29] to recent bilevel-optimization approaches [38]. Tessler and Mannor [5] consider a complementary problem to HuRL: given a discount γ′, they find a reward r′ that preserves trajectory ordering in the original MDP. Meanwhile there is a vast literature on bias-variance trade-off for online RL with
horizon truncation. TD(λ) [39, 40] and Generalized Advantage Estimates [41] blend value estimates across discount factors, while Sherstan et al. [42] use the discount factor as an input to the value function estimator. TD(∆) [43] computes differences between value functions across discount factors.
Heuristics in model-based methods. Classic uses of heuristics include A* [24], Monte-Carlo Tree Search (MCTS) [25], and Model Predictive Control (MPC) [44]. Zhong et al. [26] shorten the horizon in MPC using a value function approximator. Hoeller et al. [27] additionally use an estimate for the running cost to trade off solution quality and amount of computation. Bejjani et al. [28] show heuristic-accelerated truncated-horizon MPC on actual robots and tune the value function throughout learning. Bhardwaj et al. [7] augment MPC with a terminal value heuristic, which can be viewed as an instance of HuRL where the base algorithm is MPC. Asai and Muise [45] learn an MDP expressible in the STRIPS formalism that can benefit from relaxation-based planning heuristics. But HuRL is more general, as it does not assume model knowledge and can work in unknown environments.
Pessimistic extrapolation. Offline RL techniques employ pessimistic extrapolation for robustness [30], and their learned value functions can be used as heuristics in HuRL. Kumar et al. [46] penalize out-of-distribution actions in off-policy optimization while Liu et al. [31] additionally use a variational auto-encoder (VAE) to detect out-of-distribution states. We experimented with VAEfiltered pessimistic heuristics in Appendix C. Even pessimistic offline evaluation techniques [16] can be useful in HuRL, since function approximation often induces extrapolation errors [47].
Heuristic pessimism vs. admissibility. Our concept of heuristic pessimism can be easily confused for the well-established notion of admissibility [48], but in fact they are opposites. Namely, an admissible heuristic never underestimates V ∗ (in the return-maximization setting), while a pessimistic one never overestimates V ∗. Similarly, our notion of improvability is distinct from consistency: they express related ideas, but with regards to pessimistic and admissible value functions, respectively. Thus, counter-intuitively from the planning perspective, our work shows that for policy learning, inadmissible heuristics are desirable. Pearl [49] is one of the few works that has analyzed desirable implications of heuristic inadmissibility in planning.
Other warm-starting techniques. HuRL is a new way to warm-start online RL methods. Bianchi et al. [50] use a heuristic policy to initialize agents’ policies. Vinyals et al. [2], Hester et al. [10] train a value function and policy using batch IL and then used them as regularization in online RL. Nair et al. [9] use off-policy RL on batch data and fine-tune the learned policy. Recent approaches of hybrid IL-RL have strong connections to HuRL [17, 51, 52]. In particular, Cheng et al. [17] is a special case of HuRL with a max-aggregation heuristic. Farahmand et al. [8] use several related tasks to learn a task-dependent heuristic and perform shorter-horizon planning or RL. Knowledge distillation approaches [53] can also be used to warm-start learning, but in contrast to them, HuRL expects prior knowledge in the form of state value estimates, not features, and doesn’t attempt to make the agent internalize this knowledge. A HuRL agent learns from its own environment interactions, using prior knowledge only as guidance. Reverse Curriculum approaches [54] create short horizon RL problems by initializing the agent close to the goal, and moving it further away as the agent improves. This gradual increase in the horizon inspires the HuRL approach. However, HuRL does not require the agent to be initialized on expert states and can work with many different base RL algorithms.

heading: 7 Discussion and Limitations
text: This work is an early step towards theoretically understanding the role and potential of heuristics in guiding RL algorithms. We propose a framework, HuRL, that can accelerate RL when an informative heuristic is provided. HuRL induces a horizon-based regularization of RL, complementary to existing warm-starting schemes, and we provide theoretical and empirical analyses to support its effectiveness. While this is a conceptual work without foreseeable societal impacts yet, we hope that it will help counter some of AI’s risks by making RL more predictable via incorporating prior into learning.
We remark nonetheless that the effectiveness of HuRL depends on the available heuristic. While HuRL can eventually solve the original RL problem even with a non-ideal heuristic, using a bad heuristic can slow down learning. Therefore, an important future research direction is to adaptively tune the mixing coefficient based on the heuristic quality with curriculum or meta-learning techniques. In addition, while our theoretical analysis points out a strong connection between good heuristics for HuRL and pessimistic offline RL, techniques for the latter are not yet scalable and robust enough for high-dimensional problems. Further research on offline RL can unlock the full potential of HuRL.

Review summaries:
This work proposes a framework for incorporating heuristics into reinforcement learning. The main idea is to construct a new MDP where the new reward function is offset by a scaled heuristic and the new temporal discount factor is scaled down. The scaling of the heuristic and temporal discount factor are controlled by a mixing coefficient $\lambda \in [0, 1]$. The proposal is to run an RL algorithm in this new MDP with the mixing coefficient adjusted over time (HuRL). The main theoretical result relates performance in the new MDP to performance in the original MDP (Theorem 4.1). Empirical results in MuJoCo and Procgen with PPO and SAC show that HuRL improves on several baselines.

  This paper proposed an alternative framework for reward shaping in RL   that uses a heuristic function.    Unlike potential-based reward shaping, the algorithm does not subtract   the heursitic value of the current state from the reward.  There is a   coefficient for the heursitic value to be added to the reward.   After each episode, it incrementally increases the discounting factor   (converges to 1) and decreases the coefficient for the heuristic value   (converges to 0).    In section 4, the authors theoretically analysed their framework.   During the analysis, the authors rediscovered *admissibility* &   *consistency*, concepts that are already well-known in shortest path   finding literature from the earliest history of AI (can be traced back   to 1968).  Obviously, being such a fundamental, well-known concepts,   you are not allowed to rename and replace them, so it is necessary to   fix these definitions to match the existing literature.  However,   although these definitions and proofs are not new, I believe *the   finding that admissibility & consistency will help RL is quite new*,   and has never been theoretically analyzed before.  This will attract   the attention of not just the RL community but also of the symbolic   AI community. 

The paper aims to solve/mitigate the long term credit assignment problem in reinforcement learning. It does so by pre-training heuristic value functions and using them to shorten the horizon. The claim is that the proposed approach could potentially improve sample complexity, like other warm-start or regularization methods in RL.