Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper the problem modifying a very sparse reward, e.g., an
indicator for task completion, in a manner that remains sparse but
increases the "informativeness". The resulting reward should ideally
result in faster convergence of RL style learning algorithms.  The
paper formulates this reward design problem as a form of discrete
optimization and provide a greedy approximation scheme, which is
proved to not deviate too much from the optimum.  Furthermore, a
theoretical analysis shows the relates this new measure to existing
reward design algorithms, and in particular potential based shaping.
Finally, the paper illustrates the approach on two domains, leveraging
state space abstraction to support continuous dynamics. There they show
that the they are indeed able to learn sparse rewards in a manner that
optionally incorporates and improves convergence time.


main_review: I found the topic and techniques employed in this paper very
interesting. While I must admit it is outside my domain of
expertise, with the exception of the submodularity discussion,
I was able to follow the exposition. Again, since this is
not my primary area, I hesitate to comment on the novelty,
I believe the contribution to be original, with the paper
having a well made related work section.

This empirical evaluation highlights how useful the sparsity is
for interpretability, and I found it much easier to parse the
synthesized reward compared to the potential based approach.
Together with a strong theoretical basis, I find this to be
good motivation for accepting this work and allowing for a
more general discussion.

# Minor Points

A minor point of feedback and a point of early confusion on my part
was the mixing of stochastic and deterministic policies, sometimes
using the same notation, i.e., on line 97 is delta* for stochastic
policies?  And on line 92, is the set of policies deterministic?

Another point I found hard to initially follow was the motivation
for the particular form of the informative criterion. In particular,
how does the choice of the function l empirically and theoretically
affect convergence.

Finally, I think to me the most interesting feature this algorithm does not have is the ability to introduce new memory (state) which may make the reward even easier to interpret and potentially more robust to domain transfer - relying less on features of the dynamics.
limitations_and_societal_impact: I believe the problem of reward design is incredibly important for safe RL, both from an engineering perspective (less numerical errors and places to introduce the reward) and a human auditability perspective.

The primary limitation of this work, as I understand, seems to be that the reward designer must have a complete understanding of the dynamics. While reasonable for some applications, in many others, it somewhat defeats the purpose RL. Nevertheless, I think this is a very important subject to study.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper introduces ExpRD, a novel optimization framework to design explicable reward functions that attempts to balance informativeness and sparsity of the reward. The proposed reward design framework is theoretically underpinned into the existing framework of PBRS and tested in two distinct environments with some success.
main_review: - The paper is well-written and easy to follow.
- The related work section is extensive and provides a good overview of related literature on methods that address reward function design. 

- I am not fully convinced that sparseness is a desirable characteristic for a reward function. I understand the reward functions are often sparse in real world environments and it is necessary to design learning algorithms that can work for them. However, the authors note sparsity as a “preferred characteristic” alongside informativeness [Line 100]. Settings highlighted to support this such as pedagogical and robotic applications [Line 35-38] might have to work with sparse rewards. However, I view this sparsity as a limitation to overcome rather than a characteristic to be desired. More discussion to support why we want sparsity would clarify the thesis of the paper.

- Results in 2a suggest that PBRS still outperforms all variants of the proposed method notwithstanding that the proposed method has more parameters that needs to be optimized. Results in 4a suggest something similar - the proposed method (one variant) outperforms PBRS only slightly. It isn’t clear whether this justifies the optimization necessary to acquire the parameters that achieves this for the proposed method while PBRS seems to work out of the box.

limitations_and_societal_impact: - The benefits of the proposed method hinges on sparsity being a preferred characteristic. I am not fully convinced of this. If the authors could clarify the case towards this, it would alleviate my primary reservation.

- Author indicates that the proposed method can be seen as a relaxation of PBRS towards (1) guaranteeing a weaker invariance property and (2) maximizing informativeness under (1) and given sparsity constraints. It is not clear to me what the redeemable benefit to this relaxation is as the empirical results do not seem to clearly indicate a marginal benefit. 

- The work does not have any discernable negative societal impacts that is obvious to me.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper tackles an important question in reward design for reinforcement learning - the trade-off between sparseness and learnability. It describes a framework to build modified rewards that are denser than the original but produce a set of optimal policies that are guaranteed to be a subset of the optimal policies induced by the original reward. The framework, ExpRD, is benchmarked on two relatively simple environments against several baselines. Experiments show improved convergence compared to the original sparse reward while being relatively sparser compared to PBRS. 
main_review: This paper tackles an important question - how can one improve the informativeness of reward functions while not degrading their interpretability. To this question, the paper implies a strong correlation between sparseness and interpretability. Thus, the paper is fundamentally about the balance between informativeness and sparseness of reward functions. The authors take inspiration from PBRS - an important work that explored the design of dense rewards from an original sparse reward while avoiding locally optimal policies that are globally suboptimal (reward bugs). The ExpRD formulation achieves sparser rewards compared to PBRS. 

Strengths:
1. The paper is grounded in theory - the authors provide detailed proofs of propositions in the appendix. 
2. The paper provides a simple concave optimization method to derive sparse-but-informative rewards.
3. Provides a simple sparsity budget parameter B that can control the trade-off between sparseness and informativeness

Weaknesses:
1. The authors make "explicability" a central premise and imply an equivalence between explainability and sparsity. Beyond a few examples of rewards that are explainable and sparse, they do not explain why this equivalence should hold generally. Thus, this paper is fundamentally about the trade-off between how sparse and how learnable a reward function is. 

2.  The paper does a mixed job of providing intuition behind the defined quantities or features. For example, the informativeness metric and its properties could have been better intuited.

3. Experiments conducted are relatively simple settings. While both environments capture the basic notion of a sparseness-informativeness trade-off, it is not clear that the performance improvements over the original sparse reward would hold for much larger state-spaces while still maintaining a comparable level of sparseness. The fundamental difference between PBRS and this method is the control over sparsity - and it is not clear to me that convergence would improve at all for small values of B when |S| is large.

Overall this is a good paper when viewed as a fundamental theoretical study of reward functions - but could be much stronger if the experimental treatment were to be more extensive. 


limitations_and_societal_impact: The authors point out that this paper is primarily a theoretical treatise on reward functions and that there are no direct negative social implications beyond risks inherent in any reward design. I would agree with the authors on this point.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes an optimization-based framework for designing reward functions that balance sparsity/interpretability with informativeness. A novel optimization framework is proposed to directly learn these new reward signals given an initial reward signal and the corresponding optimal policy set. Three optimization problems are proposed that take into consideration subgoals, as well as learning subgoals on-the-fly given a budget on their number. An informativeness criterion is proposed based on Bellman residuals for optimization from which the new reward can be recovered. An iterative algorithm is proposed for approximately solving these problems, and state abstractions are also used to scale the method to larger state spaces. Theoretical analysis is provided to ensure feasibility of the optimization objective, and a near-optimal bound is provided for the iterative algorithm under reasonable assumptions on the informativeness criterion used. Finally experiments on simple domains are used to visualize the learned rewards in terms of their interpretability and informativeness.
main_review: originality: the work is original and novel, but some existing methodologies need further comparison, see limitations below

quality: the work is technically sound, and all claims are supported by proofs

clarity: the writing is very clear and precise, and well organized. however, I think it needs to be better motivated in the introduction, e.g. to state up-front what the use-cases of the method are, where it could be applied in practice, and where it could fail. This is somewhat indicated in the related work section, but I also feel could be elaborated on in the motivation. the assumptions of requiring the optimal policy set on the task seems to exclude a large number of use cases, which is important to discuss early on.

significance: the work is quite significant as reward design, sparsity and interpretability are all important topics currently studied in RL. it is not fully clear that the method is "better" than other methods, since not many have been discussed (see limitations below). the experiments only seem to consider simple baselines which does not answer this matter. 
limitations_and_societal_impact: ========  strengths  =========

1. Intelligent reward design is an important problem in the reinforcement learning community. The connection between sparsity and explainability is quite interesting and novel, and to my knowledge has not been studied in a mathematically coherent framework in the past. The paper is also very clearly written and the mathematics is precise. 

2. The problem is cast as a problem in concave/convex optimization. This makes it possible to incorporate a variety of information into the objective function (e.g. subgoals or landmarks, other rewards, etc) and constrain the learned rewards appropriately. Theoretical results are provided that analyze the optimization objectives, proving feasibility. Furthermore, a greedy algorithm (Algorithm 1) is provided that iteratively solves these optimization problems near-optimally with a precise gap (Theorem 1). 

3. The method, while inherently computationally challenging to solve in large MDPs, can be cast using state abstraction to reduce the dimensionality, and apply the proposed methods to this transformed MDP. The experiments, while toy in nature, demonstrate how the method works in discrete and a continuous environment. The visualization and interpretation of the learned behaviors is very well illustrated for these domains. 

======== limitations ========

1. It is not immediately clear that sparseness of the reward function is the deciding criterion for interpretability. On the contrary, I believe it is not difficult to derive reward functions that are both dense and interpretable. For instance, "survivability" of the agent can be best modeled by assigning a (constant) positive reward on each transition, as seen in the classical cart-pole domain. In many robotics/nagivation problems, we could design a reward function that awards the agent based on how close the agent is to a pre-determined goal state. Finally, in many OR-related real-world problems, the reward is often best described in terms of revenues, e.g. for inventory control how many items are sold in a period. While I agree with you that sparsity can be useful for some toy domains, is it reasonable to expect similar notions on the type of problems above?

2. While the technical analysis of the method is very strong, a weaker point is the assumptions needed to realize the proposed methods. In lines 97-100, it is stated "learning an optimal policy induced by the sparse reward R-bar is challenging due to high sample complexity". The next lines mention that "... given R-bar and the corresponding optimal policy set". In some sense, it is difficult to see how these assumptions can be realized in practice on non-trivial domains, since learning this policy set is at least (if not more) challenging than learning even a single optimal policy with R-bar. 

3. In light of point 2, I have to wonder if the initial motivation and assumptions, and experimental design could be tailored to solve a slightly different problem to the one initially proposed in the introduction, making the motivation of the paper much stronger. Namely, suppose we have solved a source task and obtained both an R-bar (learned from the source reward data) and a set of optimal policies. This knowledge can then be used to initialize the algorithm on a target environment in which the dynamics are different, but the goals remain the same. Since reward invariance - a key property the ExpRD method is designed to satisfy -- is required in this setup, does it mean it can be applied directly to landmark/subgoal discovery and transfer? If not, what could be changed in the methodology to allow it to work under change of dynamics?

======== other questions ========

1. Conditions (C1) and (C2) essentially require that the true Q-values are known. How can this condition be satisfied when they are estimated, up to some error say epsilon? 

2. The current methodology seems quite reminiscent of the reward shaping literature in which arbitrary reward functions (in this case R-bar) can be converted to potential functions for PBRS (see, e.g. [1]). It seems as though subgoals can be encoded in a reward with "bugs", but then that method can be used to guarantee invariance, by learning a secondary value function on this subgoal-driven advice. This method has the advantage of being scalable to large or continuous spaces, and requiring little knowledge besides learning the secondary values on data. Given how similar the problem setting tackled by these two methods, can you compare them conceptually, if not experimentally? Does that method have limitations with regard to sparsity, or can sparsity be enforced in learning values by using state abstractions, sparse codings, etc?

3. Theorem 1 provides a gap between the optimal objective value and the greedy one. Is it possible to understand how "good" this gap is? Is it the best bound possible under the given assumptions? 

[1] Harutyunyan, Anna, et al. "Expressing arbitrary reward functions as potential-based advice." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 29. No. 1. 2015.
review_title: null

Meta-review: The reviewers agree that the problem of reward design is important and particularly relevant for safe reinforcement learning (RL). It is also a timely subject now that the deployment of RL systems in the real world is becoming increasingly more common. There was also a consensus among the reviewers that the proposed approach is technically sound. 

Based on the submission, the reviews, the rebuttal and the subsequent discussions, we strongly advise the authors to make two modifications to the paper. 

First, the placement of the proposed approach should be much more clear and stated at the outset. Some passages of the text suggest that the motivation underlying the proposed method is to find a reward to replace the original, sparse, reward in order to solve a specific task. 

The connections made with Ng et al.'s PBRS and variants are one example. One of the requirements of the proposed approach is that one has access to (an approximation of) the optimal value function $\bar{V}^*$. One of the reviewers called attention to this fact and asked how realistic this is in practice, to which the authors responded that "similar to PBRS with $\bar{V}^*$ as the potential function, our framework does require solving the task w.r.t. the original reward function $\bar{R}$".

Although it is true that $\bar{V}^*$  can be used to derive PBRS' potential function, and Ng et al. point out that this choice gives rise to a particularly easy problem, their result apply to *any* potential function derived from a function $\Phi$ define over states (see Theorem 1 in Ng et al. 1999). In fact, Ng et al. emphasize that their method does *not* depend on $\bar{V}^*$, and also illustrate this point in their experiments by handcrafting a $\Phi$ that is intuitive but considerably different from $\bar{V}^*$. 

PBRS and variants aim at finding a reward $\hat{R}$ to replace the original, potentially sparse, reward $\bar{R}$ in order to solve a specific task. If we view the proposed approach as an alternative to these methods, the fact that it needs $\bar{V}^*$ is a strong limitation. 

An alternative view is that we *can* solve the task $\bar{R}$ but want a different version of it, $\hat{R}$, to be used in the future when we solve the task again. This new version of the reward, $\hat{R}$, should have two desirable properties: it should be informative and interpretable. Under this view, the fact that we need $\bar{V}^*$ seems to be less of an issue. Although this interpretation of the proposed approach seems to be favored in parts of the paper, it should be more clearly stated, and any passages that suggest otherwise should be modified to avoid ambiguities. 

A second modification to the paper we strongly suggest regards the use of sparsity as a proxy for interpretability. This concern came up in most of the reviews and was a point of contention in the discussions. We advise the authors to add the good points made during the discussion to the paper. Specifically, they should clarify why sparsity is a good measure of interpretability and explain how the proposed approach can be modified to accommodate other reward structures. They should also add the provided list with examples of applications where sparsity structure in the reward design is important. 

We hope the provided feedback will be helpful in making your paper even stronger.

Decision: Accept (Poster)