Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper introduces a new algorithm to solve the sparse reward settings. The algorithm tries to find an optimal policy by leveraging two learners: a controller and a shaper. The controller learns to maximize the environment reward signal plus the signal provided by the shaper. The shaper learns a potential-based reward shaping function by maximizing the controller's objective plus a cost penalty for providing reward feedback and an exploration bonus. The shapers reward function is created using a randomly generated state function and a dot product based on the shaper's "action." Some theoretical analysis is provided along with experiments demonstrate to demonstrate that this algorithm is helping solve sparse reward problems. 

main_review: This paper aims to tackle an important problem in RL and does a good job of conducting some experiments to show what the method learns. However, there are some significant concerns with the paper. The first is a lack of clarity in the presentation of the method and problem setup. The second is that it is unclear where or if any benefit is coming from the proposed method. The issues are expanded below. 



Clarity: 
The paper’s clarity can be improved by being more precise in writing and avoiding redundant arguments. 

The first thing to fix is to make sure every term and symbol has a definition before it is used. In section, when an expression for F is given, phi is used, but it is unclear what phi is required to be. This creates confusion later Section 3 third paragraph, where F hat uses some phi hat, and \theta^\star is supposed to make \hat \phi equal to \phi. \theta^\star is often used to indicate optimal weights, but it is not clear what optimal is because phi is undefined. It is said that \theta^* is supposed to yield a useful shaping reward, but it is unclear what that means. Without proper definitions, it is not easy to understand the proper motivation and reason about whether the method accomplishes the stated goals. 

There are also many redundant arguments made throughout the paper. For example, at the start of the third paragraph in Section 3, an argument is given that was discussed several times above. 


At the start of Section 4, further discussion is given about the goal/objective for each learner, but they are both not provided until later. This lack of specificity is frustrating as a reader because all statements given so far have been vague and the exact relationship of the two algorithms continues to go misunderstood. Also, for both objective functions, it is specified that each learner needs to maximize a value function at some given state, but this is not a proper objective function because a distribution or weighting over states is not given. 

Method benefits:
The stated objective is to tackle the problem of sparse and uninformative rewards through autonomously learning a reward function. Additionally, it is said that the “…shaping rewards supplement the environment reward and promote effective learning, our framework therefore addresses the key challenges in RS”. One issue with this claim is that learning of the shaping rewards cannot be more efficient than just learning about the reward function of the environment, i.e., what makes a good reward function can only be learned once the agent has already learned what the good behavior is. Thus, it seems unlikely that this method could be doing anything more effective than encouraging exploration. This brings up another issue, in that it is unclear what components of the method are necessary or helpful in solving sparse reward problems. The experiments demonstrate some learned behavior, but they do not clearly show how each component helps the algorithm change the learning dynamics, so sparse reward problems are manageable. These experiments are an essential step in proposing new methods so other researchers can build off the knowledge generated in a paper to solve new and different problems. 

summary_of_the_review: This paper lacks proper justification for the design choices of the presented method and is thus not ready for acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The key idea in this paper is to jointly train a pair of agents, namely a Controller that performs the RL task and a Shaper agent that shapes the Controller's reward function to better its performance. Rather than shape all states, Shaper learns "switching controls" to determine states on which to place its modeling effort on, and ablation experiments suggest this works well compared to the straightforward approach of shaping all states. A natural concern is whether this Markov game approach results in stable training and convergence. To address this issue, the authors provide theoretical convergence results which show ROSA convergences to a Nash Equilibrium (NE) with weakly higher total return. Experiments on several domains suggest the method works well relative to alternative reward shaping approaches (e.g., those based on curiosity or bi-level optimization). 
main_review: The idea of jointly training an agent to assist the controller is relevant to the RL community and new (to my knowledge). In my mind, the primary insight is to connect reward shaping to Markov games. The theoretical results built off [25] appear to support the methodology and experiments suggest ROSA works well and is robust (up to the points below). I appreciate that the authors attempted to show the method performs well in various task contexts, e.g., for subgoal discovery. 

On the downside, there are several aspects of the work which are unclear to me and several claims are not well established by the theory nor the experiments:

- the paper claims that ROSA's concurrent learning leads to "a faster, more efficient procedure" compared to [15,34]. Can the authors provide additional theoretical or experimental justification for this claim? 
- Sec 4.1. on the switching controls can be better explained; I don't understand the definition for the switch being $I_{\tau_{k+1}} = 1 - I_{\tau_k}$; the switch is flipped after each step? This seems at odds with the later explanations about the switching behavior. Looking at the main events, the switch is decided upon at each step?  
- Sec 4.2. The role of the bonus reward L remains rather opaque to me. Perhaps I missed it but I didn't see any experiments studying its effect. Perhaps the authors can clarify?
- Sec 5. It is unclear what $v_1^{\pi, \pi^2}$ means. In Sec. 4, it is defined as the objective for controller, incorporating both the extrinsic and intrinsic rewards. However, in Proposition 3, it appears to denote extrinsic expected return. Likewise, the corresponding proof (Proof 7) doesn’t explicitly write out $v_1^{\pi, \pi^2}$. 
- Sec 6. Key details on the experimental settings are missing, especially the number of runs. It is well-known that RL performance can vary significantly between random initializations. How does the incorporation of Shaper affect this variance? I appreciate space is tight so perhaps this can be put in the supplementary. 
- Sec 3. "Red-herrings"; I'm puzzled as to how Shaper learns to do this since there is a bonus for exploration (L). The mechanism by which the exploration/exploitation trade-off is resolved is not apparent to me from reading the paper. 

## Minor comments 
- Sec 4: "RIGA" should be "ROSA"
- Sec 5: "The result is established by a careful adaptation of the policy invariance result in [25] ...." is repeated after Corollary 1. 

summary_of_the_review: The paper makes interesting contributions, but the clarity could be improved. At this point, my score is a reflection of my uncertainty about the above issues.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors propose ROSA, a reward shaping method that trains a separate “Shaper” policy to learn how to generate reward bonuses. The problem is formulated as a two-player Markov game, in which the environment dynamics are only affected by the primary, “Controller” policy, but the Shaper and Controller policies each optimize their own rewards. The Controller’s reward is the normal reward plus a potential-based reward that depends on the previous two states and the previous two Shaper actions. The shapers’ reward is a combination of the Controller’s reward, a penalty for switching often, and a count-based exploration bonus. The shaper’s rewards are also automatically gated by a switching function, which is hard-coded to switch with higher probability whenever a curiosity-metric increases (in this case using the RND exploration metric). The authors extend the standard reward shaping result to show that including the actions of the Shaper in the potential-based reward shaping term maintains policy invariance. Then, the authors empirically demonstrate on a grid-world environment that ROSA provides useful reward shaping that guides the agent towards the goal and ignores irrelevant parts of the state space. The authors also compare to and find that ROSA outperforms ICM, RND, PPO, and LIRPG on Gravitar, and gets similar performance on Solaris and Super Mario as some of these prior works.
main_review: # Strengths

This paper proposes an interesting and (as far as I know) novel approach to learning how to shape rewards. The idea of training an agent to output actions that modulate a potential-based reward is quite interesting, since this Shaper agent can use heuristic metrics (e.g. the RND bonus) to guide exploration while preserving the Controller agent’s final performance thanks to the extended policy invariance results. As the paper notes, this multi-agent approach could lead to interesting new solutions for RL. The experiments in the paper compare against appropriate baselines and demonstrate promising results. The visualizations are useful, and overall the paper is easy to follow.

# Weaknesses

One concern with the paper is that it is the combination of many heuristic components (e.g. how L is chosen, how c is chosen, how I is chosen, and how phi is chosen). This runs a bit counter to the author’s motivation to avoid manually engineering components. I understand that part of the paper is demonstrating that despite these heuristics, the Controller policy is still optimizing the correct objective, but these additional design choices may result in a method that is overall rather brittle and sensitive to the design choices, even if the Controller is *theoretically* optimizing the right objective. Demonstrating that the method still performs well when L, c, I, and/or phi is altered would provide evidence for the generality of this approach.

The other main weaknesses of the paper come in the writing and experiments, which I detail below.

## Writing:
One major concern is that the main paper does not describe how phi is chosen. This decision is critical to the success of the paper, and I could not find much in the paper other than a hypothetical description (“φ can be, for example, a neural network with fixed weights with input (s, a2)”).

The authors claim that there are two advantages over past work: (1) learning the reward shaping term concurrently as opposed to iteratively and (2) avoiding the computational cost of computing the reward at every state. The second concern seems rather minor. For the first claim, the authors do not provide evidence that, “ROSA performs these operations concurrently leading to a faster, more efficient procedure.” It would help to evaluate these methods as a comparison. Without this comparison, the difference between updating the other networks concurrently vs iteratively seems superficial (e.g., can’t you just run the prior methods with a faster iteration loop)?

There are also other claims that seem unsubstantiated. For example:

“it ensures that the information-gain from Shaper encouraging Controller to explore a given set of states is sufficiently high to merit activating the stream of rewards”
Is there evidence or proof of information being maximized by the Shaper?

“Controller’s rewards only at states that are important for guiding Controller to its optimal policy.
This enables Shaper to quickly determine its policy π2 and how to choose the values of F unlike Controller whose policy must learned for all states”
Why does this enable the Shaper to quickly determine its policy? Is there evidence of this?


## Experiments
One limitation of the experiments is that the method is only applied to a relatively easy robot environment and a limited number of video game domains. In particular, on Solaris and Super Mario, most of the learning happens within the first few time steps, suggesting that exploration is not a big challenge in these domains. Although the authors do demonstrate that the other methods have some instability issues, it would be great to test the environment on more domains where the bottleneck is clearly exploration.

It would be great to compare to [3,4] since, as the authors say, these are “closest to our work”. Although I understand that [3] requires a shaping reward to begin with, ROSA also assumes access to a bonus (through L(s)), and so comparing to [3] with the same RND bonus seems like a fair comparison.


## Minor comments

The statement “Unlike [15] which requires a useful shaping reward to begin with” seems unfair since the whole point of [15] is that you can learn when to ignore a non-useful shaping reward.

“ Moreover, in [15,34], the agent’s policy and shaping rewards are learned with consecutive updates. In contrast, ROSA performs these operations concurrently leading to a faster, more efficient procedure.”
As written, the difference sounds rather superficial because it’s relatively simple to run [15, 34] concurrently. Do the authors mean to highlight the difference between a bi-level optimization and having a separate Shaper policy that can generate on-the-fly actions?

In Figure 1, why does your method start off better at steps=0 than RND and count-Based ICM? Shouldn’t they start at the same performance?
Could the authors report normalized returns, which I believe is more standard for Atari?

“Another issue is that using an optimisation procedure to find θ directly does not make use of information generated by intermediate state-action-reward tuples of the RL problem which can help to guide the optimisation”
I’m not sure what problem is being highlighted here. Are you saying that trying to optimzie theta without using any samples is a bad idea? While I agree, it’s unclear why anyone would do this.

“Now the problem is to find θ...such that F(st+1, st) = \hat F(st+1, st; θ)”
What is F? Is it just any “useful shaping-reward function F” or is it a specific F?

“these methods provide no performance guarantees nor do they ensure the optimal policy (of the underlying MDP) is preserved”
Some curiosity-based reward shaping methods provide guarantees (though “curiosity” is a bit ambiguous of a category). See [1,2] 


## typos/low-level:
- during training. [16].
- Moreover, they naively reward exploration to unvisited states without consideration of the environment reward
- when Shaper influences Controller) 
- Figure legends and axes labels are very small and hard to read
[1] Hazan, Elad, et al. "Provably efficient maximum entropy exploration." International Conference on Machine Learning. PMLR, 2019.
[2] Misra, Dipendra, et al. "Kinematic state abstraction and provably efficient rich-observation reinforcement learning." International conference on machine learning. PMLR, 2020.
[3]  Yujing Hu et al. “Learning to Utilize Shaping Rewards: A New Approach of Reward Shaping”. In: Advances in Neural Information Processing Systems 33 (2020).
[4] Bradly Stadie, Lunjun Zhang, and Jimmy Ba. “Learning Intrinsic Rewards as a Bi-Level
Optimization Problem”. In: Conference on Uncertainty in Artificial Intelligence. PMLR. 2020,
pp. 111–120.
summary_of_the_review: The paper presents an interesting idea and has some promising results. However, there are a number of clarity issues (including lack of details on an important design), claims that seem unsupported, and limitations in the experiment (in particular, not comparing to certain baselines and evaluating on tasks that may not be challenging enough) that make me currently believe that the paper is not ready.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes to frame the reward shaping method as a Markov game between two players. In this setting the first player is learning to act in the environment while the second player is learning to provide reward shaping to the first player. Additionally, the authors propose to use a switching scheme that indicates whether or not to perform reward shaping for the first player. The authors provide some theoretical guarantees under a large set of assumptions. The authors perform experiments on a set of toy tasks and a few more complex domains.
main_review: Strengths
------------
-Framing reward shaping within the Markov game (MG) framework is novel

-Some theoretical guarantees are provided, in particular Proposition 1

Weaknesses
------------------
-The presentation and clarity of the paper is lacking

-Many low level choices are brushed upon and hardly motivated

-Empirical improvements are quite limited and the code is not provided


Details
---------
Presenting a solution to the potential function in PBRS is an important contribution as it is still to this day an open problem. Moreover, most of the research on PBRS has not used neural networks and therefore can be seen as limited. As such, framing the method as a Markov game is an interesting avenue. That being said, the paper does a poor job at presenting clearly the ideas, motivations, limitations as well as some related work. For example, the idea of introducing switching controls can by itself be an interesting idea, but is completely orthogonal to framing the method as a two player MG. Yet the method that the authors present ties the two concepts together. Around the idea of switching is the claim that since the method only learns to shape rewards at relevant states, it is more computational efficient. First, is the proposed method, in practice, really learning what are the relevant states? Second, wouldn't be the computational cost be equivalent if one first has to learn on what states to perform reward shaping? I would argue that the computational cost even greater since both elements need to work together (reward shaping and switching controls), unless a more trivial solution is proposed, as in the paper. Given these considerations, I would be much more careful about the kind of claims being made.

The idea of two player MG can be an interesting avenue, but I am wondering if the fact that only the Controller affects the dynamics, is it really relevant to talk a two player game? In the end, the Controller is a network that is simply using reward shaping, while the Shaper is separate network that learns how to shape the rewards. What does framing the setup as a two player game bring in terms of insights/methods/solutions? This kind of questions is not really addressed in the paper.

The presentation of the method has a structure that doesn't help clarity where many of the details are only later presented and are not really motivated. The presentation itself is interleaved with claims that hinders clarity and bring more questions, such as first paragraph of 4.2 where claims about the effect of the switching cost are made. The idea of termination times is presented quickly but most of the details are in the appendix, which again hinders a nice and clean presentation. The final algorithm makes choices such as adding an exploration bonus to the Shaper or using a fixed network f(s) for the potential function. Especially with respect to the latter point, why would it make any sense to have a random network output the value for reward shaping? The algorithm also mentions that $a^2_{\tau_k} =0 \forall k$, but then it also mentions that when $g(s_t)=1$ we sample from the Shaper's policy? Why are such choices being made? Is it to make sure that the theoretical derivation work out, such as in Proposition 1? How does it help in practice? 

Finally, related work is missing.The paper claims that "In RS the question of which φ to insert has not been addressed." This is simply false. There is recent and relevant work on this such as (Klissarov et al. 2020), as well as more classic work such as (Brys et al., 2015, Grzes and Kudenko 2010). These references should be included in the paper given their close conenction and the claims adjusted. Moreover, there is many landmark papers on curiosity that are missing, such as  (Schmidhuber 2010,  Oudeyer et al. 2007)

J. Schmidhuber. Formal theory of creativity, fun, and intrinsic motivation (1990–2010)

Brys et al. 2015, Reinforcement learning from demonstration through shaping

Grzes and Kudenko 2010,  Online learning of shaping rewards in reinforcement learning

Klissarov et al. 2020, Reward propagation using graph convolutional networks

Oudeyer et al. 2007, What is intrinsic motivation? A typology of computational approaches


summary_of_the_review: The paper proposes an original way to frame reward shaping. However, the presentation is lacking clarity and many of the choices/details are not well motivated. Despite my negative review I think there is potential in the approach, but I believe that a major rewriting is necessary as well as more qualitative empirical analysis. The quantitive empirical results are not especially favourable either.
review_title: null

Meta-review: This paper tackled the reward shaping problem under the framework of Markov games. The authors proposed reward shaping algorithms for RL with mild theoretical guarantees. The AC agrees with the reviewers that the empirical performance is ambiguous. The paper should be substantially improved before being accepted.
Decision: Reject