Heuristic-Guided Reinforcement Learning
Authors: Ching-An Cheng
Andrey Kolobov
Adith Swaminathan
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
heuristic
warm-start
truncated horizon

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.

Heuristic-Guided Reinforcement Learning
Ching-An Cheng Microsoft Research
Andrey Kolobov Microsoft Research Redmond, WA
Adith Swaminathan Microsoft Research Redmond, WA
Redmond, WA
chingancemiicooofft.
akolobov@miccrooft..o com
adswaminnmicrosoofff. com
Abstract
We provide a framework for accelerating reinforcement learning (RL) algorithms by heuristics constructed from domain knowledge 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- guiidd RL induces a much shorter-horizon subproblem that provably solves the original task. Our framework can be viewed regularization for controlling bias and variance in RL under finite interaction budget.
horizon-bart based
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, heuristic that allows an RI. agent to extrapolate beyond its prior knowledge. On the empirical side, we instantiate our framework to accelerate several state-of-the-ar 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
Many recent empirical successes of reinforcement learning (RL) require solving problems with very long decision-making horizons. OpenAl Five [1] used episodes that were 20000 timesteps on average, while AlphaStar (2 used roughly 5000 timesteps. Long-term credit assignment is very challenging statistical problem, with the sample complexity growing quadratically (or worse) with the horizon K 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 interactions and compute: even with tuned hyperparameters, AlphaStar needed over 10 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-stan or regularize learning with prior knowledge [ [O] For instance, AlphaStar learned policy and value function from human demonstrations and regularized the RI. agent using imitation learning (IL.. AWAC [ 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, propose complementary regularization technique that relies heuristic value functions, or heuristics for short, to effectively shorten the problem horizon faced by an online RL agent for fast learning. We call this approach Heuristic-Guiie The core idea is simple: given a Markov decision process (MDP) M = AS, P.r.y) and heuristic h. S F, we select mixing coefficient X [0, 1) and have the agent solve new MDP M (S, A, 7, ?) with a reshaped reward and a smaller discount (i.e. a shorter horizon):
Reinforcement Learning (HuRL).
a(s,a) == r(s, a) (1 A) [(s')] and 7 : Xy.
(1)
We borrow this terminology from the planning literature to refer to guesses of V in MDP [I]
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

HuRL effectively introduces parizon-basedd regularization that determines whether long-ten term value information should come from collected experiences or the heuristic. By modulating the effective horizon via X, we trade off the bias and the complexity of solving the reshaped MDP. HuRI. with recovers the original problem and with x = 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 MDP M.. 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 good heuristic? In the planning literature, this is typically achieved by solving a relaxation of the original problem [13 [5]. 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
[ For some dense reward problems,
zero heuristic can be effective in reducing RL. complexity, as exploited by the guidance discount framework [3.. In this paper, we view heuristics as 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 251, and MPC 77 26-228 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 F(s, a) r(s, a) + 1 (h(()ss'))) - 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 faster learning. because the base RI. 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 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 's horizon-basee regularization in order characterize the solution quality as a function of X 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 MX. 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 sequence of mixing coefficients (i.e. As) 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. HuRI. starts off by guiding the agent's search direction with heuristic. As the agent becomes more experienced. gradually removes the guidance and lets the agent directly optimize the true long-tern 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.
2 Preliminaries
2.1
Notation
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 5 A discounted infinite-horizon MDP is denoted as 5-tuple M = (S, A, P. P.r. 7) where S is the state space, .A is the action space, P(s')s, ss a) is the transition dynamics, r(s, a) the reward function, and 7 [o, 1) is the discount factor. Without loss of generality, we assume S x A > [0. 1]. We allow the state and action spaces and A to be either discrete or continuous. Let A(-) denote the space of probability distributions. A decision-making policy π is conditional distribution : S - A(A), which can be deterministic. We define some shorthand for writing expectations: For a state distribution d E A(S) and a function }) similarly, for a policy л and function Q : S x A R,
V: S + R, we define V(d)= = [V~a(V [+()]:
we define ((s, 7) == Ba- (s) ( a)). Lastly, we define Eg/ := E, Ee-
2 We consider the RL setting for imitation where we suppose the rewards of expert trajectories are available. MDPs, we need
3 'The results here can be readily applied to knite-horizel MDPs; for other further, e.g., mixing assumptions for limits to exist.
2

---

Central to solving MDPs are the concepts of value functions and average distributions. For a policy T, we define its state value function V as VT := =Ep 1oi= /'1(s, at)] where p denotes the trajectory distribution of 8o, do $1,... induced by running πT starting from so 8. We define the state-action value function (or the Q-function) as @2"(s, a) = r(s, a) + [
We
denote the optimal policy as nt and its state value function as V* = V" Under the assumption that rewards are in [0. 1], we have V (s). Q* a) E [0, [ for all 9, S, and E A. We denote the initial state distribution of interest as do E (S)) and the state distribution of policy v at time t as d7,, with d = dg- Given do, we define the average state distribution of a policy as d= == 7) E d'd With a slight abuse of notation, we also write d' (s.a) = d= (a)sss
2.2 Setup: Reinforcement Learning with Heuristics
We consider RL with prior knowledge expressed in the form of heuristic value function. The goal is to find a policy и that has high return through interactions with an unknown MDP M, i.e., max, V (do). While the agent here does not fully know M, we suppose that, before interactions start the agent is provided with a heuristic h : S - I which the agent can query throughout learning.
The heuristic h represents a prior guess of the optimal value function V of M.. Common sources of heuristics are domain knowledge as typically employed planning, and logged data collected by exploratory by expert behavioral policies. In the latter, 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 F(s, a) == r(s, a) + ".. - h(s). It can be shown that this transformation does not introduce bias into the policy ordering, and therefore solving the new MDP M = would yield the same optimal policy म of M..
Conceptually when the heuristic is the optimal value function / V*, the agent should be able to find the optimal policy n² of M 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. solving M := (S, P. F, 7)) 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 smaller discount) with the shaped reward can yield good policies. An intuitive idea is to run the RL algorithm to maximize VX (do). where VX denotes the value function of π in an MDP MA = (S, A, P,T, Ar) for some À E [0, 1]. However this does not always work. For example, when À = O, max, V (do) only optimizes for the initial states do, but obviously the agent is going encounter other states in M. We next propose a provably correct version, HuRL, to leverage this short-horizon insight.
3 Heuristic-Guidee Reinforcement Learning
We propose a general framework, HuRL, for leveraging heuristics to accelerate RL, contrast to tabula rasa RI. algorithms that attempt to directly solve the long-horizon MDP M. HuRL. uses a hcuristic 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 heuristic-based based learning curriculum to help the agent learn faster.
3.1 Algorithm
HuRL takes reduction-based approach to realize the idea of heuristic guidance. As summarized in Algorithm| [T] HuRL takes a heuristic h S + RR and a base RL algorithm L as input, and outputs an approximately optimal policy for the original MDP M. During training, HuRL iteratively runs the base algorithm L to collect data from the MDP M and then uses the heuristic h to modify the agent's is collected experiences. Namely, in iteration n, the agent interacts with the original MDP M and saves the raw transition tuple Fl D, = {(s, a, s')} (line 2). HuRL then defines a reshaped MDP
Mn == A, 7n) (line 3 by changing the rewards and lowering the discount factor:
(s a) == r(s, a) + (1 An) 1s.
and
5m == An
(2)
'If' L learns only with trajectories, we transform each tuple and assemble them to get the modified trajectory.
3

---

Algorithm 1 Heuristic-Guided Reinforcement Learning (HuRL)
Require: MDP M = AS, P,r, 7), RL algorithm L, heuristic h. mixing coefficients (An}.
1: for n = I,...., do
2: Dn + L.CollecDData()MM
3: Get An from } } and construct M, P, 7n) according to (2) using h and An
4: Tn < C.Trainn Mn)
5: end for
6: return TN
is the mixing coefficient. The new discount 5n. effectively gives Mn. shorter horizon than M's, while the heuristic is blended into the new reward in (2) to account for the missing long-term information. We call 7n >, 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 D. HuRL calls the base algorithm L to perform updates with respect to the
where A, E [0,
reshaped MDP Mn. This is realized by 1) setting the discount factor used in L to Tn and 2) setting the sampled reward to + (7 %, (h(s)) for every transition tuple (s, r. s') collected from M.. We remark that the base algorithm C in line always collects trajectories of lengths proportional to the original discount y, while internally the optimization is done with lower discount 7n in line 4
Over the course of training. HuRL repeats the above steps with a sequence of increasing mixing coefficients {Aa). From (2) we see that as the agent interacts with the environment, the effects of the heuristic MDP reshaping decrease and the effective horizon of the reshaped MDP increases.
3.2 HuRL as Horizon-based Regularization
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 the role of regularization in supervised learning. Unlike the typical weight decay imposed on function approximators (such as the agent's '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 7n is lower than the original discount ? (i.e. An < 1), the reshaped MDP Mn 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 term returns of M. In the extreme case of An, O, HuRL would solve a zero-horizon contextual bandit problem with contexts (i.e. states) sampled from dl of M.
3.3 A Toy Example
We illustrate this idea in a chain MDP environment in Fig. I The optimal policy n² for this MDP's
original 7 = 0.9 always picks action -,, as shown in Fig. lb (1), giving the optimal value V in Fig. (2) Suppose we used a smaller guidance discount
0.5r to accelerate learning. This is
equivalent to HuRL with zero heuristic h = 0 and X = 0.5. Solving this reshaped MDP yields a policy H' that acts very myopically in the original MDP, as shown in Fig, (2); the value function of # in the original MDP is visualized in Fig. (4).
Now, suppose we use Fig. (4) as a heuristic in HuRL. instead of h = 0. This is a bad choice of heuristic (Bad h) it introduces a large bias with respect to V (cf. Fig. Ta- On the other hand, we can roll out a random policy in the original MDP and use its value function as the heuristic (Good f)). shown in Fig. (3).3). Though the random policy has an even lower return the initial state it gives a better heuristic because this heuristic shares the same trend as V* in Fig. (1). HuRL run with Good h and Bad lt yields policies in Fig. (b,44, and the quality of the resulting solutions in the original MDP, V (dn). is reported in Fig. Tc for different X. Observe that HuRL with good heuristic can achieve V (do) with a much smaller horizon À < 0.5. Using a bad h does not lead to r" at all when À= 0.5 (Fig. Tb (4)) but is guaranteed do so when À converges 1. (Fig. Tb (b.

---

11 Abr
Abx
(2) 87
(3) 0.000.300 030, 8700.700 0..00
Good
Bad
89
3C 00000600000 1.50 11 (0.2)
SC. 000 OUDII WWw.OOO
(6)
60 0:48 BY 0AR
(a) Heatmap of different values.
(b) Different policy behaviors.
(c) HuRL with different h and X.
Figure Example of HuRL in a chain MDP. Each cell in row each diagram represents a state from S == fl,.... 10}. The agent starts at state 3 (so), and states 1 and 10 are absorbing (Abs in subfigure a-(1)). Actions A -+ move the agent left or right in the chain unless the agent is in absorbing state. Subfig, a-(1) shows the reward function: r22 4-) - 0.1,
0.2,, r55, + 0.1, and all state-action pairs not shown a-(1) yield r = O. Subfig. a-(2) shows V for y = 0.9. Subfig. a-(3) shows good heuristic
V (random x). Subfig. a-(4) shows a bad heuristic
V (myopic r). Subfig. b-(1): x² for V from a-(2).
Subfig. b-(2): H" from HuRL with / = 0, À = 0.5. Subfig, b-(3): x from HuRL with the good h from (a).() and 0.5. Subfig, b-(4): #* from the bad h from a-(4), À 0.5. Subfig. b-(5): 7' from the bad and 1. Subfig. (c) illustrates the takeaway message: using HuRI. with a good h can find from so even with a small X (see the z-axis), while HuRI. with a bad requires a much higher X to discover nt
4 Theoretical Analysis
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 good direction. In HuRL's case this is determined by the heuristic, which resembles a prior 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, P.T.T) for a fixed À E [0, 1], where fy are defined in ① We can view this MDP as the one in single iteration of HuRL. For a policy denote its state value function in M V'h and the optimal policy and value function of M as 7 and V respectively. The missing proofs of the results from this section can be found in Appendix A
4.1 Short-Horizon Reduction: Performance Decomposition
Our main result is performance decomposition, which characterizes how a heuristic h and subopti- mality in solving the reshaped MDP M relate to performance in the original MDP M. Theorem 4.1. For any policy n, heuristic f R. and mixing coefficient À e [0, 1]. V*(do) (do) Regret A, + Bias(h, AT)
where we define
Regret(h, h, X, A, = (V-(d)) - (d(o))
+ (d- -v=("))(((())))
1 1-
(3)
1 1-7
Bias(h, A, = (do))) v'(do) + 7(1 11-1) 2)
1- Ex Esls la [ ((6))-v((s)) (*()))
(4)
Furthermore, Vb E IR, Bias(h, X, = Bias(h (1 + b, A, π) and Regret X, = Regret (h / b, X, TT)
The theorem shows that suboptimality of a policy æ in the original MDP M can decomposed into /) bias term due to solving a reshaped MDP M instead of the original MDP M, 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 heuristic induces matters in learning, not the absolute values.
5

---

Balancing the two terms trades off bias and variance in learning. Using 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 ( 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 MDP M directly.
4.2 Regret, Algorithm Requirement, and Relationship with PBRS
The regret term in ( characterizes the performance gap due to π being suboptimal in the reshaped MDP M, because Regret(h, X, )²
for any and X. For learning, we need the base RL algorithm C to find a policy such that the regret term in ( is small. By the definition in (3), the base RL algorithm L is required not only to find a policy such that (*) (T()) is small for states from dg, but also for states π visits when rolling out in the original MDP M. In other words, it is insufficient for the base RL algorithm to only optimize for ("(do) (the performance in the reshaped MDP with respect to the initial state distribution; see Section 2.2). For example, suppose and do concentrates on single state so. Then maximizing V (do) alone would only optimize π (-1sa) and the policy и need not know how to act in other parts of the state space.
To use HuRL, need the base algorithm to learn policy that has small action gaps in the reshaped MDP M but along trajectories in the original MDP M, as we show below. This property is satisfied by off-policy RL. algorithms such as Q-learning [34].
Proposition 4.1. For any policy n, heuristic J S - and mixing coefficient X E [0,
Regret (h, X, x) = (d)) (A)
where p² (do) denotes the trajectory distribution of running क from dg. and (s, = =(ss
" (V (s') (s) < 0 is the action gap with respect to the optimal policy मt of M.
Another way to comprehend the regret term is through studying its dependency on A. When À Regret(A, /, 0, T) = V (ddd)--V'' which is identical to the policy regret in .M for a afxxed initial dis- tribution dg. On the other hand, when A = O, Regret (h, 0, x) maxx' -- [Tss, x -'s- m)), which is the regret of a non-stationary contextual bandit problem where the context distribution is d' (the average state distribution of rT. In general, for > E (0. 1), the regret notion mixes a short-horizon non-stationary problem and long-horizon stationary problem.
One natural question is whether the reshaped MDP M has a more complicated and larger value landscape than the original MDP M, 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) E 10. r-g then (*(s) E [0. for all a and s E S. 2) If M is linear MDP with feature vector a(s, a) (iee. r(s,a) and (.()),l((())) for any g can be linearly parametrized in ((s,a)) then M is also a linear MDP with feature vector ((s.a).
Xy) in Section 2.2 does not have these properties. We can show that MM is equivalentt to M up to PBRS transformation (i.c., F(s, a) r(s, a) a [h(s')] - h(s)). Thus, HuRL incorporates guidance discount into PBRS with nicer properties.
On the contrary, the MDP M ==
4.3 Bias and Heuristic Quality
The bias term in 4 characterizes suboptimality due to using a heuristic in place of long-term state values in M. What is the best heuristic in this case? From the definition of the bias term in ( we see that the ideal heuristic is the optimal value V*, as Bias(V", A, π) = 0 for all X E [0. By continuity, we can expect that if la deviates from V* a little, then the bias is small.
Corollary 4.1. ffn ||h + b - V* S e, then Bias(h, X, T) < (1-20)2-
(1-7)=6.
To better understand how the heuristic affects the bias, we derive an upper bound on the bias by replacing the first term in 4 with upper bound that depends only on x".

---

Proposition 4.3, For S + R and 17 E [0, 1], define C(T.g.n) n) == E (db) (do)
g(s:)].
Then Bias(h, A, T) S (1- (17 V - - X7) + C(T, V*, ;)))
In Proposition 4.3 the term (1 - A)=C(=*, V h, Ar)) is the underestimation error of the heuristic h under the states visited by the optimal policy x in the original MDP M. Therefore, to minimize the first term in the bias, we would want the heuristic / to be large along the paths that n generates.
However, Proposition 4.3 also discourages the heuristic from being arbitrarily large, because the second term in the bias in (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 obey some form of spatial consistency. A quick intuition is
the observation that lss)) V= (s) for some n' or i((s) = O, then (s)) v (s) for & E S. More generally, we show that if the heuristic is improvable with respect to the original MDP M
(i.e. the heuristic value is lower than that of the max of Bellman backup), then hss) S V*()). By
Proposition 4.3, learning with an improvable heuristic in HuRL has a much smaller bias.
[h(s')] A heuristic Definition 4.1. Define the Bellman operator (Bh) a) = r(s, a) +y
function h: : S + R is said to be improvable with respect to an MDP M if max, (Bh) (s, a) 2 h(s)..
Proposition 4.4. If is improvable with respect to M, then (s) Z h(s). all X E [0. 1].
4.4 Pessimistic Heuristics are Good Heuristies
While Corollary 4.1 shows that HuRL can handle an imperfect heuristic, this result is not ideal. The corollary depends on the for approximation error, which be difficult 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 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 heuristies from data that does not have sufficient support.
From Proposition 4.3 we see that the source of the loo error is the second term in the bias upper bound, as it depends on the states that the agent's '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-consister pessimism yields improvable heuristics. Proposition 4.5. Suppose h(s) Q(s for some policy n' and function Q : 8 A R such that Q(s, a) < (Bh)(s, a). Vs E S. E A. Then h is improvable and f(s) S V (s) for all s E S.
The -el.man--ooniiiiee 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 (3 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, X, R) S (I X)DC(T', V h, Ay). Therefore, as long as enough batch data are sampled from a distribution that covers states that x² visits, these pessimistic algorithms can construct good heuristics with nearly zero bias for HuRL with high probability.
5 Experiments
32 robotics We validate our framework HuRL experimentally in MuJoCo (commercial license)
control problems and Procgen games (MIT License) 33 where soft actor critic (SAC) proximal policy optimization (PPO) B6 were used as the base RL algorithms, respectively" The goal is to study whether HuRL can accelerate learning by shortening the horizon with heuristies. 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 domain or batch of data is beyond the scope of the current paper but important future research directions. For space limitation, here report only the results of the MuJoCo experiments. The results on Procgen games along with other experimental details can also be found in Appendix
35 and
CCode replicate all experiments is available https//gittbbbcommmmicccos//tttt
7

---

5.1 Setup
We consider four MuloCo environments with dense rewards (Hopper-v2, HalfCheetah-v2, Humanoid-
v2, and Swimmer-v2) and sparse reward version of Reacher-v2 (denoted as Sparse-Reacher-ve. _
We design the experiments to simulate two learning scenarios. First, we use
to simulate the setting where engineered heuristic based on domain knowledge is available; since this a goal reaching task, we designed a heuristic (1()) = r(s, a) - 100]le(s) - g())]l 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 heuristic is constructed by an offline policy evaluation algorithm from the batch data (see Appendix [ 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-Carde 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 Li- cense) [37] The policy and value networks are fully connected independent neural networks. The and the value network has linear head.
policy is
Algorithms. We compare the performance of different algorithms below. /) BC 2) SAC 3) SAC with BC warm start (SAC w/ BC) 4) HuRL with the engineered heuristic (HuRL. 5) HuRL with zero heuristic and BC warm start (HuRL-zeroo) 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 An. Ao + (1 Ao) tanh(w(r for n 1,.., .N, where A E [0, 1J. w > controls the increasing rate, and c, is normalization constant such that X = and An E [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.
1)),
Evaluation and Hyperparameters. In each iteration, the RL agent has 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 y of the original MDP M. Fixing the hyperparameters above, we additionally tune Åo and w 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.
5.2 Results Summary
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 worse local maximum in Swimmer-v2. 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, (HuRL-zero) with extra X-scheduling does not further improve the performance of SAC w/ BC. This comparison verifies that the learned Monte-Carlo heuristic provides non-trivial information.
that using the zero heuristic
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
'The reward zero at the goal and -1 otherwise.
8

---

100
SAC
PBRS
2000
Rehur
200
HaKI
Reurs
3000
Reure
1,500
300
2000
1000
400
1000
500
-500
50
1100 Inenation
150
1000
200
300
400
50
100 Eteration
1.50
lteration
(a) Sparse-Reare Reacher-v2
(b) Humanoid-v2
(c) Hopper-v2 v2
300
2000
4000
PERS
1500
Retum
Retum
Retu
100
2000
SAC
HuRLL-aero
1000
2 11.9
HuRL MC
0g
_,
2 11.01
160 Bocniion
150
50
150
100
150
Iterationn
Tteration
(d) Swimmer-y2
(c) HalfCheetah-v2
(f) Ao ablation.
Figure 2: Experimental results. (a) uses an engineered heuristic for a sparse reward problem: (b)-(e) use heuristics learned from offfine data and share the same legend; (c) shows ablation results of different initial Au in Hopper-v2. The plots show the 25th, 50th, 75th percentiles of algorithm performance over 30 random seeds.
as we discussed before: /) PBRS changes the reward/value scales in the induced MDP, and popular RL algorithms like SAC are very sensitive 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. also have another notable aspect. Because the datasets used in the dense reward experiments contain trajectories collected by 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 be less sensitive to these conflicts and still results in helpful heuristic for HuRL. One explanation can be that heuristics are only functions of states, not of states and actions, and therefore the conflicts 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, the quality of prior knowledge.
5.3 Ablation: Effects of Horizon Shortening
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. 2i HuRL- MC's best X-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, 2 we ran HuRL-MC with constant-A schedules for several more values. Fig. 2i shows that increasing above 0.98 leads to performance drop. Since using 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 HuRL's horizon shortening (coupled with the guidance provided by its heuristic).
6 Related Work
Discount regularization. The Morizon-truncatto idea can be traced back 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 al. 22 study POMDPs. Amit et al.
(3 focus on discount regularization for Temporal Difference (TD) methods, logarithmic mapping to lower the discount for online RI.
while Van Seijen et al. 6
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 complementary problem to HuRL: given a discount 7/, they find a reward r' that preserves trajectory ordering in the original MDP. Mcanwhile there is vast literature on bias-variance trade-off for online RL with

---

blend value estimates across discount factors, while Sherstan et al. 142 use the discount factor as an input to the value function estimator. TD(A) 4 computes differences between value functions across discount factors.
horizon truncation. TD(X) [3 40 and Generalized Advantage Estimates 41
Heuristies in model-based methods. Classic uses of heuristics include A* Monte-Carle 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. (7 additionally use an estimate for the running cost to trade off solution quality and amount of computation. Bejjani et al. [28] show heuristic-accelerated
mancated-horizon MPC on actual robots and tune the value function throughout learning. Bhardwaj et al. [7] augment MPC with 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 HuRI. 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 robust- ness [30]. and their learned value functions can be used as heuristics in HuRL. Kumar et al. [46] penalize out-of-distributie actions in
optimization while Liu et al. [3]] additionally use
a variational auto-encoder (VAE) to detect distiiiiitiittiinnn states. We experimented with VAE- filtered pessimistic heuristics in Appendix C
Even pessimistic offline evaluation techniques [16] can
be useful in HuRI., 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-mximizattion 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, intuuterittuitively from the planning perspective, our work shows that for policy learning, inadmissible heuristies 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 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 tue-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 max aggreeggent heuristic. Farahmand et al. 8 use several related tasks to learn a dase-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 '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 the goal, and moving it further away the agent improves. This gradual increase in the horizon inspires the HuRL approach. However, HuRL does not require the agent be initialized on expert states and can work with many different base RL algorithms.
7 Discussion and Limitations
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 horizon-based regularization of RI., complementary to existing warm-starting schemes, and we provide theoretical and empirical analyses to support its effectiveness. While this is conceptual work without foresccable societal impacts yet, we hope that it will help counter some of Al'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 strong connection between good heuristics for HuRL. and pessimistic offline RI., techniques for the latter are not yet scalable and robust enough for high-dimensionall problems. Further research on offline RL can unlock the full potential of HuRL.
10

---

References
[1] Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemystaw Dębiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, al. Dota 2 with large scale deep reinforcement learning. arXiv preprint
2019.
[2] Oriol Vinyals, Igor Babuschkin, Wojeiech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Jun- young Chung. David Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et Grandmaster level in Starcraft II using multi-agent reinforcement learning. Nature, 575(7782):350-334
2019.
[3] Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforce- ment learning. In NIPS, 2015.
[4] Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving Markov decision processes with generative model. In NeurIPS, 2018.
[5] Chen Tessler and Shie Mannor. Maximizing the total reward via reward tweaking. arXiv preprint arXiv:2002.033327, 2020.
[6] Harm Van Seijen, Mehdi Fatemi, and Arash Tavakoli. Using a logarithmic mapping to enable lower discount factors in reinforcement learning. In NeurlPS, 2019.
[7] Mohak Bhardwaj. Sanjiban Choudhury, and Byron Boots. Blending mpe & value function approximation for efficient reinforcement learning, In ICLR, 2021.
[8] Amir-massoud Farahmand, Daniel N Nikovski, Yuji Igarashi, and Hiroki Konaka. Truncated approximate dynamic programming with task-dependent terminal value. In AAAI, 2016.
[9] Ashvin Nair, Murtaza Dalal, Abhishek Gupta, and Sergey Levine. Accelerating online rein- forcement learning with offline datasets. arXiv preprint arXiv:2006.09355 2020.
[10] Todd Hester, Matej Vecerik, Olivier Pietquin, Marc Lanetot, Tom Schaul, Bilal Piot, Dan Horgan, John Quan, Andrew Sendonaris, Ian Osband, et al. Deep Q-learning from demonstrations, In AAAI, 2018
[11] Mausam and Andrey Kolobov. Planning with Markov decision processes: An Al perspective. Synthesis Lectures on Artificial Intelligence and Machine Learning, 6:1-210, 2012.
[12] Dylan Foster and Alexander Rakhlin. Beyond UCB: Optimal and efficient contextual bandits with regression oracles. In 1CM1.
[13] Hoffmann and B. Nebel. The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research, 14:253-302, 2001.
[14] S. Richter and M. Westphal. The LAMA planner: Guiding cost- based anytime planning with landmarks. Journal of Artificial Intelligence Research, 39:1277177, 2010.
[15] Andrey Kolobov, Mausam, and Daniel S. Weld. Classical planning in MDP heuristics: With little help from generalization. In AAAI, 2010.
[16] Caglar Gulcehre, Sergio Gómez Colmenarejo, Ziyu Wang, Jakub Sygnowski, Thomas Paine, Konrad Zolna, Yutian Chen, Matthew Hoffman, Razvan Pascanu, and Nando de Freitas. Regu- larized behavior value estimation. arXiv preprint arXiv:2103.09555. 2021.
[17] Ching-An Cheng, Andrey Kolobov, and Alekh Agarwal. Policy improvement via imitation of multiple oracles. In NewrIPS, 2020.
[18] David Blackwell. Discrete dynamic programming. The Annals of Mathematical Statistics, pages 719-726, 1962.
[19] Marek Petrik and Bruno Scherrer. Biasing approximate dynamic programming with lower discount factor. In NIPS, 2008.

---

[20] Nan Jiang, Alex Kulesza, Satinder Singh, and Richard Lewis. The dependence of effective planning horizon on model accuracy. AAMAS, 2015.
[21] Nan Jiang, Satinder Singh, and Ambuj Tewari. On structural properties of mdps that bound loss due to shallow planning. In IJCAI, 2016.
[22] Yi-Chun Chen, Mykel Kochenderfer, and Matthijs TJ Spaan. Improving offline value-function approximations for pomdps by reducing discount factors. In IROS, 2018.
[23] Ron Amit, Ron Meir, and Kamil Ciosek. Discount factor as regularizer in reinforcement learning. In ICML, 2020.
[24] Peter E Hart, Nils J Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100-107,
1968.
[25] Cameron Browne, Edward Powley, Daniel Whitchouse, Simon M Lucas, Peter Cowling. Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and Al in games, 4(1):1 43, 2012.
[26] Mingyuan Zhong, Mikala Johnson, Yuval Tassa, Tom Erez, and Emanuel Todorov. Value function approximation and model predictive control. In IEEE International Symposium on Adaptive Dynamic Programming and Reinforcement Learning, pages 100-107, 2013.
[27] David Hoeller, Farbod Farshidian, and Marco Hutter. Deep value model predictive control. In CoRL, 2020.
[28] Wissam Bejjani, Rafael Papallas, Matteo Leonetti, and Mchmet R Dogar. Planning with a receding horizon for manipulation in clutter using learned value function. In Humanoids, pages 1-9, 2018.
[29] Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transforma- tions: Theory and application reward shaping. ICML., 1999.
[30] Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline RI.? arXiv preprint arXiv:2012.15085, 2020.
[31] Yao Liu, Adith Swaminathan, Alckh Agarwal, and Emma Brunskill. Provably good batch off-policy reinforcement learning without great exploration. In NeurIPS, 2020.
[32] Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: control. In IROS, 2012.
physics engine for model-based
[33] Sharada Mohanty, Jyotish Poonganam, Adrien Gaidon, Andrey Kolobov, Blake Wulfe, Dipam Chakraborty, Gražvydas Semetulskis, João Schapke. Jonas Kubilius, Jurgis Pašukonis, Linas Kli- mas, Matthew Hausknecht, Patrick MacAlpine, Quang Nhat Tran, Thomas Tumiel, Xiaocheng Tang, Xinwei Chen, Christopher Hesse, Jacob Hilton, William Hebgen Guss, Sahika Gene, John Schulman, and Karl Cobbe. Measuring sample efficiency and generalization in reinforcement learning benchmarks: NeurIPS 2020 Procgen benchmark. arXiv preprint 1333 2021.
[34] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is Q-learning provably efficient? In NeurIPS, 2018
[35] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In ICML, 2018
[36] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 2017.
[37] The garage contributors. Garage: A toolkit for reproducible reinforcement learning research.
http:///jthbbboommmwwwwggggo///p 2019.
12

---

[38] Yujing Hu, Weixun Wang. Hangtian Jia, Yixiang Wang, Yingfeng Chen, Jianye Hao, Feng Wu, and Changjie Fan. Learning utilize shaping rewards: A new approach of reward shaping, In NeurlPS, 2020.
[39] Harm Seijen and Rich Sutton. True online td (lambda). In ICML, 2014.
[40] Yonathan Efroni, Gal Dalal, Bruno Scherrer, and Shie Mannor. Beyond the one-step greedy approach in reinforcement learning. In ICML, 2018.
[41] John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. In ICLR, 2016.
[42] Craig Sherstan, Shibhansh Dohare, James MacGlashan, Johannes Günther, and Patrick M Pilarski. Gamma-nets: Generalizing value estimation over timescale. In AAAI, 2020.
[43] Joshua Romoff, Peter Henderson, Ahmed Touati, Emma Brunskill, Joelle Pineau, and Yann Ollivier. Separating value functions across time-scales. In ICML, 2019.
[44] Jacques Richalet, André Rault, JL Testud, and Papon. Model predictive heuristic control. Automatica, 14(5):413-42) 1978.
[45] Masataro Asai and Christian Muise. Learning neural-symbolis descriptive planning models via cube-space priors: The voyage home (to strips). In IJCAI, 2020.
[46] Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. In NeurlPS, 2020.
[47] Tyler Lu, Dale Schuurmans, and Craig Boutilier. Non-delusional q-learning and value iteration. In NeurIPS, 2018.
[48] Stwart J. Russell and Peter Norvig. Artificial Intelligence: A Modern Approach. Pearson, 4th edition, 2020.
[49] Judea Pearl. Heuristic search theory: Survey of recent results. IJCAI, 1981.
[50] Reinaldo AC Bianchi, Murilo Martins, Carlos HC Ribeiro, and Anna HR Costa. Heuristically. accelerated multiagent reinforcement learning. IEEE transactions cybernetics, 44(2):252- 265, 2013.
[51] Wen Sun, Arun Venkatraman, Geoffrey Gordon, Byron Boots, and J Andrew Bagnell. Deeply aggrevated: Differentiable imitation learning for sequential prediction. ICML, 2017.
[52] Wen Sun, Andrew Bagnell, and Byron Boots. Truncated horizon policy search: Combining reinforcement learning & imitation learning. In ICLR, 2018.
[53] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. arXiv preprint arXiv: 1503.02531, 2015.
[54] Carlos Florensa, David Held, Markus Wulfmeier, Michael Zhang, and Pieter Abbeel. Reverse curriculum generation for reinforcement learning. In CoRL, 2017.
[55] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In ICML, 2002.
[56] Karl Cobbe, Christopher Hesse, Jacob Hilton, and John Schulman. Leveraging procedural generation to benchmark reinforcement learning. In ICML, 2020.
[57] Eric Liang, Richard Liaw, Robert Nishihara, Philipp Moritz, Roy Fox, Ken Goldberg, Joseph Gonzalez, Michael Jordan, and Ion Stoica. RLlib: Abstractions for distributed reinforcement learning. In ICML, 2018
[58] Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, Shane Legg, and Koray Kavukcuoglu. IMPALA: Scalable distributed deep-RL. with importance weighted actor-learner architectures. In ICMI. 2018.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Section
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Section 7
a conceptual work that doesn't 't have foreseeable societal impacts yet.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] The assump- tions the theorem, proposition, and lemma statements throughout the paper. (b) Did you include complete proofs of all theoretical results? [Yes] Appendix and
Appendix B
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material URL)? [Yes] In the supplemental material.
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] Appendix C
(c) Did you report error bars (e.g., with respect to the random seed after running experi-
ments multiple times)? [Yes] Section and Appendix C
(d) Did you include the total amount of compute and the type of resources used (e.g., type
of GPUs, internal cluster, or cloud provider)? [Yes] Appendix
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? and [33 in Section
[Yes] References 337 32
(b) Did you mention the license of the assets? [Yes] In Section 5.1
(c) Did you include any assets either in the supplemental material URL? [Yes] Heuristic computation and scripts to run training.
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're
using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "qtANw67wiOw", "reviewer": "Reviewer_RNky", "summary": "This work presents a theoretical framework for reasoning about solving MDPs in which agents have access to pretrained \"heuristics\", which are defined as functions that provide some prior over the optimal value function. The framework is used to define a regularization technique for mixing a such heuristics into the training of a standard model-free RL pipeline, presenting experiments on Mujoco and Procgen with a variety of heuristic baselines.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "TL;DR -- This is a relatively good paper. The work presents a sound regularization technique for incorporating some prior knowledge about the task, as well as a good theoretical framework for reasoning about the method and potential follow ups. There remain some doubts / questions about the breadth of classes of heuristics that can be effectively used in this setting.\n\nI enjoyed reading the manuscript. It is well written, mostly backed up by a good literature research, and has a decent amount of low level details in both the main document and the appendix.\n\nThings that I think could be improved:\n\n1. I think \"heuristics\" here is used a little too across the text. Before getting to Section 2, I was under the impression that the method would have involved some form of heuristic *policy*, rather than a \"prior guess of the optimal value function $V*$\" (Section 2.2). Other readers might be confused by this mismatch, and I think it'd be appropriate to think about a different nomenclature. If anything, is there prior work that uses the same definition?\n\n2. Much of the presented experimental setting relies on fitting a Monte-Carlo regressor on some observed data. While sound, it seems quite a relatively naive / weak heuristics whose effectiveness is highly dependent on the shape and behavior of task / reward function. In particular, in the experiments the manuscript does not seem to explicitly declare how the data is collected. Are the various heuristics trained from data collected by SAC at different training times? If so, how do they qualitatively look like wrt. the presented tasks?\n\n3. It's a little hard placing this work in the existing literature because there's a vast amount of work that tries to utilise prior information about the task (e.g. via knowledge distillation, transfer learning, expert-based training) in all sorts of contexts. Some of this work is covered in the manuscript's lit review, but there's much that isn't:\n  a. https://ojs.aaai.org/index.php/AAAI/article/view/5963\n  b. https://arxiv.org/abs/2009.07888\n  c. https://arxiv.org/abs/1905.01240\n  d. https://arxiv.org/abs/1905.06750 (and so forth...)\n\n t think a lot of this stems from the paper pushing an overly general narrative about \"heuristics\", while actually using a rather narrow definition and formalisation of it.\n\nSo, ultimately I am going to recommend for acceptance, but I would like some additional clarity on the following to improve my score:\n\n- How's this method generally superior to standard distillation methods in RL? (Or at the very least how does it compare generally?)\n- Considering many heuristics out in the wild are in the form of more or less fixed policies, what could be some strategies for adapting these to be employed in HuRL? (It's probably okay to hypothesise, guess, or even present naive / baseline ideas, but at the very least discussing this in a informed manner in the manuscript would be useful)\n- How do the heuristics used in the experiments generally look like? (i.e. generally more clarity on this, rather than handwaveing them as just monte-carlo regression of some data)\n\n## After-rebuttal Edit\n\nGiven the authors' responses to my and other reviewers comments, I am happy to raise my score to full accept.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some limitations of the work were discussed, however I have raised some points in the main review about adding some further discussion and clarity on some of them.\n\nI haven't seen an explicit discussion on societal impact of the work in the manuscript.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "KzvbrkGhefm", "reviewer": "Reviewer_58wi", "summary": "  This paper proposed an alternative framework for reward shaping in RL\n  that uses a heuristic function.\n\n  Unlike potential-based reward shaping, the algorithm does not subtract\n  the heursitic value of the current state from the reward.  There is a\n  coefficient for the heursitic value to be added to the reward.\n  After each episode, it incrementally increases the discounting factor\n  (converges to 1) and decreases the coefficient for the heuristic value\n  (converges to 0).\n\n  In section 4, the authors theoretically analysed their framework.\n  During the analysis, the authors rediscovered *admissibility* &\n  *consistency*, concepts that are already well-known in shortest path\n  finding literature from the earliest history of AI (can be traced back\n  to 1968).  Obviously, being such a fundamental, well-known concepts,\n  you are not allowed to rename and replace them, so it is necessary to\n  fix these definitions to match the existing literature.  However,\n  although these definitions and proofs are not new, I believe *the\n  finding that admissibility & consistency will help RL is quite new*,\n  and has never been theoretically analyzed before.  This will attract\n  the attention of not just the RL community but also of the symbolic\n  AI community.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "2 Definition 4.1 and Proposition 4.4 are well-known concepts in shortest path finding literature - rename them\n==============================================================================================================\n\n  Despite I am not familiar with the regret & bias analyses in RL,\n  definitions and propositions in section 4 are known.  Definition 4.1\n  is called *consistency*, and $V^*(s)\\geq f(s)$ is called\n  *admissibility*.  Proposition 4.4 is known (consistency implies\n  admissibility).  Both are important concepts in search algorithm\n  literature and in deterministic/stochastic shortest path finding on\n  graphs (which is my primary background).\n\n  In shortest path finding problems, we have costs instead of rewards,\n  which are typically not discounted, and is aimed to be minimized.\n  For a moment, assume a problem of finding the smallest cost path to\n  one of the goal states $G$ on a graph with deterministic transitions.\n  We define $h^*(s)$ to be the shortest path cost from the current state\n  $s$ to the nearest goal $g\\in G$.  A heuristic function $h(s)$ is an\n  estimate of $h^*(s)$. (see the resemblance to $V(s)$ and $V^*(s)$.)\n\n  An *admissible* heuristic function is an optimistic heuristic function\n  that never overestimates $h^*(s)$, i.e., $h(s) \\leq h^*(s)$.\n  Many heuristic graph search algorithms, most notably $A^*$, are\n  guaranteed to find an optimal solution if it uses\n  admissible heuristics.\n\n  Moreover, a heuristic function is called *consistent* or *monotonic*\n  when, for every action $a$, $h(s) \\leq c(s,a,s')+h(s')$.  Obviously,\n  this is a deterministic Bellman equasion.  With a consistent\n  heuristics, $A^*$ has a more desirable guarantee that it never\n  re-expands the same node.  The name derives from the fact that the\n  heuristic value monotonically decreases toward the goal on any optimal\n  solution, and thus consistently guides the search toward the goal\n  (without misguiding along the path; i.e., without increasing values).\n  Consistency implies admissibility.\n\n  These fundamental facts are discovered by the seminal paper of $A^*$\n  by Hart et al, 1968.  You can find them in every symbolic AI textbook\n  that most surely covers $A^*$, such as [1], but I guess you are only\n  familiar with post-deep-RL literature and lack history.  Later, these\n  concepts are extended to stochastic domains by [2] when they describe\n  Loop-AO* algorithm for stochastic shortest path problems.\n\n  [1] Stuart J. Russell, Peter Norvig: Artificial Intelligence: A Modern\n  Approach (4th Edition). Pearson 2020, ISBN 9780134610993\n\n  [2] Hansen, Eric A., and Shlomo Zilberstein. \"LAO∗: A heuristic search\n  algorithm that finds solutions with loops.\" Artificial Intelligence\n  129.1-2 (2001): 35-62.\n\n\n3 Other comments\n================\n\n  Since I am not familiar with the theoretical analyses of RL\n  algorithms, it is difficult for me to understand Section 4.  So I\n  instead have several high-level questions to the authors that could be\n  perhaps implied by the theorem but is not communicated effectively to\n  the wider audience.\n\n  In l.350, you mention \"our reshaped MDP can be shown to be equivalent\n  to ... PBRS\". Where is this shown? Why this is true?\n\n  I am not quite sure if the proposed HuRL guarantees that the resulting\n  policy will converge to the optimal in the original MDP.  Otherwise,\n  unlike potential-based reward shaping, this is like shifting the goal\n  post, and it is theoretically less appealing because it is not\n  optimizing what we want to optimize.\n\n\n  This paper does not specify the exact definition of f(s).  Is it an\n  estimate of V*? If it is an estimate of V*, is it an estimate of the\n  cumulative discounted reward with the same discount factor?\n  For heuristic functions in graph search, these questions do not arise\n  because we do not typically use discounting.\n\n\n        However, PBRS does not fully leverage information provided\n        by the heuristic because it still requires the learning\n        agent to solve a long horizon problem, which is the main\n        source of difficulty in RL. Conceptually ∗when the\n        heuristic is the optimal value function f = V , the agent\n        should be able to find the optimal policy π∗ of M by\n        acting myopically, as V ∗ already contains all necessary\n        long-term information for good decision making. However RL\n        with PBRS does not enable such a solution concept.\n\n  I believe this is a miunderstanding.  The authors does not\n  sufficiently explain why \"PBRS does not enable such a solution\n  concept\", And indeed the proposition \"PBRS does not enable such a\n  solution concept\" is incorrect.  ~r(s,a,s') = r(s,a,s') + γh(s')-h(s)\n  is equivalent to V*(s) = ~V*(s) + h(s) and Q*(s,a) = ~Q*(s,a) +\n  h(s). [Ng, Harada, Russel, 1999] So if you just adjust the value of\n  ~V* by h post-hoc, then acting myopically according to ~V*+h is\n  equivalent to acting myopically according to V* (Same for Q*.)\n\n\n        In the planning literature, this is typically achieved by\n        relaxing the problem using domain knowledge.  ...\n        Although using heuristics to accelerate search has been\n        popular in planning and control, such as $A^*$ [12], MCTS\n        [13], and MPC [7, 14–16], its theory is less developed for\n        the setting where the MDP is unknown.\n\n  Actually, [i,ii] learns a world model which is compatible with\n  planning formalisms and can directly benefit from relaxation-based\n  heuristics and shows substantial speedup without any policy learning.\n\n  [i] Masataro Asai, Hiroshi Kajino, Alex Fukunaga, Christian Muise:\n  Classical Planning in Deep Latent Space. CoRR abs/2107.00110 (2021)\n  [ii] Masataro Asai, Christian Muise: Learning Neural-Symbolic\n  Descriptive Planning Models via Cube-Space Priors: The Voyage Home (to\n  STRIPS). IJCAI 2020: 2676-2682\n\n\n  Finally, the evaluation does not include comparisons against\n  potential-based reward shaping.  HuRL and PBRS are given the same\n  amount of information from the environment --- if you claim HuRL is\n  better than PBRS, you should definitely compare the results.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper is categorized as basic research rather than applied research. It is not likely to cause large societal nor environmental impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "4n4vLP-BIu2", "reviewer": "Reviewer_bqji", "summary": "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors proposed a novel variant of the existing ideas (of warm starts) and gave some theoretical reasoning. However, the experiments are very limited in nature:\n1) The idea was proposed as a solution to the long-term credit assignment and long horizon problems in reinforcement learning but the results were demonstrated on simple MuJoCo tasks\n2) The details of how long (number of time steps or episodes?) the value function was trained is unclear. A comparison of a standard algorithm (like SAC) using this pre-trained value function vs HuRL-MC would be useful. \n3) Am I understanding correctly that in the plots, HuRL-MC starts with pre-trained value function whereas SAC starts training from scratch? I do not think this is a fair comparison \n4) The authors cited several other warm-starts and regularization based approaches but no performance comparison with those algorithms was provided thus making it difficult to understand the effectiveness of the proposed algorithm\n5) The authors mentioned that for each environment, they performed hyper parameter tuning for learning rates and the discount factor of SAC and then $\\lambda_0$ and $w$ were tuned for each heuristic of each environment. In my opinion, this is an extreme overkill and consumes a lot of computational resources. I recommend authors to clarify this and provide comparisons of the computational resources used (including resources for hyper parameter tuning)  \n\nOverall, the proposed algorithm is a novel variant and the authors provided sufficient theoretical backing but the experiments are seriously lacking. The current experimental results do not demonstrate the superiority of the algorithm at all. I am willing to increase my score if my 5 concerns above are addressed. Additionally, it would be nicer to relate the proposed algorithm with the curriculum learning literature as the setup seems very similar. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors should address the impact of using biased data (and the quality of the dataset in general) for pre-training the heuristic value functions", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "0bTlILrEXO", "reviewer": "Reviewer_vrFt", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nOverall positive comments:\n\n* To my knowledge, the MDP reduction proposed in this work has not been previously considered in the literature.\n* The inclusion of code with the submission is appreciated.\n* Reporting results with 30 random seeds is commendable!\n* The paper is relatively well organized.\n* The related work section covers the main areas that I would consider relevant.\n* I did not find any major errors in the theoretical analysis.\n* Proposition 2.4 is quite interesting -- I wish there were more discussion and focus on that result.\n\n\nCritiques and concerns:\n\n\n* My main concern is significance with respect to potential-based reward shaping (PBRS). As a practitioner, I am not sure why I would opt for HuRL instead of PBRS. \n\nThe main benefit of PBRS is that it is optimality-preserving, so there is no need to worry about introducing Bias, like there is with HuRL. Another benefit of PBRS is that it does not require tuning any of the additional hyperparameters that are introduced in HuRL. \n\nThe paper mentions two possible reasons to prefer HuRL: \n\n(1) “PBRS does not fully leverage information provided by the heuristic because it still requires the learning agent to solve a long horizon problem, which is the main source of difficulty in RL. Conceptually, when the heuristic is the optimal value function, the agent should be able to find the optimal policy by acting myopically, as $V^*$ already contains all necessary long-term information for good decision making.” [L103-108]\n\n\n(2) “We choose (2) over the PBRS version, because the latter does not preserve the properties in Proposition 4.2.” [Footnote 3]\n\nThe second reason is interesting, but requires more discussion and support (e.g. proof that PBRS does not have the properties in proposition 4.2). The first reason is presented as the main motivation for not using PBRS, but I do not find it convincing. For example, in the original PBRS paper, at the end of their Section 3, they discuss how reward shaping using the optimal value function $V^*$ would work particularly well for PBRS, saying that all that would be left to do is determine Q values from V, which could be done with only a one-step lookahead (myopically). If I am misunderstanding the claims of L103-108, please let me know in the rebuttal, ideally with a concrete example.\n\n\nFinally, PBRS should be included as a baseline in the experiments. This is an important empirical omission.\n   * Relatedly, the claims that heuristics have not been considered very much in RL (e.g. L99-100) is not very convincing if we understand heuristics to be essentially the same as reward shaping, on which there has been a lot of work.\n   * The environments and methods considered in the experiments are standard and sensible, but I would have liked to see HuRL applied in a setting where RL without heuristics is intractable and some good heuristics are available. One interesting possibility would be to borrow from the classical planning literature and use domain-independent PDDL heuristics (e.g., with PDDLGym).\n   * Also, given the origin of the heuristics in the experiments, and the discussion of offline RL throughout the paper, it would be good to see offline RL baselines.\n   * The fact that the HuRL-specific hyperparameters need to be tuned per-environment is limiting.\n   * It looks like HuRL may be prematurely plateauing in Figure 2(c) [swimmer], can you comment on that?\n\n\nMinor:\n   * L22: manifests -> manifest\n   * L74: wlog, reward function bounded between [0, 1]. This is not really wlog -- boundedness of the reward is an additional assumption.\n   * L219: Regret(f,0,\\pi) should be Regret(f,1,\\pi)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See “concerns and critiques” above.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: I thank the authors for their submission and active participation in the discussions. The majority of reviewers find this paper valuable, in particular they emphasized the novelty [bqji], a good theoretical framework [RNky] with new findings that admissibility consistency help RL [58wi], a comprehensive discussion of related literature [RNky,vrFt], and that the paper is well structured and well written [RNky,vrFt]. On the negative side, reviewer bqji voiced concerns about limited experimental validation. I believe the authors have addressed these concerns well in their rebuttal. I thus side with reviewers RNky, vrFt and 58wi, and recommend acceptance. I encourage the authors to further improve their paper based on the reviewer feedback.

Decision: Accept (Poster)