Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
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:
1) 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
2) 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. 
3) 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 
4) 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
5) 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)  

Overall, 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. 
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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

I 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.

Things that I think could be improved:

1. 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?

2. 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?

3. 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:
  a. https://ojs.aaai.org/index.php/AAAI/article/view/5963
  b. https://arxiv.org/abs/2009.07888
  c. https://arxiv.org/abs/1905.01240
  d. https://arxiv.org/abs/1905.06750 (and so forth...)

 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.

So, ultimately I am going to recommend for acceptance, but I would like some additional clarity on the following to improve my score:

- How's this method generally superior to standard distillation methods in RL? (Or at the very least how does it compare generally?)
- 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)
- 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)

## After-rebuttal Edit

Given the authors' responses to my and other reviewers comments, I am happy to raise my score to full accept.
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.

I haven't seen an explicit discussion on societal impact of the work in the manuscript.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary:   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.

main_review: 2 Definition 4.1 and Proposition 4.4 are well-known concepts in shortest path finding literature - rename them
==============================================================================================================

  Despite I am not familiar with the regret & bias analyses in RL,
  definitions and propositions in section 4 are known.  Definition 4.1
  is called *consistency*, and $V^*(s)\geq f(s)$ is called
  *admissibility*.  Proposition 4.4 is known (consistency implies
  admissibility).  Both are important concepts in search algorithm
  literature and in deterministic/stochastic shortest path finding on
  graphs (which is my primary background).

  In shortest path finding problems, we have costs instead of rewards,
  which are typically not discounted, and is aimed to be minimized.
  For a moment, assume a problem of finding the smallest cost path to
  one of the goal states $G$ on a graph with deterministic transitions.
  We define $h^*(s)$ to be the shortest path cost from the current state
  $s$ to the nearest goal $g\in G$.  A heuristic function $h(s)$ is an
  estimate of $h^*(s)$. (see the resemblance to $V(s)$ and $V^*(s)$.)

  An *admissible* heuristic function is an optimistic heuristic function
  that never overestimates $h^*(s)$, i.e., $h(s) \leq h^*(s)$.
  Many heuristic graph search algorithms, most notably $A^*$, are
  guaranteed to find an optimal solution if it uses
  admissible heuristics.

  Moreover, a heuristic function is called *consistent* or *monotonic*
  when, for every action $a$, $h(s) \leq c(s,a,s')+h(s')$.  Obviously,
  this is a deterministic Bellman equasion.  With a consistent
  heuristics, $A^*$ has a more desirable guarantee that it never
  re-expands the same node.  The name derives from the fact that the
  heuristic value monotonically decreases toward the goal on any optimal
  solution, and thus consistently guides the search toward the goal
  (without misguiding along the path; i.e., without increasing values).
  Consistency implies admissibility.

  These fundamental facts are discovered by the seminal paper of $A^*$
  by Hart et al, 1968.  You can find them in every symbolic AI textbook
  that most surely covers $A^*$, such as [1], but I guess you are only
  familiar with post-deep-RL literature and lack history.  Later, these
  concepts are extended to stochastic domains by [2] when they describe
  Loop-AO* algorithm for stochastic shortest path problems.

  [1] Stuart J. Russell, Peter Norvig: Artificial Intelligence: A Modern
  Approach (4th Edition). Pearson 2020, ISBN 9780134610993

  [2] Hansen, Eric A., and Shlomo Zilberstein. "LAO∗: A heuristic search
  algorithm that finds solutions with loops." Artificial Intelligence
  129.1-2 (2001): 35-62.


3 Other comments
================

  Since I am not familiar with the theoretical analyses of RL
  algorithms, it is difficult for me to understand Section 4.  So I
  instead have several high-level questions to the authors that could be
  perhaps implied by the theorem but is not communicated effectively to
  the wider audience.

  In l.350, you mention "our reshaped MDP can be shown to be equivalent
  to ... PBRS". Where is this shown? Why this is true?

  I am not quite sure if the proposed HuRL guarantees that the resulting
  policy will converge to the optimal in the original MDP.  Otherwise,
  unlike potential-based reward shaping, this is like shifting the goal
  post, and it is theoretically less appealing because it is not
  optimizing what we want to optimize.


  This paper does not specify the exact definition of f(s).  Is it an
  estimate of V*? If it is an estimate of V*, is it an estimate of the
  cumulative discounted reward with the same discount factor?
  For heuristic functions in graph search, these questions do not arise
  because we do not typically use discounting.


        However, 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 f = V , the agent
        should be able to find the optimal policy π∗ of M by
        acting myopically, as V ∗ already contains all necessary
        long-term information for good decision making. However RL
        with PBRS does not enable such a solution concept.

  I believe this is a miunderstanding.  The authors does not
  sufficiently explain why "PBRS does not enable such a solution
  concept", And indeed the proposition "PBRS does not enable such a
  solution concept" is incorrect.  ~r(s,a,s') = r(s,a,s') + γh(s')-h(s)
  is equivalent to V*(s) = ~V*(s) + h(s) and Q*(s,a) = ~Q*(s,a) +
  h(s). [Ng, Harada, Russel, 1999] So if you just adjust the value of
  ~V* by h post-hoc, then acting myopically according to ~V*+h is
  equivalent to acting myopically according to V* (Same for Q*.)


        In the planning literature, this is typically achieved by
        relaxing the problem using domain knowledge.  ...
        Although using heuristics to accelerate search has been
        popular in planning and control, such as $A^*$ [12], MCTS
        [13], and MPC [7, 14–16], its theory is less developed for
        the setting where the MDP is unknown.

  Actually, [i,ii] learns a world model which is compatible with
  planning formalisms and can directly benefit from relaxation-based
  heuristics and shows substantial speedup without any policy learning.

  [i] Masataro Asai, Hiroshi Kajino, Alex Fukunaga, Christian Muise:
  Classical Planning in Deep Latent Space. CoRR abs/2107.00110 (2021)
  [ii] Masataro Asai, Christian Muise: Learning Neural-Symbolic
  Descriptive Planning Models via Cube-Space Priors: The Voyage Home (to
  STRIPS). IJCAI 2020: 2676-2682


  Finally, the evaluation does not include comparisons against
  potential-based reward shaping.  HuRL and PBRS are given the same
  amount of information from the environment --- if you claim HuRL is
  better than PBRS, you should definitely compare the results.

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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: 
Overall positive comments:

* To my knowledge, the MDP reduction proposed in this work has not been previously considered in the literature.
* The inclusion of code with the submission is appreciated.
* Reporting results with 30 random seeds is commendable!
* The paper is relatively well organized.
* The related work section covers the main areas that I would consider relevant.
* I did not find any major errors in the theoretical analysis.
* Proposition 2.4 is quite interesting -- I wish there were more discussion and focus on that result.


Critiques and concerns:


* 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. 

The 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. 

The paper mentions two possible reasons to prefer HuRL: 

(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]


(2) “We choose (2) over the PBRS version, because the latter does not preserve the properties in Proposition 4.2.” [Footnote 3]

The 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.


Finally, PBRS should be included as a baseline in the experiments. This is an important empirical omission.
   * 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.
   * 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).
   * 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.
   * The fact that the HuRL-specific hyperparameters need to be tuned per-environment is limiting.
   * It looks like HuRL may be prematurely plateauing in Figure 2(c) [swimmer], can you comment on that?


Minor:
   * L22: manifests -> manifest
   * L74: wlog, reward function bounded between [0, 1]. This is not really wlog -- boundedness of the reward is an additional assumption.
   * L219: Regret(f,0,\pi) should be Regret(f,1,\pi)
limitations_and_societal_impact: See “concerns and critiques” above.
review_title: null

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)