Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: = Overview = 

The paper proposes "Asymptotically equivalent reward shaping", a new reward shaping approach that extent potential-based reward shaping to allow for shaping functions that -- even if eventually altering the resulting optimal policy -- retain key elements in the performance of such policy, namely ensuring that the resulting policy leads the agent to a subset of the states that the original optimal policy does. The paper also proposes a method to compute a shaping function from behavior demonstration.
 
= Positive points =

The idea of reward shaping is important in reinforcement learning, as it can have an important impact in terms of sample complexity. As far as I know, this area of research has not seen significant advances or new ideas in recent years. The paper provides a fresh view of this problem, by proposing to alleviate the requirement that the shaped function should lead to the same optimal policies.

= Negative points =

The proposed approach seems to be restricted to a very narrow class of MDPs. Additionally, the proposed shaping function is presented with little motivation, intuition or discussion whatsoever. Finally, the experimental evaluation is not very convincing, as the proposed approach is compared with "arbitrary" potential based shaping functions (more details below).

= Comments = 

The paper addresses a problem that, in my view, is relevant to the RL community and has not seen many advances in recent years. Its premise is that the "classical" reward shaping may be too restrictive, in that it requires the optimal policies before and after shaping should be the same. The paper instead proposes to alleviate this requirement, as long as the resulting policies lead to "similar" long-term behavior. 

This notion is, in my view, interesting and in line with work on intrinsic motivation, by Barto and collaborators, and in reward optimization conducted by Sorg, Sequeira and others. In this respect, it could be relevant to at least mention this line of work in the paper.

In addressing reward shaping, however, the paper restricts to problems where the reward is binary (i.e., 0 most of the time, and 1 in some states). These are, essentially, goal-driven MDPs, where the optimal policy just drives the agent towards one of the states with non-zero reward. The paper notes that, if the reward is shaped by providing sufficiently small reward values in the non-goal states and the discount is made sufficiently large, the optimal policy will still lead the agent to one of the goal states. This is a relatively straightforward conclusion, and the whole shaping strategy proposed by the paper follows from this simple observation.

The paper then proposes a shaping function from a given demonstration (consisting of a sequence of states). Unfortunately, the presented shaping function is introduced with no motivation, intuition, or discussion whatsoever, and one wonders why such shaping function is a good idea.

The paper concludes with an experimental evaluation section, where the proposed approach is compared against potential-based reward shaping and shown to outperform the latter. However, the potential-based shaping functions used for comparison are introduced in an ad hoc manner, and it is not clear to me why these shaping functions are good baselines for comparison.

Finally, on a small note, I feel that the paper could benefit from cleaning up/streamlining the notation and language. For example, why the proposed notion of "asymptotic equivalence" is called asymptotic of equivalence is unclear, since the notion of "optimal asymptotic volume", on which the former builds, is defined for a finite time (not asymptotic), and the relation does not seem to be an equivalence (if for no other reason, it does not seem symmetric to me). Definitions 4.1-4.3 make use of heavy notation but translate a very simple notion: that an MDP M is "asymptotically equivalent" to an MDP M' if the optimal policy of the former leads the agent to a subset of the goal states of the latter.
review_title: The ideas in the paper are potentially interesting, but the assumptions appear somewhat restrictive, the experiments are unconvincing, and there are a couple of technical details that lack discussion.

final_score: rating: 7: Good paper, accept
review_content: SUMMARY OF CONTRIBUTION:

This work presents asymptotically-equivalent (ASEQ) reward shaping as an alternative to potential-based shaping.  ASEQ shaping admits a more general class of augmented reward functions than potential based shaping, at the cost of a weaker notion of equivalence between the classes of optimal policies for the original MDP and the augmented MDP.  ASEQ assumes that the original MDP uses a binary reward function that is 1 for all states in a subset of the state space to which any optimal policy will converge (effectively the "goal" of the MDP), and 0 elsewhere.  The theoretical results presented in this work show that for any augmented reward function which is between 0 and 1 outside of the goal region, and for a sufficiently large discount factor, the an optimal policy for the augmented reward will converge to this goal region.  The flexibility of this form of reward shaping with a plan-based shaping reward that provides smaller rewards for reaching waypoints along a path to the goal.  The advantage of this form of shaping reward over more limited potential-based shaping is demonstrated on a set of simulated robotic manipulation tasks.

AREAS OF CONCERN:

One potential issue with the experimental results is that the potential function used for the baseline is defined identically to the plan-based shaping reward used with ASEQ shaping.  While this is the most direct comparison between the two approaches, it is possible that using potential-based shaping with a simpler potential function, such as the distance between the box and the goal, would lead to better performance for potential-based shaping.

As reward shaping is a meta-algorithm that can be applied to almost any RL method, it would also be useful to evaluate ASEQ shaping on multiple RL algorithms, not simply DDPG, to show that the benefits of the more flexible class of shaping rewards are not limited to a single class of algorithms.

There are some places where the notation could be improved:
  1) The notation in Equations (1) and (2) is somewhat awkward, as q_pi appears to be a distribution over transitions in (1), but is defined as a distribution over entire trajectories in (2).
  2) It isn't entirely clear what the subscript 'a' of the sets G_a in definitions 4.1 and 4.2 refers to.

CONCLUSION:

While the form of shaping reward used in this work is not itself novel, the work does for the first time formally describes the class of problems to which this more general form of reward shaping can be applied, with conditions on the form of the shaping reward that guarantee compatibility with the original task.  The work does have its limitations, both in terms of the class of problems to which ASEQ shaping can be applied, and in terms of the depth of the empirical evaluations, but it will be of value to the community nonetheless.
review_title: This work presents asymptotically-equivalent reward shaping as an alternative to potential-based shaping.  Theoretical results show that for certain goal-oriented MDPs, the much more flexible class of ASEQ shaping rewards yield policies that converge to the same goal regions as optimal policies for the original MDP. 

final_score: rating: 7: Good paper, accept
review_content: POST-REBUTTAL UPDATE
======================

The rebuttal and resulting changes have addressed most of my concerns, and expanding the alternative reward-shaping aspect of the evaluation has helped too. I've increased the score.

======================


SUMMARY

The paper introduces a new, plan-based reward shaping approach to RL called ASEQ-RS. It is a generalization of potential-based reward shaping, one that doesn't have the same optimality guarantees but empirically facilitates faster policy learning.


HIGH-LEVEL ASSESSMENT

The paper's approach looks interesting, especially empirically. However, I have a number of concerns about the paper's theory: much of it seems to have errors. The paper can't be published with these errors, which is why I'm giving a slightly below borderline score for now. However, these error might be easily fixable. If the authors demonstrate a way to fix them without detracting much from the generality of the results, I'll increase the score, because the approach looks useful in practice.  


TECHNICAL ISSUES/QUESTIONS

-- Def. 4.3 seems to have an error, in the sense that it doesn't quite have the interpretation stated in the paragraph below it. If an MDP has G = \emptyset (which is possible if different optimal policies lead to disjoint parts of the state space), it is asymptotically equivalent to any other MDP ver the same state and action space according to Def. 4.3, but it certainly doesn't mean that optimally behaving in this MDP and some other that has G \neq \empyset will have the same result. This may be fixable by excluding G = \emptyset MDPs from consideration, although I haven't fully verified this.

-- Def. 4.3 is also broken in the sense that the notion of equivalent it introduces is asymmetric, which contradicts the intuitive meaning of equivalence. Perhaps the easiest way to fix this one is to replace the term "equivalent" in this definition with something else.  

-- Theorem 4.1's statement is ambiguous: when you say "Let M be convergent with optimal asymptotic volume G \subseteq B", are you assuming that M's asymptotic volume is always a subset of B? Or are you implicitly saying "*if* M's asymptotic volume is a subset of B, then let's call it G"? If it's the former, then that assumption is invalid -- due to \gamma being strictly less than 1, the optimal policy may eventually choose an action that lead to B with some probability and with some probability leads to a region with reward 0 (outside of B).

This can be quite an issue for Cor. 4.1.1 and Theorem 4.2, which are based on 4.1, and also in practice, because in non-ergodic MDPs with a discount factor the former version of the assumption can easily fail to hold, potenially breaking the paper's main results.

-- Theorem 4.1 loses its meaning if B = emptyset, in a similar way as Def 4.3. 

-- The last paragraph on p.4 promises that the bound on gamma can be relaxed by Theorem 4.2, but I can't find a formal result that shows what the new bound on \gamma as a result of Theorem 4.2 is. This is important because in practice due to issues caused by function approximation, in RL one wants to set \gamma as low as possible. So what are the implications of Theorem 4.2 for choosing gamma?

 
Language errors:

"worst-case bound to the reward function:" --> "worst-case bound on the reward function:"

"lower bound to \gamma" --> "lower bound on \gamma"

"upper bound to" --> "upper bound on"

(Please search through the paper and fix all mistakes like the above.)
review_title: A potentially useful approach to reward shaping in robotics settings.

final_score: rating: 3: Clear rejection
review_content: In this paper the authors introduce an asymptotic-equivalent (ASEQ) reward shaping reinforcement learning algorithm, which, they argue, is a relaxation of potential based reward shaping (PB). The authors present results suggesting that the proposed ASEQ method is significantly better than PB. 

The authors state that this new method is a superset of PB (or a “subclass of reward shaping broader than PB”) which allows for a policy to be determined by shaping rewards on all intermediate states in a trajectory. There is unconvincing details on how this is done (eg. the authors state that it is ‘more direct’). 

The authors make claims that this new method is suitable in difficult exploration problems in high-dimensional states spaces. They do not show evidence to support this claim and evaluate their method in a 10-d state space robotic manipulation task. 

The contributions of this work are stated unconvincingly. For example, claims 1 and 2 are the same. The authors do not compare this method with other learning from demonstration methods (e.g. behavioural cloning or Generative Adversarial Imitation Learning)

Definition 4.1 is unclear and \mathcal{G} is undefined. There are assumptions that the authors state about the applicability of this method, such as at the end of section 4.1 regarding the likelihood of an agent leaving a well-defined volume of state space. The authors make claims that their method is asymptotically equivalent, that is in the long run, behaviour in a modified MDP will have the same result in a modified MDP. I would urge the authors to clarify this point. 

The metic state-space (\mathcal{S}, d) is not well defined in Theorem 4.2. 

The authors present their method as a modification to DDPG, and show that reward shaping leads to better performance on their tasks than no reward shaping. This is a likely outcome, given that they are providing the method with additional information. 

I would urge the authors to compare against algorithms which use the same information, and stronger baselines rather than just ablative baselines on their method.  Finally, I do not think that this work is a good fit for ICLR given that it is more related to methods in reward shaping for reinforcement learning as opposed to the topics of more general greater interest to the audience at ICLR. 

review_title: Review of Plan-Based Asymptotically Equivalent Reward Shaping

Meta-review: Summary:
This paper introduces a novel type of reward shaping (not potential-based) that can work for MDPs with 0/1 rewards (e.g., systems with goal states). I think the paper contains a nice nice of empirical results, clear explanations/insights, and theoretical contributions.
As long as the authors do a good job saying up-front what kinds of MDPs the method does/does not address, this would provide an interesting addition to practical methods for solving sparse-reward RL tasks.
The paper could be strengthened with additional empirical results, but that is almost always true, and I think the number and quality of experiments are well above the bar.
The paper could also be strengthened if it better compared with other ways of using demonstrations. This is done in the text, but not empirically, as the authors wanted to focus on reward shaping methods. I think this is a relatively minor point and does not outweigh the many positives.

Discussion:
One reviewer remains against accepting this paper. I respectfully disagree with their evaluation and unfortunately they did not update their review after the responses. Hopefully they would agree the final version of this paper is indeed a useful contribution.

Recommendation:
I believe this paper should be accepted based on the science. 
Decision: Accept (Poster)