Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Learning near-optimal policies in sparse reward environments with large state space is challenging. In theoretical reinforcement learning (RL) literature, it has been understood that directed (optimistic) exploration strategies (provably) improve sample complexity over random exploration techniques. However, in practice, people use heuristic-based (exploiting domain knowledge) reward shaping to demonstrate successful results. This paper conducts a formal theoretical investigation on the impact of such reward shaping methods on the sample complexity of RL algorithms. In particular, the authors propose two simple modifications to the well-known UCBVI algorithm and show how these changes lead to tight regret bounds. In the experiments, they studied: 
- the importance of the two modifications that they introduced, 
- the type of environments where the utility of reward shaping can be realized, and 
- the impact of the quality of the shaping function on the sample complexity. 
strengths_and_weaknesses: **Post Rebuttal:** I thank the authors for the detailed response that addresses most of my concerns. I hope that the authors can incorporate the details in the rebuttal in the updated version of their draft. I have updated my score accordingly. 

----

Strengths:

Despite the practical success of reward shaping (exploiting domain knowledge), theoretical understanding (specifically in sample complexity) is still lacking in the literature. Thus, the formal investigation of this paper is an important step in this direction. The proposed changes to the UCBVI algorithm are theoretically motivated, novel, and easy to implement. 

The related work is clearly discussed in Section 2, and the current work is clearly positioned in the literature.

****

I have checked the theoretical claims in the main paper but haven't checked the proofs (or verified the correctness) in the appendix. However, the theoretical claims seem to match with the intuition. The authors have explained the role of reward shaping in pruning the unnecessary part of the state space in the theoretical section. 

Since the paper is theoretical, the conducted experiments are sufficient/reasonable enough to flesh out the essential characteristics of reward shaping (or to validate the paper's central claims).

****

Weaknesses:

For most of the part, the paper is well written; the motivation and the story are well conveyed. However, the writing of the theoretical section can be improved, and some intuitive examples would also help non-theoretical readers. 

Also, see the questions below. 
questions: Questions:

1/ I couldn't fully understand Assumption 3; please explain with an example and point me where it is used in your analysis. 

2/ I have noticed several inconsistencies in the theoretical section, for example:
- In Eq.(1), $N_h^t$ is already defined, but $N_t$ is not. 
- Does $\widehat{P}_t$ depend on $h$? In line 168, it is defined based on $N_h^t$ not $N_t$. 
- $\widetilde{V}$ is a function of $\mathcal{S}$ only not a function of $\mathcal{S} \times \mathcal{A}$, right? In Assumption 1, line 174, and Algorithm 2, $\widetilde{V}(s,a)$ is used. 

Please fix them. 

3/ The PseudoSub and PathPseudoSub sets introduced in Section 5.1 are clearly explained. However, illustrating these notions for some specific environments (e.g., deterministic chain MDP) would help the reader understand the tightness/improvement of the regret bound presented in Theorem 5.2. 

4/ Regarding section 6.2, it would be interesting to consider a formal investigation on the type of environments where the reward shaping function improves/hurts the learning process. See Section 5 of [Dann et al. 2022]. 

5/ Regarding section 6.3, how does your work theoretically/empirically relate to [Cheng et al. 2021], who also investigate the quality of shaping functions in improving the sample complexity. 

References:

[Dann et al. 2022] Dann et al. Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximation. ICML, 2022. 

[Cheng et al. 2021] Cheng et al. Heuristic-Guided Reinforcement Learning. NeurIPS, 2021. 


limitations: Their proposed method does not seem to cause any direct potential negative societal impacts.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper attempts to shed light on reward shaping (RS) in reinforcement learning (RL) from a theoretical perspective. The authors contend -- correctly, in my opinion -- that the majority of work in RS has focused on RS from a practical point-of-view, while there is relatively less work developing theoretical characterizations of it. 

The authors ask the question *"Can we theoretically justify the sample complexity benefits that reward shaping from prior domain knowledge can provide reinforcement learning?"*. In seeking an answer to this question, the authors make some assumptions (e.g., bounds on $\tilde{V}$) and propose a specific algorithm, UCBVI-shaped, which is amenable to analysis. 

Given the set-up describe in the preceding paragraph, the contributions of this paper are:
1. A new algorithm that incorporates the RS method of the paper called UCBVI-shaped
2. A theoretical upper-bound on the regret of this method showing lower regret compared to vanilla UCBVI (along with some mathematical tooling, e.g., pseudosuboptimal states)
3. Empirical analysis of the proposed method showing its strengths and weakesses.

In short, the paper puts forth a question and then quite thoroughly studies it. The end result is an affirmation in the sense that the authors are able to derive a bound on regret when they enhance an algorithm (UCBVI) to use their specific instantiation of RS.
strengths_and_weaknesses: *Strengths*
1. In terms of quality and scientific soundness, this paper is difficult to fault. The object of inquiry is clearly stated, as are the assumptions made of the investigation into it. A theoretically justified answer to the question is derived, and the paper goes even further by analysing the strengths and weaknesses of the method upon which their theoretical results are based.
2. Moreover, in terms of originality, the paper deserves merit. I can only think of one other work which attempts to develop some theoretical results about RS (which is cited -- Ng et al., 1999).
3. Modulo one major complaint and a few minor issues (described below), the paper is also eminently readable and clear. I rarely found myself repeatedly re-reading anything to try to deduce what was being said.

*Weaknesses*
1. My central issue with the paper is its significance. By this I mean that the assumption of the type of shaped reward function -- $\tilde{V} \leq V^* \leq \beta \tilde{V} $ -- limits the impact and applicability of the results of the paper. It is a significant assumption. In fact, I would argue that it's almost expected that given such a form for the RS that there would be benefits to sample complexity. I know your assumption is looser than this, but the following is just to explain  why I made the last statement. Suppose we have access to the $V^*$. We can essentially just set the values of the $V$ we are learning to the intrinsic rewards generated by $V^*$, and this will almost certainly benefit sample complexity.  While I do appreciate that some simplifying assumptions are required, I think this really limits the scope and impact of this paper. With that said, it's interesting to see how sample complexity is affected by pseudosuboptimal states and so on.
Note: I may have misunderstood/missed something here, in which case I urge the authors to clarify.

2. Further to the point above, I'm also a little unconvinced about the characterization of what kind of problems RS helps. The intuition about dubious paths makes sense in grid-worlds, but I don't see exactly how this intuition generalizes to general RL problems.

*Minor Issues*
Furthermore, below is a list of minor textual errors I was able to catch.
 
* Figure 1 - Very nice, but what do the colours mean?
* Figure 5 appears before Figure 4 in the text. This was a bit confusing for a moment.
* Assumption 3 - What's $[H]$? I don't think this is defined?
* Theorem 3.1/Lemma 5.1 - What's $\delta$? Not sure if I missed something but as far as I can tell it is not defined.

* L3 "...choice of reward function..." - I found this a bit misleading as normally in RL we just accept the reward function that comes with the environment.
* L47 "...tabula-rasa RL" - I don't know what tabula-rasa means
* L47  "...better direct. exploration..." - typo
* L73 "...aim to learning..." - should it be "learn"
* L111 "...high probability having..." - should it be "has"
* L108-117 - very long run-on sentence was quite confusing to parse
* L183 - "bonus_2"? 
* L 296 - "As shown in Fig 5., we see that for environments with open paths..." - But Fig. 5 doesn't show Gridworld (which is the env I assume has open paths)

I am open to reconsidering my evaluation if the authors can convince me of the broader applicability of their results in this paper.

[1] - A. Y. Ng, D. Harada, and S. Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In ICML, volume 99, pages 278–287, 1999.
questions: *Suggestions for Improvement*
1. One of my main issues while reading this paper was that the UCBVI algorithm was not described. As a result, some of the points of the text were lost on me as I list below.
* L63 refers to some $H$. I'm not sure where this came from as it isn't previously defined, and so I can only assume it has something to do with UCBVI.
* Moreover, some of the argument in Section 5 compares the regret of UCBVI and UCBVI-shaped. It's difficult to understand this as UCBVI isn't discussed.

2. How does UCBVI-shaped fare if we corrupt $\tilde{V}$? I'm quite curious about this experiment.

3. I'd have been interested in seeing some experiments where UCBVI-shaped uses RND as a method to compute "pesudo-counts"?

4. Figure 4e - Why is there that one state with really high visitations?

5. Figure 3e - What happened to UCBVI-shaped? Some explanation of this peculiar degradation would be helpful

6. L100 "...H is the problem horizon..." - Is H fixed? Can you clarify exactly what H means?

7. Number of seeds used in the experiments is not mentioned?
limitations: N/A
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper investigates the regret analysis of a particular form of reward shaping where the shaping function is an approximation of the optimal state value function. This reward shaping is integrated into an extension of the UCBVI algorithm to obtain UCBVI-Shaped. Experiments show benefits of this approach by enabling the elimination of potentially large subsets of the state space by ignoring regions where the value is low during exploration.
strengths_and_weaknesses: Strengths
* The proposed algorithm has good sample complexity and a detailed regret analysis

Weaknesses
* It seems like a strong assumption is being made whereby the shaping signal is an approximation of the optimal value function. 
questions: 1. Can you justify the assumption that the reward shaping function is an approximation of the optimal state value function? How strong of an approximation does it need to be? If there is a close enough approximation, this trivializes the problem.
2. Why do you choose the bonus term to be the empirical second moment of \tilde{V}?

Minor comments:
* "has focused smarter" -> has focused on smarter
* In Algorithm 2, line 5: should the k superscript be a t? Should \tilde{V} have a subscript of h?
* "\beta . ."
* "\beta = \{1.5, 1.9\}" -> \beta \in \{1.5, 1.5\}


limitations: The authors state that Section 7 covers the limitations of their work. It does not seem to. But, elsewhere, it is stated that for some experiments (like the single corridor example), the reward shaping may not be very informative and something like an optimistic shaping function can yield better results.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: Reward shaping is used to speed up reinforcement learning, i.e., it is expected to make exploration more focused and to allow the algorithm to find the optimal policy without the need to explore the entire state space. This means that reward shaping is expected to reduce regret. This is exactly what the authors of this paper study within the family of UCB algorithms. These algorithms use an exploration bonus, which can be seen as a shaping reward. The authors assume that some background knowledge is available. This knowledge can be used to design an informative exploration bonus. This assumption is absolutely correct since this is a common requirement in research on reward shaping, e.g., potential-based reward shaping requires the potential function that can be seen as a very similar assumption. Though I have to admit that the multiplicative bounding of the current paper is a bit strong an assumption, but I think that the contribution is still excellent. The theoretical investigation in this paper is relevant and timely. Having some insights into the impact of reward shaping on regret is very useful, and it is remarkable that the authors managed to get rid of the impact of the horizon H. The two uses of shaping information presented in this paper lead to an interesting algorithm. Empirical evaluation on three domains is also provided, and the experiments confirm the merit of the contribution.
strengths_and_weaknesses: The paper addresses a very relevant and useful question, and it provides a convincing and competent answer.

This is something that can be fixed easily, but the paragraph entitled "Practical Reward Design and Reward Shaping" is a bit unclear because the authors seem to be unaware of one topic in the related literature. The authors indicate that the potential-reward shaping methods try to cover all states and the shaping reward is unknown. This is not entirely true because the literature on potential-based reward shaping has good insights into that, and optimism is also studied and required. For an excellent treatment of this issue, the authors could check [1]. I feel that the current discussion in lines 87-96 is a bit misleading because [1] shows that potential-based reward shaping is a principled method too, the right bias is known (i.e., we know which information is required), and the number of explored states can be reduced (even in the Rmax type of algorithms). As I said above, this is a minor comment, but I hope that the authors could address it in this paragraph.
questions: Initially I wanted to ask how V was determined, but this was clarified in the appendix. I don't have any specific questions.

This paper studies the impact of reward shaping on regret, and it generated insightful results. I feel that it would be interesting if, either the authors of this paper or someone else with similar skills, analysed  the impact of policy or representation transfer [2] or other tweaks with an assumption of optimism [3] that make the exploration more focused. This is of course beyond the scope of this paper, but it would beneficial for the community if this was explored in the future.

[1] Asmuth, John, Michael L. Littman, and Robert Zinkov. "Potential-based Shaping in Model-based Reinforcement Learning." AAAI. 2008.
[2] Taylor, Matthew E., and Peter Stone. "Representation Transfer for Reinforcement Learning." AAAI Fall Symposium: Computational Approaches to Representation Change during Learning and Development. 2007.
[3] Grzes, Marek, and Daniel Kudenko. "PAC-MDP learning with knowledge-based admissible models." Proc. of AAMAS. (2010): 349-358.

Fonts in Figures 3, 5, 6 are too small.

The paper reads well, and I did not see technical problems, but I have to admit that I only scanned the proofs in the appendix. I would probably need to spend a week or more if I wanted to trace all the steps in the proofs.
limitations: I am not sure if there is anything to say here.
review_title: null

Meta-review: metareview: The reviewers carefully analyzed this work and agreed that the topics investigated in this paper are important and relevant to the field. Overall, the reviewers had a generally positive impression of this paper. One reviewer argued that this paper addresses a relevant and valuable question and makes an important step towards a better understanding of regret when reward shaping is used. Even though this paper makes assumptions that were of some concern to other reviewers, this reviewer argued that the paper is nonetheless an important milestone for the community. Another reviewer acknowledged that this paper conducted a formal theoretical investigation of the impact of reward shaping methods on the sample complexity of RL algorithms and argued that all proofs seem to be sound. This reviewer had a few technical questions, which were all addressed by the authors. Post-rebuttal, the reviewer encouraged the authors to incorporate the corresponding details (such as those discussed in the rebuttal) in the updated version of their draft. A third reviewer emphasized that this paper shed light on reward shaping from a theoretical perspective. They argued that the quality and scientific soundness of the paper are objectively excellent, that the paper is original, and that it deserves merit. The reviewer pointed out one main weakness, however, regarding the assumption of the type of the shaped reward function. They wondered whether this assumption could limit the impact and applicability of the paper's results. After reading the authors' thorough rebuttal, however, the reviewer stated that they were satisfied with all responses and updated their score accordingly. Finally, a fourth reviewer also had an overall positive view of this work but pointed out, as a weakness, the seemingly strong assumption that the shaping signal is an approximation of the optimal value function. After reading the authors' response, however, the reviewer stated that the assumptions made in this paper were not as restrictive as they initially thought, and updated their score. Overall, thus, it seems like most reviewers were positively impressed with the quality of this work. They look forward to an updated paper version addressing the suggestions mentioned in their reviews and during the discussion phase.
confidence: Certain
Decision: Accept