Action-Dependent Optimality-Preserving Reward Shaping
Authors: Grant Collier Forbes
Jianxun Wang
Leonardo Villalobos-Arias
Arnav Jhala
David Roberts
Venue: ICML 2025 poster (2025)
Keywords: Reinforcement learning
reward shaping
intrinsic motivation
potential-based reward shaping
exploration
Primary area: reinforcement_learning
TL;DR: Previous methods for adapting shaping rewards/intrinsic motivation to prevent reward hacking don't scale well to complex environments; we invented one that does.

Abstract: Recent RL research has utilized reward shaping--particularly complex shaping rewards such as intrinsic motivation (IM)--to encourage agent exploration in sparse-reward environments. While often effective, ``reward hacking'' can lead to the shaping reward being optimized at the expense of the extrinsic reward, resulting in a suboptimal policy. Potential-Based Reward Shaping (PBRS) techniques such as Generalized Reward Matching (GRM) and Policy-Invariant Explicit Shaping (PIES) have mitigated this. These methods allow for implementing IM without altering optimal policies. In this work we show that they are effectively unsuitable for complex, exploration-heavy environments with long-duration episodes. To remedy this, we introduce Action-Dependent Optimality Preserving Shaping (ADOPS), a method of converting intrinsic rewards to an optimality-preserving form that allows agents to utilize IM more effectively in the extremely sparse environment of Montezuma's Revenge. We also prove ADOPS accommodates reward shaping functions that cannot be written in a potential-based form: while PBRS-based methods require the cumulative discounted intrinsic return be independent of actions, ADOPS allows for intrinsic cumulative returns to be dependent on agents' actions while still preserving the optimal policy set. We show how action-dependence enables ADOPS's to preserve optimality while learning in complex, sparse-reward environments where other methods struggle.

Action-Dependent Optimality-Preservinn Reward Shaping
Grant C. Forbes' Jianxun Wang'
Leonardo Villalobos-Arias
Arnav Jhala' David L. Roberts'
Abstract
1. Introduction
There is growing interest in the Reinforcement Learning (RL) literature in using reward shaping to train agents in sparse-rewards environments that would otherwise be in- tractable (Mataric, 1994; Randløv & Alstromm 1998; Belle- mare et al., 2016); specifically, interest in Intrinsic Mo- tivation (IM): complex, Markovaav reward functions used to encourage exploration in sparse reward environ- ments (Pathak et al., 2017; Burda et al., 2018).
Recent RL research has utilized reward shaping- particularly complex shaping rewards such as in- trinsic motivation (IM)-to encourage agent ex- ploration in sparse-reward environments. While often effective, "reward hacking" can lead the shaping reward being optimized at the expense of the extrinsic reward, resulting in a suboptimal policy. Potential-Bas -Bsse Reward Shaping (PBRS) techniques such as Generalized Reward Match- ing (GRM) and Volicy-Invarian Explicit Shaping (PIES) have mitigated this. These methods al- low for implementing IM without altering optimal policies. In this work show that they are effec- tively unsuitable for complex, exploration-hewr heavy environments with long-duration episodes. To remedy this, we introduce Setion-Dependen Op- timality Preserving Shaping (ADOPS), a method of converting intrinsic rewards to an optimality- preserving form that allows agents to utilize IM more effectively in the extremely sparse environ- ment of Montezuma's 's Revenge. We also prove ADOPS accommodates reward shaping functions that cannot be written in potential-base based form: while PBRS-based methods require the cumula- tive discounted intrinsic return be independent of actions, ADOPS allows for intrinsic cumula- tive returns to be dependent on agents' actions while still preserving the optimal policy set. We show how action-dependence enables ADOPS's to preserve optimality while learning in complex. sparse-reward environments where other methods struggle.
It has been noted that both traditional reward shap- ing (Randløv & Alstrom, 1998) and IM (Burda et al., 2019) can be "hacked," with the agent learning to opti- mize the shaping reward at the expense of the actual re- ward. Potential-Based Reward Shaping (PBRS) aims to rectify this and provide a form for reward-shaping terms in which they can be guaranteed to not alter the set of optimal policies of the underlying environment. To apply PBRS to IM, previous work on Potential- tion (PBIM) (Forbes et al., 2024a) and Generalized Reward Matching (GRM) (Forbes et al., 2024b) implement arbitrary intrinsic rewards while preserving the theoretical optimality guarantees of PBRS. These methods have proven effective at speeding up training and preventing divergence from an optimal policy in grid world and cliff walking domains, with tabular exploration reward and Random Network Distil- lation (RND), respectively. However, their efficacy is still untested in more complex environments. Policy-Invariant Explicit Shaping (PIES) (Behboudian et al., 2022), another method developed for implementing shaping rewards with- out altering the optimal policy, has similarly been tested thus far only in relatively simple environments, and not in any environments wherein training with intrinsic reward is itself essential in consistently obtaining any extrinsic rewards in agent-environment interactions during training. Testing in Montezuma'ss 's Revenge, a benchmark environment that has been widely acknowledged (Mnih et al., 2015; Burda et al., 2019) to possess these characteristics, we find that all of these methods, while preserving the optimal policy set, de- tract from the agent's 's ability to learn the extent that none of them can outperform agent training on RND alone.
Intrinsic Motiva-
'Department of Computer Science, North Carolina State Uni- versity, Raleigh, USA. Correspondence to: Grant C. Forbes <gforbes@ @ @eceessuusss Jianxun Wang <jwang75 ncsu.duu>> Leonardo Villalobos-Arias <lvillal @ ncsu.edu>, Arav Jhala <abihala@@ccu..du>>, David L. Roberts (itrober4@nssu.ddu
Motivated by this, we develop Action-Dependent Pptimality-Preserviii Shaping (ADOPS), method for converting any arbitrary shaping reward (including IM)
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Action-Dependent Peptimality-Preeevviin Reward Shaping
to form that preserves optimality. ADOPS functions by consulting an agent's critic networks' estimations of the extrinsic and intrinsic value functions, and using these estimations, actively adjusting the intrinsic reward seen by the agent if and only if that reward would cause an action to be preferred when it would not be preferred by external rewards alone, or vice-versa. ADOPS improves on existing methods in several key ways:
tions both by their generality, as most of them are domain- agnostic, and by their complexity. IM methods are almost universally non-Markovian, often involving the agent's 's en- tire training history, and involving additional neural net- works and/or auxilliary learning algorithms.
Intrinsic motivation is often used as a means to reward exploration of the environment. IM methods such as count- based exploration (Bellemare et al., 2016), Intrinsic Cu- riosity Module (ICM) (Pathak et al., 2017), and Random Network Distillation (RND) (Burda et al., 2018; 2019) in- centivize visiting unfamiliar states. More recent IM works implement increasingly complex strategies (Badia et al., 2020; Yuan et al., 2023).
1. We forego the need for several key assumptions quired for previous methods to ensure optimality. These include the requirement that the environment be episodic and that the underlying IM is "future- future-agnostie."
2. We encompass a provably wider set of optimality- preserving shaping functions than prior methods. While GRM and PBIM both ensure and require that the expected intrinsic return at any given time step is action-independer our method produces shaping functions whose returns can be action-dependentt, yet still preserve optimality, Addition- ally, while PIES preserves optimality by eventually return- ing no shaping rewards at all, our method allows the agent to receive shaping rewards for an arbitrarily long amount of time. We argue that both of these improvements over prior methods are key to ADOPS's 'sss ability to outperform the baseline in complex, extremely sparse environments.
While useful for exploring, IM algorithms, including RND, are known to alter the optimal policy of the underlying envi- ronment. Take for instance the "noisy TV problem" (Burda et al., 20, in which an agent prioritizes an inrinsically- rewarding stochastic area of the state space at the expense of pursuing external rewards. A version of this problem exists in Montezuma's 's Revenge with RND in particular, deemed "dancing with skulls," " in which the agent tends to actively pursue "risky" behavior (Burda et al., 2019).
There have been some efforts to mitigate the noisy TV prob- lem: Chen et al. (Chen et al., 2022) introduce EIPO, which automatically adjusts the scaling factor of the IM, reducing the reward when exploration is unnecessary and increasing it when the agent must explore, and Le et al. (Le et al., 2024) mitigate it using "surprise novelty." " However, neither of these approaches provide theoretical guarantees that the optimal policy set is unchanged, and they both require non- trivial additional (neural network) architecture and computa- tional overhead. Forbes et al. (Forbes et al., 2024a) introduce PBIM, a Sitential-Based Readd-Reaa-d-apiiiiii approach that overcomes both of these limitations, and fur- ther expand it to the more general method of Generalized Reward Matching (GRM) (Forbes et al., 2024b). However, these works don't demonstrate efficacy at scale. We discuss these works in further detail in Section 3.
3. ADOPS empirically improves performance over base- line IM in complex, extremely sparse environments where preexisting methods for preserving optimality fail. We empirically demonstrate improvement over other optimallit--pessrviin methods and the baseline IM in Mon- tezuma's Revenge, and thus achieve new SOTA in imple- menting IM while preserving the optimal policy.
2. Background and Related Work
(PBRS) based
Here, we briefly discuss the relevant background literature more broadly. In Section 3, we describe more closely the three specifie methods we are building off of, and which we test against ADOPS in Section 6.
2.1. Intrinsic Motivation
2.2. Potential-Based Reward Shaping
Many problems in reinforcement learning are reward- sparse (Mataric, 1994) and are difficult for agents to properly learn. Sparse rewards can lead to an agent never learning viable policy. One method to remedy this is by granting a shaping reward: an extra reward, added to the native envi- ronment reward, to decrease sparseness, and convey more useful information.
AitentialBBssed Reward Shaping is subfield of reward shaping that specifically studies reward-shaping terms that are theoretically guaranteed to maintain the optimal pol- icy set of the underlying environment. The foundational paper in the field (Ng et al., 1999) explores how adding a reward shaping term to an MDP can alter the optimal policy. The study uncovers that the optimal policy will re- main unchanged in infinite-horizon MDPs, those with an absorbing state, if the shaping reward follows the form of state-based potential F = >D(s') - 4(s). This is further extended by Wiewiora et al (Wiewiora, 2003) by cre- ating a state-action potential (ss, a). whereas the original
Intrinsic Motivation is subfield of reward shaping that aims to navigate sparse-reward environments by giving the agent additional "intrinsic" reward shaping functions. These are usually distinguished from traditional reward shaping func-
2

---

Action-Dependent Optimality- Preeervvnn Reward Shaping
was state-only. Such potentials, however, must be removed from the final Q-values learned by the model to guaran- tee policy invariance. Similarly, Devlin et al. (Devlin & Kudenko, 2012) extend the original potential notation by adding time-dependence, $(s, 1), similarly guaranteeing policy invariance. Harutyunyan et al. (Harutyunyan et al., 2015) uncovered a method to convert any Markovian reward function into a potential-basee -base version that follows the form (ss a, t). A later study by Behboudian et al. (Behboudian et al., 2022) however demonstrates that this potential- -based conversion can, in fact, alter the optimal policy. In this same article, the authors propose Policy- Invariant Explicit Shap- ing (PIES), an algorithm that decrements the magnitude of shaping rewards to guarantee policy invariance by the end of training. We discuss this work more closely in Section
Thus an optimal policy in M' may be suboptimal in M, and we are interested in constructing F2 such that this is provably not the case.
3.1. Potential-Based Intrinsic Motivation (PBIM)
Potential- -asid Intrinsic Motivation (Forbes et al., 2024a), inspired by (Ng et al., 1999), proves that the optimal policy set of an environment will remain unchanged by the addition of a shaping reward in the form
F = 22.
(3)
where & is a potential function that meets the boundary condition:
PBRS was extended to the finite-horizon setting in (Grzes, 2017), and this finite-horizon setting was then later shown to be able to accomodate most IM terms' complex variable- dependence via PBIM (Forbes & Roberts, 2024; Forbes et al., 2024a) and later GRM (Forbes et al., 2024b).
E Now.,ar-T. R R (7 NN (,)) = T Vt E (0, (O....N
1),
(4)
and & is an arbitrary function that is constant with respect to action dz.
Any arbitrary shaping reward Fg can be transformed into potential-basee form if the value of F; does not depend on any future actions that the agent takes (For example, in episodic environments where the shaping reward is given retroactively). That is, F; must meet
In the next section, we highlight three of the most recent potential-based approaches: PIES, PBIM, and GRM. These are all aongg--ndppa""" approaches, signifying that they are generally adaptable methods for converting reward shaping function (or IM) into form that preserves the optimal policy (provided some assumptions are met). They will be the baseline algorithms that we compare our method against.
F2 constant w.r.t. aest, Vt, I' E (O....,N-1)) (5)
The authors of PBIM propose two transformation methods, normalized and non-normalized PBIM. Normalized PBIM is defined as
3. Preliminaries and Previous Methods
We define Markov Decision Process (MDP) as tuple M = (S, So, A, P, y, R)), where S is the state space, So C S is the set of start states, A is the action space, P(s++1 = s'1s, = 8, = a) the probability of transitioning to state s' by taking action a in state s, 7 E [o, 1] is the discount factor, and and R is the reward function. An agent in an MDP follows policy ([aas): S x AA- + [0, 1], which gives the probability of taking action a in state 8. An optimal policy maximizes the value function:
N -g - Fy, N f
F EPPIM
(6)
F. F.
where F is estimated average shaping reward for the current policy. Fý for non-normalized PBIM is defined identically, except that the F term is set to zero. They prove that using either of these conversion methods with an F; that meets the assumption in Equation 5 will result in a F/ that leaves the optimal policy unchanged if used as the shaping reward in Equation 2. Intuitively, both of these methods function by waiting until the last time step of episode, then subtracting all the accumulated intrinsic rewards from the agent.
N
VT++=
E
y R
(1)
GNT S00
1=
where Rs is the reward at time I, and N is the number of time steps in given episode. For infinite-horizon cases, the sum to N - becomes an infinite sum.
3.2. Generalized Reward Matching (GRM)
Generalized Reward Matching (Forbes al., 2024b) is broader pppimality-preservinn reward shaping method that encompasses both PBIM and all other PBRS- methods. It defines a matching function My : : x N + [0, 1] that 'matches' every instance of the shaping reward at timestep with an
Reward shaping methods, such as IM, add reward F; on top of the regular MDP reward Rg This defines a new MDP
M' = (S, So. A, P, R²), where
R² R₁ + Fr.
negative reward in future
3

---

Action-Dependent Sedimallit-Preserviinn Reward Shaping
timestep 1. The general förm of GRM shaping reward is
PBIM and GRM. However, though it is sufficient condi- tion for the preservation of optimality, it is not necessary condition, and we prove in Theorem B.1 that there will exist optimality-preserving preserving reward- shaping terms that cannot be written as a difference of potentials that follow Equation (4) in any non-trivial environment. 1. Fully-matching: Each given shaped reward must be subtracted exactly once (Although it may be partially subtracted across various timesteps): Vy Mi.=
F/GRM Fi
7
GRM rewards are proven not alter the optimal policy under two conditions:
Similarly, PIES preserves optimality by using only extrinsic reward in the latter stages of training: this is also clearly sufficient condition to preserve optimality, but just as clearly not necessary one. As such, it follows that many reward-shaping functions cannot, in principle, ever be obtained from either PIES or the PBRS- based methods described in prior literature.
2. auture-agnostic: Each shaped reward can only be dis- counted in future timesteps: Ve,es Mz,e" O.
In this section, we examine the more general condition from which Equation 4 is derived, and derive a more general condition, which captures shaping potentials that are "actioon-dependett" and thus provably cannot be accommodated by prior plug-and-play optimallty-preservingg methods. In Section 5 we then intro- duce ADOPS, which can accommodate this more general form.
A family of GRM functions is introduced in the same study, where the shaping reward is 'matched' either after a delay of 20 0 timesteps, or at the end an episode, whichever comes first. The corresponding shaping reward defined as:
presservin reward-
iKDD
F. GRG D)=
P--D F P--- D-1 10 PN-I-DH
if DS
(8)
-t=
4.1. Conditions For -reeaaiit-- Reward Shaping Functions Beyond PBRS
Note here, noted in (Forbes et al., 2024b), that if D N 1 for any given episode, then Equation (8) becomes equivalent to PBIM, while if D = 0, it becomes equivalent to having no shaping reward at all. In our experiments, we use this same parameterization as a representative sample of GRM methods.
We define the Q-function
as, Ry(s,,,t) VM,',++++)
(10)
to be the expected discounted return of taking action a in state of MDP M, then following policy x.? For simplicity of notation, we also define Qhr (St, a,, t) Qh,, Q5. We notate the Q-function of taking an action and then fol- lowing an optimal policy as QT Qūr- We can then write the general condition for preserving optimality: we want to ensure the optimal policy set is the same for both the original MDP M and the shaped MDP M', that is:
3.3. Policy-Invarian Explicit Shaping (PIES)
Policy-Invarian Explicit Shaping (Behboudian et al., 2022) proposes learning from a shaping reward without altering the optimal policy by multiplying the expected return of that shaping reward by a scaling coefficient& Ç that scales linearly to zero before the end of training. During training. PIES begins with So = 1, then for each episode n during training, Ç is updated according to
argmax Qh argmax Qia Vs,t.
(11)
This is the condition that all prior work in PBRS seeks to preserve. Note crucially that we are defining T such that it is an optimal policy in the original environment M, not necessarily in an environment M' with the shaping reward present. For clarity on this point, we define Q Q7 to be the extrinsic Q function, and Q = Q% Q% + Q7 to be the combined extrinsic and intrinsic Q functions. We define VTE. Vē, and V/ likewise. Thus, we have
if S--1> j/
Gn -==
(9)
otherwise.
Here, C' is a coefficient that controls how quickly Ç decays. Ideally, will reach zero with enough training time left that the agent can converge to an optimal policy, if the reward shaping term is one that the agent would otherwise hack.
argmax Qi argmax + Q7) Vs,t, (12)
4. More General Conditions For Optimality
'The 4,, terms each of these methods are implicit, rather than explicit, but both methods are designed around ensuring that Equation 4 always holds.
A PBRS term that follows Equation (4) guarantees that the optimal policy set of the original MDP will remain un- changed. This includes the PBRS terms utilized in both
NNote the direct d-dependence, as we're generally dealing with non-Markovian reward functions.
4

---

Action-Dependent
Reward Shaping
Note the enumeration over all x*: this is because, while every optimal policy by definition has identical QE and V to every other optimal policy, they may differ from each other intrinsically, resulting in different Q7 and Vi.
5.1. The 'Ideal' ADOPS Function
Inspired by the conditions in Equations 13 and 14, we first introduce an "ideal" reward-shaping conversion method that actively checks whether these conditions are satisfied, and if not, modifies the initial shaping reward just enough to ensure that they are. We define this ideal ADOPS reward as FF = F + F2, where F is some arbitrary initial shaping reward, and F22 is defined as
If we now define ā as any action not in argmax, Qg. then Equation 12 becomes equivalent to
Vi = (o, V Qis(s,ā,t) < (iE(s,t) Vs,
(13)
min (o.VV -V--)---- it VEVVE 1
(14)
F2=
if Q.2V.
(15)
Here, e is arbitrarily small positive constant. We are defining Vý here such that it represents the maximum in- trinsic reward achievable while following an extrinsically optimal policy.
Intuitively, the first of these conditions says that every action that would be optimal without IM must remain optimal after the addition of the IM, while the second condition says that any suboptimal action must remain suboptimal with the addition of any shaping reward.
The first case of this equation can be intuitively thought of as checking to see if Equation 14 is violated, and if so adjusting the intrinsic reward downwards until it longer is ("if this action is extrinsically suboptimal, make sure that it is still suboptimal when the IM is taken into account"). Conversely, the second case checks to see if Equation 13 is violated, and adjusts the IM upwards if so until is not ("if this action is extrinsically optimal, make sure that its intrinsic returns are equal to those of every other extrinsically optimal action")).
In prior work in PBRS, the optimal policy set is provably unchanged due to mathematical guarantees that Qi differs from Qi by some term that independent of the agent's is actions at a given time step: see for example the (s)) of (Ng et al., 1999), or the &' of (Forbes et al., 2024a). In other words, all prior work in this area has met the condition of Equation 12 by removing (a)'s a-dependence, and essentially setting (a(a) = V? Va. While this is a suffi- cient condition to ensure that optimality is preserved (as this term then drops out of the argmax,. it is not a necessary one. As we will see, it leaves out a theoretically interest- ing and empirically useful subset of pptimality-preservinn reward shaping functions: those whose cumulative intrin- sic returns are allowed to depend on the agent's actions. In Appendix 1. we offer a formal proof that there exist optimality-preserinng reward shaping functions that meet these conditions we have just provided, but which cannot be accounted for by any PBRS function. In the next section, we derive a new plug-and -lay method of utilizing arbitrary IM functions while theoretically guaranteeing preservation of optimality, one that both overcomes the limitations of flex- ibility highlighted in Appendix B.1 and foregoes the need for several key assumptions (an episodic environment, and agnostiiiy as defined in Equation 5). We then show that our method speeds training efficiency over a baseline in complex, difficult environment where other optimality- preserving methods fail.
A full proof that this version of ADOPS preserves the op- timal policy can be found in Appendix B.2. In the next section, we introduce a of ADOPS, and prove that it preserves optimality, as well.
version
5.2. A Practical, Easy-To-Use Form of ADOPS
While it would be idcal, it is usually not feasible to imple- ment Equation (15), as it requires an accurate estimate of the optimal value function. Let's assume instead that we have access to some critic function that allows us to make approximations of the value function of given state, and the f-fncciion of taking some action in that given state, under the agent's current policy л. Let us also assume that this critic handles the extrinsic and intrinsic rewards sepa- rately, such that we can deal with them independently (this is already a common practice, for example in (Burda et al., 2019), whose example we follow in Section 6 6). We notate these estimates as V Vi QT, and Q7 This notation has dependence, but occasionally throughout
implicit variable-dependeee - this section we make their variable dependence explicit, as in Q%, a).
5. ADOPS For Action-Dependent Preseeii Shaping
Given some initial shaping reward F, about which we make no assumptions, we define the ADOPS reward to be
Here, we introduce our main contribution, and prove its efficacy at preserving the optimal policy.
min(O, V -7+
if QE<VE
F
Implicit in the step from Equation 12 Equation 13 is the fact that @i(aa) )- = V Va", Va",=". ...
max -7-7 ir Q72VE.
(16)
5

---

Action-Dependent DpptinalityPrreervviin Reward Shaping
We define this shaping reward in terms of the actual value
equivalent. We define
and Q-function values (as opposed to their critic-based esti- mates) for the proof, and discuss our conditions for imple- menting this practically at the end of this section.
Ω = VE -Q2 + - -V7((- - F
(17)
C = =1QQ7 < VE AQ>
(18)
For our proof, we make an additional assumption about our optimization process itself. Let n be a policy that takes action On in some state s E S. Additionally, take Rm to be a policy that is identical to Ty, except that takes action a. in that same state s. We will say that policy an is "unstable" if there exists a Tm such that QTE (8, an) < VEE Vigg's (s) and Q7, am) 2 (s). In other words, if a policy is unstable, that means there exists some other extremely similar policy, which differs by only one action in one state, and yet is strictly preferred under any nontrivial mixture of the two policies. Conversely, a policy is "stable" if no such strictly-pree prreffrabeee policy exists. We can now state our assumption:
C2 = =(QQ7
(19)
C3 = - < A
(20)
where C₁ C22 and C3 are indicator functions that are 1 if the condition in them is true, and 0 otherwise. We can then rewrite F2 as
=2 1C-2-CC-
+ + - C3e.
(21)
We can now rewrite Q7E as
Qis
(22)
E
[RAF4
(23)
(s'lass)
Assumption 5.1. The training algorithm being used will, upon convergence, only execute stable policies.
E P(F
(24)
E P(''aa))
V (C1
(25)
This assumption can be thought of as a requirement that the learning algorithm being employed will only converge to policy that is preferred to all other policies in the local policy space (a local optimum). Note that any optimal (with respect to intrinsic and extrinsic rewards) policy will always be stable, and thus that any algorithm guaranteed to converge to an optimal policy is also guaranteed to converge to a stable policy. Intuitively, then, we should expect any competent learning algorithm not ever converge unstable policy, as any exploration around the local policy space would cause the agent to learn action am over On- Indeed, any learning algorithm that does not ever explore the local policy space sufficiently so as to find such a strictly- preferred, small perturbation to its current policy is unlikely to have learned much in the first place. As such, this is reasonable assumption make, at least in the limit as training converges to policy, which is the domain in which we're interested for the purposes of leaving the set of optimal policies unchanged.
When taking the argmax of this result, the Vig term drops out due to having no a-dependence, and we are left with
argmax, =argmax,
Ha-- (26)
For any given a value, either Qg(a) < Vg. or (a) > Vg. If (%) < V then a will not be included in argmax, o (QE (a)). Correspondingly, if (a) < Vg. then Equations 17, 18, 19 and 20 require that C2 = 0, and one of either - C2 or -Cye will be nonzero and strictly negative for these actions, with the other term being zero Therefore, for actions that are extrinsically worse in expec- tation than the current policy, the term inside the argmax of Equation 26 will be strictly less than zero. Thus, following Equation 25, if (a) < Vž. then (Tn(a) < ViE-
If (T(a) N VE. however, both the Ci and C3 terms in the argmax of Equation 26 will be zero The C2 term will be strictly positive if f2 < O, and zero otherwise. This observation combined with Equation 25 implies that Qi 2 VTr. Therefore all actions with (T) < V will not be included in argmax, (QT (a)), as there will always be at least one action with a greater expected (ix(a) (the best action sampled from the current policy T).
We now prove that adding an ADOPS reward term to any initial F' preserves optimality.
Theorem 5.2. An intrinsic reward of the form F² = FF+ with F2 defined according to Equation 16 will preserve the set of optimal policies.
We've now shown that, in any given state s, any action in a" argmax, (QL a)) will have Qig(s, a") > Vir(s), but we've not yet proven that each a" will be in argmax, (5ngnaxx(77(())) (8)) To prove this, let's now assume for contradiction that there exists some other action ā &f argmax, trggax,,Qu (s, a)) such that Q7g(s, a) > (s.(s,") We define Ta to be identical to policy π except that it takes action in state 8. We can then prove that na is unstable,
Proof. We proceed by first showing that for all possible actions the agent could take, Qie 2 VIE iff Q7 2 Vg. and QT < ViT iff QT, < Vg. We then, from this, show that for all stable policies under Assumption 5.1, argmax, (rginx,(QIE)== (Q7))
We begin by rewriting Equation (16) to be more concise, and removing the cases, while keeping it mathematically
6

---

Action-Dependent Settinaltty-Peseevinng Reward Shaping
and thus that, under Assumption 5.1, converged agent will not follow it. Under this new policy, we can calculate the new Q-function of a":
the extrinsic reward only. Therefore, upon convergence, the underlying learning algorithm using the ADOPS shaped reward will subsequentyy produce an optimal policy under the extrinsic reward, and Equation 1 holds.
(Ig(s,0")=
E e'"P(e'),,s)
IE (C1 + C2) Cze).
(27)
This proof so far has been for an F/2 wherein we have some access to perfect estimations of state and action values. To extend our framework to function approximations of state and action values, we apply an additional assumption that the base learning algorithm for updating different value estimations convergences. In other words, under the premise that the approximation error is bounded by E, the value estimations are bounded by a factor C. with regards to the approximation error (Agarwal et al., 2019; Jin et al., 2023). With our proven cedimality--reservviee property then, the underlying learning algorithm with the shaping reward from ADOPS, in the worst-case scenario, shares the same convergence property as the original version of the problem, without utilizing the ADOPS reward.
Because, by definition, V (s) < QE a²) (as otherwise a would be extrinsically optimal action in s), we know that both the C1 and C33 terms must equal zero, leaving only the C2 term, which is always positive nonzero. This proves that VIE < (s,(s, a"). That is one of the two conditions required for ma to be unstable.
On the other hand, if the agent follows policy T. defined as policy that's 's identical to except that it takes action a" in state the Q-function of taking action ā becomes
QTE (s,
E s'~P(t/(a,,)
VTE² - (C1 + C2) - C3c).
(28)
In this formulation, since know that VE (s) OTe" as, we know that the C2 term must be zero, while one of either the C1 or C3 terms must be strictly negative, with the other being zero. This implies that QTE (s, a) < VIE" (s): the other condition required for xa to be unstable.
6. Empirical Results
We test ADOPS, as well as prior optimality-preserving re- ward shaping methods in the Montezuma's 's Revenge (Belle- mare et al., 2013) Atari Learning Environment (ALE) with RND IM (Burda et al., 2019). We find that PBIM, GRM, and PIES all fail to converge to a policy that outperforms the policy trained on the baseline IM. We tested several versions of ADOPS in this environment and found that all versions tested achieve higher performance than the baseline IM. We provide details of our experiments in Appendix A.I.
Because action a" strictly better than à when the agent is following policy no*, and no worse when the agent is follow- ing policy Na. it follows that it is strictly better when follow- ing any nontrivial mixture of the two policies, and that ma is an unstable policy. From Assumption 5.1, we know that the learning algorithm will never converge to such policy. Thus we have a contradiction: in convergence, there exists no policy for which (s.(s,0) a) > Q7g(s, a²) that not in argmax, (Q%), and thus every action in argmax, (27 is also in argmax, (Q
6.1. PBIM
We find that PBIM with RND, whether normalized or non- normalized, fails to ever obtain nonzero extrinsic rewards in Montezuma's 's Revenge. PBIM almost immediately saturates the agent's action probabilities in this environment (the average probability of the action being taken). We find that the culprit is PBIM's reliance on accounting for all its intrinsic rewards at the end of the episode, combined with Montezuma's 's Revenge's 's long episode lengths. This is due to the exponential nature of the denominator in the final reward for episode under PBIM:
A similar line of reasoning goes the other direction. Given an action a" E argmax, (QT (s, a)) and another action à & argmax, (Q7e(s, a)) with QT (s, @) > (s, d"), we find that Q (s, a) < VTE and QT (s,aa))) 2 Vig. thus concluding that this is unstable as well.
When dealing with convergent policies then, given Assump- tion 5.1, we must conclude
Un 7 N-
argmax = argmax
VT.
(29)
F
F
(30)
where Up is the discounted return of the previous intrinsic rewards obtained throughout the episode. When training in smaller environments, such as the cliff walker and grid world experiments of (Forbes et al., 2024a), this reward is reason- able, and effectively speeds up training. In environments like Montezuma's 's Revenge, however, with potentially very
Because we can ensure that the learned value functions and action-value functions using the full reward will induce the same optimal actions comparing to the extrinsic reward for any converged policy, the training process will align with the Bellman optimality equation (Peng& Williams, 1993) using
7

---

Action-Depence
Reward Shaping
GRM. Though this difference isn't statistically significant, we hypothesize that is because our environment's extrin- sic reward is strictly positive, which tends to make longer episodes more likely to have extrinsically higher returns, and thus a bias toward prolonging the episode like that descrited in (Forbes et al., 2024a) is not harmful in the same way as in their experiments, which are in environments where the optimal policy is to reach goal state as quickly as possible. Thus, the normalization's effect of mitigating this bias may not be as useful here.
Eabira ADORSS
LAT NarTE
4D0P25 at
2000
1000
6.3. PIES
We tested PIES with ( decay rate č 15000 We chose this rate to strike balance between giving the agent enough time with intrinsic rewards to explore the environment and giving it enough time without intrinsic rewards to converge to an optimal policy. With this decay rate, PIES "starts" con- serving the optimal policy, in theory, at exactly the halfway point in training, as this the point which begins to return an IM of zero. We also modified the PIES algorithm slightly to suit our larger training environment: we update the value of the Ç coefficient every iteration, rather than every episode, as we are training multiple agents in parallel, and with highly variant episode lengths from one episode to another. We also modified PIES by using it to shape the coefficient of IM, rather than a potential-basee Markovian shaping reward, as it was used in (Behboudian et al., 2022); consider this itself to be novel extension of the PIES methodology, albeit a simple one.
Figure 1. Comparison of all methods in Montezuma's 's Revenge. All plots are smoothed over the past 10 steps. Error hars are errors on the mean. Differences between RND and both normalized and non-normalized GRM are statistically significant, with p 0.009 and p 0.031, respectively. Differences between RND and PIES are nearly. but not quite statistically significant, with p = 0.059. Differences between normalized and non-normalized GRM are not statistically significant, with = 0.37 (two-sided t-testt. ADOPES is better than RND to statistically significant degree, p = 0.038. ADOPS, ADOPES, and ADOPES w/ //2 all improve on PIES to a statistically significant degree, with p 4.4e 5, p 2.4e 6, and p = 6.4e - 5. respectively (two-sided t-test). They similarly improve over GRM and PBIM. N 10 for each GRM run, N for cach PBIM run, and N 20 for all other methods.
long episodes and relatively low y values, the denominator in this reward becomes unwieldy, and the end-of-episode 'penalty' term exponentially explodes, preventing further learning. We investigate and discuss this finding further in Appendix A.2.
Our PIES results are also plotted in Figure 1. Note that, while PIES performs well initially, it decreases in perfor- mance rapidly upon approaching the halfway point of train- ing, and never recovers: in other words, its performance worsens as soon PIES begins approach conserving the optimal policy set of the underlying environment. This sug- gests a clear trade-off: PIES can either conserve the optimal policy of the underlying environment, or allow for IM to be used effectively, but struggles to do both simultaneously. Also of note is that the multiplicative coefficient for the IM we used for our RND runs (and thus the effective value of ( at the first iteration for our PIES runs) was simply 1, as in the original RND paper (Burda et al., 2019). As that paper didn't test different values for this hyperparameter, the initially good performance of PIES in Figure I suggests that the best value of this coefficient is likely lower than the default value used. In the first half of Figure 1, after all, PIES is essentially equivalent to RND as implemented in the same plot, but with a lower and steadily decreasing multiplicative coefficient for the intrinsic rewards. In Sec- tion 6.4 we present more results that suggest this is indeed the best explanation for PIES's 's good early performance.
6.2. GRM
To compare our method to GRM, we chose the same subset of GRM methods recommended in (Forbes et al., 2024b), pa- rameterized by the delay hyperparameter in Equation (8). To determine for which value for D GRM fares best in this environment, we tested single runs across a wide range of D values. We detail the results of this hyperparameter test in Appendix A.3, We find that lower D values are consistently better, keeping in line with our results from Section 6.1, and further suggesting that too-long delays between when an intrinsic reward is received by the agent and accounted for can cause an exponential explosion. Our best-performing candidate used D 1. We therefore tested both normal- ized and normalized versions of this equation our representative tests of GRM.
As can be seen from Figure 1, all versions of GRM or PBIM failed to reach the same average cumulative extrinsic re- ward as RND, to a statistically significant degree. Addition- ally, normalzll GRM seems to outperform normalized
8

---

Action-Dependent Deniiaality-Prseevviin Reward Shaping
6.4. ADOPS
Acknowledgments
We test three versions of our method. The first, our baseline ADOPS method, simply implements Equation (16) using the critic networks' estimations of the relevant quantities.
Thanks to Nick Gauthier for help setting up and debugging the relevant python packages.
Noting that these critics' estimations are much better later on in training than earlier, we also implement a fusion of our method with PIES, which we call Action Dependent Optimality Preserving Explicit Shaping (ADOPES). It is equivalent ADOPS, except with a coefficient multiplied by F- that begins 0, then scales up throughout training, to final value of I, rather than down. This means that PIES and ADOPES both begin identically, giving the agent unfet- tered access to the base IM at the start of training. However, while PIES linearly scales this reward down throughout training until the agent is receiving no IM at all, ADOPES instead scales up the coefficient by which Fg is multiplied, thus preserving the optimal policy in a way that still gives the agent access to IM during the latter half of training.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
References
Agarwal, A., Jiang. N., Kakade, S. M., and Sun, W. Rein- forcement learning: Theory and algorithms. CS Dept., UW Seattle, Seatlee WA, USA, Tech. Rep, 32:96, 2019.
Badia, A. P., Sprechmann, P., Vitvitskyi, A., Guo, D., Piot, B., Kapturowski, S., Tieleman, O., Arjovsky, M., Pritzel, A., Bolt, A., et al. Never give up: Learning directed exploration strategies. arXiv preprint 2ii:22002.06034 2020.
Finally, inspired by the early success of PIES in Figure 1, to see what extent lowering the starting multiplicative co- efficient for IM had on the training speed, we also trained on version of ADOPES with the starting IM coefficient lowered to .,, or half of what was in the original RND paper or our other experiments.
Behboudian, P., Satsangi, Y., Taylor, M. E., Harutyunyan, A., and Bowling, M. Policy invariant explicit shaping: an efficient alternative to reward shaping. Neural Computing and Applications. pp. 1-14, 2022.
All our ADOPS-based runs are included in Figure 1. All of our methods outperform all prior optimality-preserve work in terms of the average extrinsic return of the final policy to a statistically significant degree, and ADOPES also outperforms RND to a statistically significant degree, as well as being the best-performing method overall. Our modified version of ADOPES with a lowered IM coefficient learned more quickly than the other runs, supporting our explanation that PIES's promising results earlier on in train- ing were the result of incidentally finding better values for the IM scaling coefficient along the way to zero. However, unlike PIES, ADOPES allows the agent to keep receiving intrinsic rewards past the halfway point of training and thus can maintain its ability to receive higher extrinsic returns throughout training.
Bellemare, M., Srinivasan, S., Ostrovski, G., Schaul, T., Saxton, D., and Munos, R. Unifying count-based ex- ploration and intrinsic motivation. Advances in neural information processing systems, 29, 2016.
Bellemare, M. G., Naddaf, Y., Veness, J., and Bowling. M.
The arcade learning environment: An evaluation plat- form for general agents. Journal of Artificial Intelligence Research, 47:253-279, 2013.
Burda, Y., Edwards, H., Pathak, D., Storkey, A., Darrell, T., and Efros, A. A. Large-scale study of curiosity-drivan learning. arXiv preprint arXiv:1808.04:3 04355, 2018.
Burda, Y., Edwards, H., Storkey, A., and Klimov, O. Ex- ploration by random network distillation. In 7th Inter- national Conference Learning Representations (ICLR 20/9), pp. 1-17, May 2019. URL https: iccr. cc/. Seventh International Conference on Learning Rep- resentations, ICLR 2019: ; Conference date: 06-05-2019 Through 09-05-2019.
7. Conclusion
We present ADOPS, a novel plug-and-play method for implementing shaping rewards while preserving the opti- mal policy of the underlying environment. We prove this eeiimality-preeerviin property, as well the lack of several previously-necessary assumptions, and demonstrate SOTA performance in a difficult environment, as compared with other optimality- preeeeriig methods.
Chen, E.,, Hong, Z.- Pajarinen, J., and Agrawal, P. Re- deeming intrinsic rewards via constrained optimization. arXiv preprint arXiv:221 1..222271.7777... 2022.
Devlin, S. M. and Kudenko, D. Dynamic potential- based reward shaping. In Proc. of the 1ith Int. Conf. on Au-

---

Action-Dependent Porimality-Preserving Reward Shaping
tonomous Agents and Multiagent Systems, pp. 433-440, 2012.
Peng, J. and Williams, R. On the convergence of stochastic iterative dynamic programming algorithms. Adaptive Behavior, 1:437-454, 1993.
Forbes, G. C. and Roberts, D. Potential-based reward shaping for intrinsic motivation (student abstract). In Proceedings of the AAAI Conference Artificial Intelli- gence. AAAI, 2024.
Randløv, and Alstrøm, Learning to drive bicycle using reinforcement learning and shaping. In ICML, volume 98, pp. 463-471, Citeseer, 1998.
Forbes, G. C., Gupta, N., Villalobos-Arias, L., Potts, C. M., Jhala, A., and Roberts, D. L. Potential-based reward shaping for intrinsic motivation. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, pp. 589-597, 2024a.
Schulman, J., Wolski, F,, Dhariwal, P., Radford, A., and Klimov, Proximal policy optimization algorithms. arXiv preprint 1707 2017.
Wiewiora, E. Potential- shaping and q-value initial- ization are equivalent. Journal of Artificial Intelligence Research, 19:205 208, 2003.
Forbes, G. C., Villalobos-Arias, L., Wang, J., Jhala, A., and Roberts, D. L. Potential-based intrinsic motivation: Pre- serving optimality with complex, non-markovian shaping rewards, arxiv preprint, 2024b.
Yuan, M., Li, B., Jin, X., and Zeng, W. Automatic intrin- sic reward shaping for exploration in deep reinforcement learning. In International Conference on Machine Learn- ing, pp. 40531-4055 PMLR, 2023.
Grzes, M. Reward shaping in episodic reinforcement learning. In Sixteenth International Conference on Au- tonomous Agents and Multiagent Systems, 2017.
Harutyunyan, A., Devlin, S., Vrancx, P., and Nowé, A. Ex- pressing arbitrary reward functions as potential-based ad- vice. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29(1), 2015.
Jin, R., Li, S., and Wang, On stationary point convergence of ppo-clip. In The Twelfth International Conference on Learning Representations, 2023.
Kazemipour, A. Ppo-rnd, 2022. URL https: /githbb. com/ com/alire http://reeeaaaaeeeoororrooo----
Le, H., Do, K., Nguyen, D., and Venkatesh, Beyond surprise: Improving exploration through surprise novelty. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, pp. 1084- 1092, 2024.
Mataric, M. J. Reward functions for accelerated learning. In Machine learning proceedings 1994, pp. 181-189. El- sevier, 1994.
Mnih, V., Kavukeuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidje- land, A. K., Ostrovski, G., et al. Human-level control through deep reinforcement learning. nature, 518(7540): 229,533,20 2015.
Ng. A. Y., Harada, D., and Russell, S. Policy invariance under reward transformations: Theory and application to reward shaping. In ICML, volume 99, pp. 278-287, 1999.
Pathak, D., Agrawal, P., Efros, A. A., and Darrell, T. Curiosity-driver exploration by self-supervised predic- tion. International conference on machine learning, pp. 2778-277720 2787. PMLR, 2017.
10

---

Action-Dependent Optimality-Preserving Reward Shaping
1.0
0.8
Probability
PBIM
PBIM Norm RND
0.4
0.2
500
1000
1500
2000
2500
Training Sleps
Figure 2. Action probabilities for RND and PBIM.
A. Experimental Details
Here, we detail more about our experiments.
A.1. Experimental Setup
Montezuma's Revenge ALE environment is a challenging sparse-rewards environment with a history of being used as a benchmark for IM methods (Burda et al., 2018; 2019). We used the environment unmodified. Our base model for all trained agents was the PPO algorithm (Schulman et al., 2017), with additional intrinsic rewards from the RND network (Burda al., 2019). We use the same hyperparameters as the 32-worker Convolutional Neural Net (CNN) runs in (Burda et al., 2019), with one key difference: while (Burda al., 2019) clips external rewards to the interval [-1, 1]. train on the external reward as-is because are primarily concerned with methods that preserve the optimal policies of the underlying environment, and this clipping might alter that set (for example, by eliminating the effective difference between a reward of 1, 000 and 2, 000, and thus changing whether it is strictly preferred for the agent to collect the latter reward first). To compensate for this change, we scaled the extrinsic reward down by a factor 1000, to keep the expected order of magnitude of extrinsic rewards identical to that in (Burda et al., 2019). 4 For methods requiring normalization, such as PBIM Norm, we used exponential smoothing with a 0.05. For all ADOPS variants, we used c 1e 7.
We use the implementation in PPO-RND (Kazemipour, 2022) as initial codebase. PPO-RND does not have active license. We conducted experiments using gymnasium API simulated by Arcade Learning Environment (ALE) (Bellemare et al., 2013) for Montezuma's 's Revenge. We use ALLEMMotezuuaReeeegeeee in our experiments. Gymnasium API is under the MIT license and ALE is under GPL-2.0 license.
We conducted our experiments on two servers with Ubuntu 22.04. One server has 12 Intel(R) Xeon(R) CPU 16506 NVIDIA GeForee GTX 1080, and 32 GiB memory. We run two experiments concurrently on The other server has 12 AMD EPYC 7401P CPU, NVIDIA TTTAN RTX, and 30 GiB memory. Each run takes around 30 hours.
A.2. Failure of PBIM To Obtain Rewards
As can be seen in Figure 2, PBIM and PBIM Norm immediately saturate the action probability, preventing the agent from ever obtaining nonzero extrinsic rewards. This is contrasted with action probabilities for of RND, which demonstrates typical action probability for successful methods in this environment at the beginning of training. As the PBIM methods immediately converge to an action probability of 1, they never explore the environment, and thus never obtain any extrinsic rewards. 5 We use the same maximum episode length and intrinsic discount ?r values as (Burda et al., 2019), which are 4, 500 and .99, respectively. As an mf-gniiude calculation, 35 R 10 implying that we should expect the intrinsic rewards in the final time steps of the longest episodes in this environment with PBIM to around this large. Indeed,
*We found that without this scaling factor, the agent performed significantly worse. This scaling factor considered separately from the scaling factor discussed in Section 6 in the context of PIES and ADOPES, as it is for extrinsic rewards, whereas that factor is for IM. 'In both cases, the particular action being taken at every time step by the agent is to not move all.

---

Action-Dependent Reward Shaping
N-1
500
1500
External
1000
5000
10000
15000
20000
25000
30000
Taining Steps
Figure 3. Extrinsic returns for runs with various values of D in Equation (8). All runs are normalized. The run with D = N 1 equivalent PBIM Norm from (Forbes al., 2024a).
through inspection, we did observe rewards of this magnitude under both PBIM and PBIM-Norm, and it was these rewards that saturated the action probability in Figure and thus prevented learning. Thus, we find that neither PBIM method is suitable to be used in environments with potentially long episode lengths and low ? values, but should instead be limited to environments with shorter episodes and long time horizons within those episodes. 6
A.3. Hyperparameter Test For D in GRM
We plot the results of our GRM D hyperparameter test in Figure We ran these tests using the normalized versions of GRM, taking into account the results of (Forbes et al., 2024b) suggesting that this makes a wider range of values robust against introducing unwanted biases from the data.
B. Additional Proofs
Here, we detail additional proofs.
B.1. Proof Regarding GRM's Lack of Generality
Here, we prove that there is relevant set of or PBRS.
shaping functions that cannot be accommodated by GRM
Theorem B.1. There exist optimalltty reward shaping functions which cannot be written GRM shaping functions.
Proof. In given MDP, take the shaping function F2 Rg Trivially, this preserves the optimal reward. For proof by contradiction, we assume there exists some ma,' Ft such that this can be written as GRM shaping reward in the form of Equation (7). Taking the intrinsic return at time f, we get
U. Σ P
(31)
N-1
Σ
(32)
1=
where Uilota is the cumulative discounted sum F., We know from the proof for GRM's optimality in (Forbes et al., 2024b)
'For reference, the longest episode length in an environment wherein PBIM successfully sped up training performance in (Forbes al., 2024a) was 640 time steps, and the discount factors tested ranged from .99 to .995. These are equivalent sets functions, as proved (Forbes et al., 2024b).
12

---

Action-Dependent Optimality- Preeerviin Reward Shaping
that this entails
U =
R
+
F
Σ mj.i
(33)
0
Since all Fy must be future-agnostic (Equation (5)), we can apply Equation (5) to assert that U.! has no a a--dependence. But this is not generally true, and certainly false in any nontrivial environment: because we've defined Ft such that U.- = UP, this would imply that in every environment, the agent actions cannot influence its return. We have thus derived contradiction, and so our assumption that GRM can accommodate F? = R& was false.
To further understand the implications this proof, examine what would happen if we were to plug this counterexample shaping function F` R. into the GRM framework: it would convert into shaping reward that is, indeed, action- independent. In doing so, it would discard much of the useful information contained in that reward.
In contrast with GRM other PBRS-based methods, ADOPS can easily accommodate reward shaping functions of this type: in fact, the theoretical best ADOPS method we define in Equation (15) correctly identifies this shaping function as not disrupting the optimal policy to begin with, and returns it back unchanged, with F" = Fe.
B.2. A Proof of Optimality of the "Ideal" ADOPS Shaping Function
Given some initial shaping reward F, about which we make no assumptions, we define the ideal (usually inaccessible) ADOPS shaping reward to be
(0, V Q' + V7 -V)(() - F-) if Q < V if Q 2 E
F2 =
(34)
ma Vg Q + V2 -V/(s)
Here, we are defining V such that it represents the maximum intrinsic reward achievable while following an externally optimal policy. While for any extrinsically optimal policy, it will always be true that V is equivalent to that of any other extrinsically optimal policy, they may differ terms of which achieves higher intrinsic reward: when this is the case, we take V, to be the maximum of these.
We prove that adding this reward term to any initial F preserves optimality.
Theorem B.2. An intrinsic reward of the form F = F F2 with F2 defined according to Equation 34 will preserve the set of optimal policies.
Proof. Proof by contradiction. To prove that optimality is preserved, it suffices to prove that Equations 13 and 14 hold for any trajectory. Let us assume that there exists some गे such that
O < Vg
O + Q7 2 V2
(35)
This is equivalent to assuming that Equation 14 does not hold. We can then write the quantity Q% + Q7
of = Q + E(F F2 + (s)))
(36)
From the first component of our assumption, we know that F2 is going to be defined according to the topmost case of Equation 34. We can then decompose our expression into contributions from terms wherein F2 0 (from the min function). and those in which it does not. We can define
Q + QF
(37)
=Po(Q Qf) (1 (1- + P
(38)
=Po( + +E(F +~VV,u(5'))
(39)
( +E(Ffo + F2,40 + > (T,z)(s))))
(40)
where Po is a scalar representing the proportion of trajectories from the relevant state in the relevant action in which F2 = 0, and the subscripts 0 and jf represent the contributing terms in which F2 and F2 * 0, respectively.
13

---

Action-Dependent Appiimalit-PPreervviin Reward Shaping
For the terms with the + 0 subscript, find
Q + EF + F2 + +
(41)
=Q + [0 #0 + VE QE Vi -VT Feo c VVT
(42)
=Q + BVV Q + Vī -c)
(43)
=VE + V7 -c
(44)
We also know from the condition in 34 that
V
Q + V7 >VV,, -20
(45)
Q + (50')) Fos V + Vi QB B(>V770 + Fo) S V + Vi
(46)
(47)
which gives us upper bound for the terms with the subscript. Taking our assumption, then, we can replace both components of Equation 40 with their respective reductions, which gives us
V V S SQ -
(48)
- Po(VE +V2 -)) + +1- + Ví e)
(49)
V2 + VÝ -c.
(50)
This is contradiction, and thus we have proven that Equation 14 holds. To prove Equation 13, we similarly assume that there exists some extrinsically optimal x such that
V
L Q7 V Vi.
(51)
The second component our assumption includes two possible cases:
QE + Qf
V V
QE
+ OF VE V
(52)
Let's begin by assuming the first of these. We again decompose Q + Q7 into two parts, using the constant Po to denote the percentage of contributing trajectories that are set to zero:
O + Q7
(53)
=Po(EE +1- + +F)))
(54)
=PoQO + EEF + (+)))
(55)
+(1 (1) BF F2,40 + (VT
(56)
Here, due to our differing assumption, whether or not a contributing trajectory has its F2 term set to zero is determined by the max function in the latter case of Equation 34, rather than the min function the former. For trajectories where F2 & 0, then, we get
QF + E(F + F2.00 + +VV))o('')
(57)
-QT + E(F + VB QE + +V -7V,500066) - Pso + +V77
(58)
=QT + E(VE Q +V7)
(59)
= VE + V
(60)
For conditions with the 0 subscript, we know from the condition in Equation 34 that
V Q +V -V% F. 5
(61)
Q + 2
(62)
OF E(Fo (7. 2
(63)
14

---

Action-Dependent Optimality-Preeeriinn Reward Shaping
Looking first at the first decomposition of the + in Equation 52, get
V + V QE + +07 PA + V7) + Po) + V7)
(64)
(65)
> VE + V7.
(66)
This is contradiction. The other decomposition of our assumption in Equation 52 implics
V V7 Q +
(67)
V + V7 < VE + +7
(68)
V7 QT
(69)
(70)
Here, between Equations 67 and 68, applied our first assumption in Equation 51. Because we have defined V to be the highest possible intrinsic reward among extrinsically optimal trajectories, this is contradiction as well. Thus Equation (13) must hold. This suffices to prove that the set of optimal policies remains unchanged.
15


Reviews:
[{"review_id": "i7ZTCQ4GLv", "reviewer": "Reviewer_4wwG", "summary": "This work introduces Action-Dependent Optimality Preserving Shaping (ADOPS), a general framework for modifying intrinsic rewards to a form that preserves the set of optimal policies. The proposed framework is general enough to capture not only potential-based reward shaping (PBRS) functions, but also reward shaping functions that cannot be written in potential-based form. Indeed, contrary to PBRS, ADOPS allows for reward shaping functions with the property that the intrinsic cumulative returns depend on agent's actions while still preserving the set of optimal policies. The authors evaluate their framework in the Montezuma's complex Atari Learning Environment, which is characterized by very sparse rewards, and show that ADOPS outperforms all other baselines, some of which struggle to make any progress at all.\n\n## update after rebuttal\nI have read the rebuttal carefully and I will keep my score unchanged. The authors have mostly addressed my questions and comments. Something to point out is that the revised proof is based on the concept of a stable policy, and I am not so clear how common such proof strategies are in the RL Literature. Can for instance the authors make any connections (if applicable) to the prior literature? Furthermore, I still feel the proof is not so easy to follow, even though the revised proof is better written.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough feedback, and for the time and energy it took to read our paper in such an in-depth manner. We appreciate your insightful comments, and our resulting edits to the paper have improved it substantially. \n\nWe acknowledge that further work on a wider suite of environments than Montezuma’s Revenge is merited, and are excited to explore this territory in future work: we are currently working to extend our empirical evaluations to other Atari environments for a follow-up work. We limited ourselves to one environment in this work due to time and compute constraints, and chose Montezuma’s Revenge due to its status as a well-tested benchmark known for being extremely sparse and difficult to learn. We’d also like to emphasize, as you’ve pointed out, that ours is a plug-and-play method with theoretical guarantees, and this represents the most complex environment in which such a method has been tested. Additionally, as you note, it would be interesting to apply our methods to shaping rewards other than RND, particularly more recent, SOTA methods such as Never Give Up. We’re excited to do so in future work; we chose RND as a base IM method for its relative simplicity and ubiquity, as a good baseline for demonstrating the initial efficacy of our method. We limited ourselves to one IM method due, again, to ever-present time and compute constraints (particularly here, wherein our experimental setup requires testing each IM method with each plug-and-play method, and so an additional one would almost double our required computational budget). We consider our experimental results in Montezuma’s Revenge to be strong contributions for an initial work, particularly when paired with our theoretical contributions. \n\nWe will next address your comments in the “Theoretical Claims” section in the order that they appear.\n\nWe’ve corrected Equation 38 as appropriate. Thank you for catching this.\n\nWe agree that  $U^{I_{old}} t $ is a somewhat odd notation, and furthermore unnecessary to condense what it is meant to represent at all. We’ve eliminated it entirely, and replaced it with the full text of what it notates, namely $\\sum_{j=t}^{N-1} \\gamma^{j-t}F’_j$ (the return of the “old” intrinsic reward, unmodified by GRM).\n\nWe have significantly updated the text of our proof of Theorem 5.3 for clarity and rigor. We’ve also added a preamble to the full text of it explaining the outlines of the proof. We further explain our modifications to the text of the proof, including more formally-defined assumptions, in our response to Reviewer cdE4. These changes include moving the $P(s’|a,s)$ term to the distribution of an expectation function, thus avoiding the need to include any (initially omitted, as you noted) summation in Equations (35) and (36), among others.\n\nA fully updated version of Section 5.2 is included in the below link, to peruse the changes to this proof at your leisure.\n\nhttps://drive.google.com/file/d/1XTZ3VSuIDFaqHM_NxsjBpQEhkR6DFOyM/view?usp=sharing\n\nThe transition from Equation (29) to (30) is essentially the same as the transition from (24) to (28), except that all the $C_1, C_2, C_3 = 0$, and the $V_E + V_I$ terms do not drop out, as they’re inside a max function rather than an argmax. This was admittedly confusing, and also unnecessary to the flow of the proof. We’ve omitted these equations in the new version, in favor of a more rigorous explanation.\n\nAs for addressing more literature, we’ve added acknowledgements of more recent approaches to Section 2, including Never Give Up and  AIRS (suggested by another reviewer).\n\nThank you again for the review, particularly the kind words about the novelty of our framework and theory; you clearly read the paper very closely and understand what we’re trying to do, and it’s nice to feel “seen.”", "claims_and_evidence": "Overall, I feel that the paper does not make unsubstantiated claims, in the sense that it provides both theoretical derivations as well as empirical evidence for the various claims it makes. That said, I feel that the empirical evidence is limited, as I explain in the next sections. I also have some concerns regarding the theory, which I discuss below.", "methods_and_evaluation_criteria": "The fact that the authors only test their approach against a single environment is a bit problematic. The Montezuma's complex Atari Learning Environment is indeed a challenging environment with very sparse rewards, but results with more environments would have made the various claims more convincing.\n\n- As an example, Random Network Distillation was testing on multiple environments such as Gravitar, Montezuma’s Revenge, Pitfall, PrivateEye, Solaris, and Venture. The recent works by Forbes (cited in the paper) also test on several environments, namely, MiniGrid DoorKey, Cliff Walking, and Longer Cliff Walking. Not all environments are equally interesting, and obviously the authors would want to choose the challenging ones with sparser rewards. My point is simply that one environment does not provide significant evidence.\n\nAs far as the baselines are concerned, I like the fact that the authors have decided to experiment with three of the most recent\npotential-based approaches: PIES, PBIM, and GRM. That said, it is also important to understand how the proposed framework compares against more traditional approaches based on curiosity and intrinsic rewards (even if these do not have theoretical guarantees). Random network distillation is an excellent candidate, but rather old. There are more recent works  like \"\"Never give up :Learning directed exploration strategies\" by  Badia et al. from ICLR 2020. It would have been interesting to see how the proposed framework would compare against the state of the art in intrinsic (but not PBRS) rewards.", "theoretical_claims": "Overall, I feel that the authors have done a good job with the derivations. Some concerns:\n- In (38), I think $F'_t$ should read $F'_j$.\n- In (39), the notation $U_t^{I_{old}}$ locks strange. Why \"old\"?\n- The proof of Theorem 5.3 may be correct, but it is not easy to read. One confusing thing concerns the policy. The authors claim that $\\pi$ is the current policy followed during training. I assume this policy refers to the ADOPS reward, not the original reward. So, essentially the current policy outputs the action it thinks is best in terms of the shaped ADOPS reward. The notation with the Q- and V-functions is also quite confusing, because there is an implicit dependence on the timestep and the policy.\n- Another issue with the proof of Theorem 5.3 concerns Assumption 5.2, which guarantees adequate exploration. I understand the authors need that assumption in the proof of the theorem. But this is still very high-level, and not completely rigorous. It is more of the big idea. I am not sure whether it can count as a formal argument though, but I could be wrong.\n- In (35), (36) and even other equations, the authors do not sum over all possible states $s'$ The Bellman operator should contain the summation over all possible next states though, weighted by the transition probabilities.\n- I was not able to figure out what (29)-(31) show. In particular, how do we go from (29) to (30)?", "experimental_designs_or_analyses": "I did not have any particular concern with the design. The authors made changed some things from the prior literature, like not clipping external rewards, but everything is explained sufficiently.\n\nThe experimental analysis is quite deep, as the authors dive deeper into all methods.", "relation_to_broader_scientific_literature": "The paper pushes the envelope in the reward-shaping literature by proposing the novel Action-Dependent Optimality Preserving Shaping (ADOPS). This framework can unify PBRS approaches; in addition to that, it can incorporate shaping reward that fall outside the PBRS paradigm. I find the framework quite powerful and interesting.", "essential_references_not_discussed": "My main concern regards the literature on Intrinsic Motivation. The authors cite some important approaches, namely, count-based exploration (Bellemare et al., 2016), Intrinsic Curiosity Module (ICM) (Pathak et al., 2017), and Random Network Distillation (RND) (Burda et a l., 2018a; 2019). All these papers are important but not recent. I think the authors could have included some papers from the more recent literature. \n\nThis could also be helpful in relation to the baselines in the experimental section. The authors use RND only from the IM literature, which is rather old. It would be great if they could show that their approach outperforms more recent approaches from the IM literature as well. This could broaden the scope of the work - do the authors want to show that ADOPS just outperforms PBRS approaches, or that it can in fact be competitive w.r.t. recent IM approaches (see also my earlier comment)?", "other_strengths_and_weaknesses": "Strengths\n- The framework is a nice contribution that goes beyond the current PBRS literature. Action-dependent but policy preserving reward shaping is a novel and promising idea.\n- The theoretical derivations are generally done with care.\n- The results on the Montezuma's complex Atari Learning Environment are good, and demonstrate superiority w.r.t. recent PBRS approaches and even RND.\n- The experimental analysis is interesting.\n\nWeaknesses\n- Proof 5.3 is hard to read with confusing notation and some non-rigorous statements.\n- Using a single environment is not as convincing as experimenting with several environments.\n- RND is not a recent approach from the IM literature. It would be interesting to know how this framework compares against more recent state-of-the-art IM frameworks.", "other_comments_or_suggestions": "- It would be nice if the authors could improve the exposition of the proof of Theorem 5.3. It might be helpful to structure the proof in a case-based format, e.g., Case 1: ...., Case 2: ...., etc. Currently, there is a lot of text, but I feel that more rigorous symbols and derivations might improve the exposition.\n- It would be nice if the authors could experiment with more environments and/or recent sate-of-the-art baselines from the IM literature.", "questions_for_authors": "Please address the various concerns.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "COVnGn0dZr", "reviewer": "Reviewer_VPTk", "summary": "The paper focuses on improving performance in complex, exploration-heavy environments with long-duration episodes. In particular, the paper focuses on reward shaping methods that shape rewards while maintaining optimality.\n\nThe paper proposes a new reward shaping approach called Action-Dependent Optimality Preserving Shaping (ADOPS). The paper claims that\n\n(a) ADOPS allows for reward shaping that previous potential-based reward shaping methods do not.\n\n(b) ADOPS allows for intrinsic cumulative returns to be dependent on agents’ actions while still preserving optimality.\n\n(c) ADOPS empirically improves performance over baseline intrinsic motivation in complex, extremely sparse environments where preexisting methods for preserving optimality fail.\n\n## update after rebuttal\nI am happy with the rebuttal. It addressed my major concerns. I think the paper has sufficient evidence for the claimed contributions.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time and effort to review our work. We appreciate your positive feedback.\n\nWe fixed the reference to Equation (41) to Equation (15). Thank you for noticing this error.\n\nWe removed unnecessary use of future tense as you suggested.\n\nEach \"training step’’ is a rollout and subsequent set of gradient updates that occurs every 128 time steps across each of 32 workers. We use the same architecture and training procedure as in the original RND paper (Burda 2019). We’ve updated our appendix to define \"training step’’ more clearly.\n\nWe’ll explain a bit more what we meant when we said Equation 13 entails that \"every action that would be optimal without IM must remain optimal after the addition of the IM.’’ There are multiple extrinsically optimal policies, two of which we can call $\\pi_1$ and $\\pi_2$. These policies, being extrinsically optimal, have equal $\\textit{extrinsic}$ value functions $V_E^{\\pi_1} = V_E^{\\pi_2}$, but that doesn’t necessarily mean $\\textit{ a priori}$ that they have equal intrinsic value functions. If they happen to not have equal intrinsic value functions, then one will be greater than the other, and thus the extrinsically optimal policy with the lower intrinsic value function will no longer be optimal (because there exists another policy that would obtain greater expected value). In order to ensure that this doesn’t happen, and that all extrinsically optimal policies are also optimal intrinsically, we need to assert that their intrinsic value functions (and thus their combined intrinsic+extrinsic value functions) are equal to each other. Admittedly, we had worded this somewhat confusingly, as we reference \"actions,’’ but Equation (13) deals explicitly only with policies. We’ve amended our explanation to say  \"every policy that would be optimal without IM must remain optimal after the addition of the IM.’’ Thank you for bringing this to our attention.\n\nThank you again for your time, effort, and kind words.", "claims_and_evidence": "For claim (a), Theorem B.1 shows that there are are reward shaping functions that previous methods such as GRM cannot use. Moreover, Theorem B.2 shows that the proposed ADOPS conserves the set of optimal policies.\n\nFor claim (b), ADOPS is designed to have action dependent reward shaping and the theoretical proof shows that ADOPS still preservers optimality.\n\nFor claim (c), the paper compares ADOPS and baselines in the Atari game Monte Zuma's Revenge. In this case, using a single benchmark is in my opinion sufficient and a good choice. The results are thoroughly analyzed and explained. Nevertheless, saying that the approach improves performance in more than one experiment (the word \"environments\", plural, is used) is a slight over-claim w.r.t. the empirical evidence and the description should be modified.", "methods_and_evaluation_criteria": "The paper compares ADOPS and baselines in the Atari game Monte Zuma's Revenge. In this case, this makes sense. The paper contains theoretical proofs and the chosen benchmark and the resulting analysis provide detailed knowledge of the methods.", "theoretical_claims": "I did not notice problems with the proofs. However, I did not check the proofs in detail.", "experimental_designs_or_analyses": "The experimental design makes sense. The experimental analysis is of high quality motivating the choice of hyperparameters and other design choices well.", "relation_to_broader_scientific_literature": "The paper provides a novel contribution in the specific domain of reward shaping. The proposed approach shows how to do reward shaping in a more complex action dependent way while maintaining optimality w.r.t. the original reward function.", "essential_references_not_discussed": "To me the references look fine. The paper has a well defined scope.", "other_strengths_and_weaknesses": "The paper is well written.", "other_comments_or_suggestions": "In \"While it would be ideal, it is usually not feasible to implement Equation (41), as it requires an accurate estimate of the optimal value function.\", should (41) be (15)?\n\nIn multiple locations, the paper uses phrases of the form \"We will begin\". These can be rephrased to \"We begin\". The word \"will\" is not necessary.\n\nFigure 1 shows result plots w.r.t. training steps. What does training steps mean here? How many time steps is one training step?", "questions_for_authors": "I did not fully understand the text that says why Equation (13) leads to \"the first of these conditions says that every action that would be optimal without IM must remain optimal after the addition of the IM\". Can you please explain this in more detail?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HuQaUQrlwC", "reviewer": "Reviewer_PXoU", "summary": "This paper presents Action-Dependent Optimality Preserving Shaping (ADOPS), a technique that transforms intrinsic rewards into a format that maintains optimality and enhances the efficacy of intrinsic motivation in the challenging, reward-sparse environment of Montezuma’s Revenge. Additionally, it establishes that ADOPS supports reward shaping functions that are not aligned with potential-based frameworks: whereas PBRS-based methods necessitate that the cumulative discounted intrinsic return remain independent of actions, ADOPS allows these returns to be contingent upon the agent’s actions while still preserving the set of optimal policies.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time, energy, and constructive feedback.\n\nWe agree with your assessments about the quality of our empirical evaluations. Our primary contribution is the initial proposal of ADOPS, as well as our theoretical proofs of both optimality and increased generality over prior methods. Our future work will focus on further empirical evaluation of ADOPS in more environments as well as against other IM methods. See our response to Reviewer 4wwG for a more detailed overview of our reasons for believing that this work stands on its own as a novel and significant contribution.\n\nOur assumptions as originally stated were somewhat stronger than they had to be in order for our proof to function, and our initial discussion around them lacked clarity. In light of your helpful feedback, as well as that of other reviewers, we’ve revised them substantially. We dropped assumption 5.1 and simply adopted the convergence property of the base learning algorithm. Additionally, our previous Assumption 5.2 (now 5.1) requires essentially that the learning algorithm executes locally greedy actions in the policy space, and we describe when it’s introduced why this is a reasonable assumption. We’ve also substantially reworded sections of the proof of Theorem 5.3, for clarity. We’ve attached an anonymous revised text of Section 5.2, so that you can examine these changes holistically.\n\nhttps://drive.google.com/file/d/1XTZ3VSuIDFaqHM_NxsjBpQEhkR6DFOyM/view?usp=sharing\n\nTo generally address your comment about requiring enough data for the critic estimators to converge to their theoretical values: while we’ve altered our assumption here, this critique still touches on an important point we’d like to address. We’re building on a prior line of work in optimality-preserving reward shaping, including (Ng, 1999), (Devlin 2012), and the PIES, PBIM, and GRM frameworks among others, that all are based on preserving the optimal policy set of the underlying environment. The implicit assumption behind this framework is that the agent being trained on an optimality-preserving reward function will converge to an optimal, or near-optimal policy, and avoid the alternative, which is to hack the shaping reward. After all, if the agent being trained does not converge to an optimal policy, or a reasonable-enough approximation of it, then practically, the importance of a shaping function being optimality-preserving is somewhat limited. So some assumption like “the agent will eventually converge to an optimal or near-optimal policy” is implicit in all prior work in this area, even though it’s rarely explicitly stated as such. \n\nOur assumption of critic convergence, both in its current and previous form, is actually somewhat limited compared with this, as convergence of the agent’s policy network (the implicit assumption underpinning prior work in this area) is generally dependent on (and therefore assumes) convergence of its critic network(s). You’re of course right to note that, in practice, finite and biased data is always what we’re working with. To more accurately characterize the convergence property, at the moment we rely on the convergence property of the base learning algorithm as the worst case scenario since ADOPS will produce an optimality-preserved policy. Our experimental results are promising, and show our method’s ability to effectively improve training in a complex, sparse-reward environment. We’re enthusiastic about expanding these results to additional domains and forms of IM in future work.\n\nAdditional responses to your comments/questions, in order:\n\nThank you for your correction about Equation (3); we’ve edited it to read $F_t$ rather than $F’_t$. \n\nWe’ve added an explanation/definition of $\\pi_1$ and $\\pi_2$ below Equations (13) and (14), on your recommendation. These are simply two (potentially distinct) extrinsically optimal policies.\n\n$\\bar{a}$ is an extrinsically suboptimal action for a given state $s$.\n\nThese assumptions you mention (being episodic and/or future-agnostic) are not necessary for our method, and can be violated freely without consequence. This is an important strength of ADOPS that you’re right to note we forgot to keep stressing the significance of about halfway through the paper. To fix this, we’ve added an additional note of our ability to relax these assumptions in the conclusion of the paper. Thank you for pointing this out.\n\nOur use of the phrase “preexisting network critics” is admittedly confusing, and we’ve replaced it in the paper for clarity. We meant “preexisting” just in the sense that these networks were already part of the architecture and algorithm being used, and so using them in our method introduced no additional computational overhead. The critic networks update their parameters throughout training, just like in a standard PPO algorithm.\n\nThank you again for your time and helpful feedback.", "claims_and_evidence": "The evidence provided in this paper vaguely supports the claims made, raising concerns about the robustness and reliability of the findings. More discussion and claims is needed.", "methods_and_evaluation_criteria": "Yes. However, only one environment is tested", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "The key contributions of the paper focus on encouraging agent exploration in sparse-reward environments.", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "Strengths:\nThe literature review is well-executed, and the discussion of prior work is thorough. \n\nThe theoretical foundations appear to be robust, and the experimental results are also commendable.\n\nWeakness: \nThe assumption are quite strong: The assumption requires that the estimator functions receive an unbounded amount of unbiased data from the environment under the current policy. In practice, data is always finite and can be biased due to exploration strategies or environmental nonstationarities. \n\nOnly one test environment is not enough to demonstrate effectiveness", "other_comments_or_suggestions": "Minor: \nEquation (3) should be F_t(s) =γΦ_{t+1}(s')−Φ_t(s) or F'_t(s) =γΦ_{t+1}(s')−Φ_t(s)? However you never define the F' before.\nπ*_1 and π*_2 should be defined in (13)\nwhat is bar{a}? in (14)?", "questions_for_authors": "In the claim you presented, could you clarify the specific assumptions you've set aside, such as the requirement for the environment to be episodic and for the intrinsic motivation (IM) to be \"future-agnostic\"? It appears that these points were not revisited later in the paper. The primary focus of the document seems to be on resolving issues arising from the discrepancy between the action-independent value function and the action-dependent Q-function.\n\nAdditionally, you mentioned \"using the preexisting network critics' estimations of the relevant quantities\"—does this critic remain static, or does it evolve over time as it learns within the ADOPS framework?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nScRr9bBcy", "reviewer": "Reviewer_cdE4", "summary": "The paper proposes a new reward-shaping framework that is action-dependent while preserving the optimal policies. The proposed method can convert any intrinsic rewards that are not optimality preserving to preserve optimal policies. Through experiments in Montezuma's Revenge, the authors demonstrate the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort in giving detailed feedback; we really appreciate it. \n\nWe’re excited to evaluate our method on additional environments in future work, and believe that these initial results stand as a significant contribution, particularly when paired with our theoretical results. See our response to Reviewer 4wwG for a more detailed overview of our reasons for believing that this work stands on its own as a novel and significant contribution.\n\nYou make multiple insightful comments about our theory, and we’ve reworked and rephrased Section 5.2 substantially for clarity and precision in light of them. In particular, we’ve improved the wording of both of our assumptions, which as previously phrased were both more restrictive than necessary, and worded somewhat confusingly. A reworked version of Section 5.2 (our main proof) can be found here, for you to peruse.\n\nhttps://drive.google.com/file/d/1XTZ3VSuIDFaqHM_NxsjBpQEhkR6DFOyM/view?usp=sharing\n\nWe will now address your comments in more detail, in the order that they appear.\n\nFor Assumption 5.1: we want to disambiguate between the two goals of ADOPS/of optimality-preserving reward shaping in general: firstly, speeding training/increasing sample efficiency, and secondly preventing reward hacking by preserving the optimal policy. The latter of these goals is what we prove in Theorem 5.3, and what we require our assumptions for. The former goal then, of speeding training, can still be met (and, empirically is met, better than RND itself, to a statistically significant degree) before the point at which Assumption 5.1 is true. Indeed, RND itself has no such theoretical guarantees of conserving the optimal policy, but has sped up training across a wide variety of domains, at the risk of making the agent susceptible to reward hacking. Our theorem is designed to prevent this reward hacking, while leaving the underlying training-speeding qualities of the base IM as unchanged as possible ($F^2=0$ very frequently on any given timestep).\nWe have removed the assumption 5.1 and adopted the convergence property of the underlying algorithm. Since the ADOPS ensures that the shaped reward will produce a consistent policy with the extrinsic reward, the learning algorithm would share its convergence property of using the extrinsic reward in the worst case scenario. \n\nWe have changed our Assumption 5.2 to be much more specific and limited of an assumption. Namely, it defines a notion of “unstable” policies, which are those for which an extremely similar, locally better policy exists, and so which any competent learning algorithm will quickly leave in favor of a better policy. It’s detailed more precisely in the attached document above, and we believe it to be much improved in both rigor and scope to the original assumption.\n\nWe’ve added the baseline you reference to our related work section, and are excited to test against this (and other IM baselines) in future work. We’ve also rewritten Theorem 5.3, in a way that clarifies many of the derivations and gives an intuitive overview at the beginning, and signposts throughout.\n\nAs for your questions:\n\nWe have substantially reworked our assumptions, and given some sense of what were to happen were they violated.\n\nYour question about the variable dependence of $\\gamma Q_{It+1}$ is valid, and brings to light the needless complexity of our previous notation. $\\gamma Q_{It+1}$ simply represents all components of $Q_{I}$ that come from a timestep later than $t$. This is equivalent to, and can be more simply written as, $\\gamma V_{I}(s’)$. We in fact rely on this equivalence in our paper, in the step between Equations (26) and (27). For clarity, we have replaced all instances of $\\gamma Q_{It+1}$ with $\\gamma V_{I}(s’)$. This depends, as you might imagine, on $s’$.\n\nThank you again for your in-depth comments and suggestions; we believe that incorporating them has substantially improved our paper.", "claims_and_evidence": "The proposed method can be supported by its theories but not sufficient enough by its experiments since only one environment is tested.", "methods_and_evaluation_criteria": "The proposed method makes sense that the classic PBRS is indeed a sufficient not necessary condition for preserving optimality after shaping. However, the evaluation criteria are a bit less convincing that the method is only evaluated in one single environment.", "theoretical_claims": "Under the assumptions, the overall proof seems legit since I haven't checked every step in detail. But those assumptions look way too strong to be realistic. \n- For assumption 5.1 which assumes the neural network estimates of the values are the true values. As the authors claim, if trained long enough, it will converge to true values, but this already hinders the initial motivation of using reward shaping - to train agents sample efficiently. \n- For assumption 5.2, if we already assume sufficient exploration of all possible actions in every state vistable by Sn, why do we even need intrinsic motivations? In other words, the intrinsic motivation is designed to motivate the agent to explore possible actions/states. Having this assumption renders intrinsic motivations useless.\n- Follow up on assumption 5.2, can you define formally the set of Sn? If we assume sufficient exploration of the action space for every policy, is it the case that Sn will be the same for everyone?", "experimental_designs_or_analyses": "The experiment results on Montezuma's Revenge, while being good empirical evidence for the proposed method, might not be sufficient enough to convince the broader community. There are many other hard-to-explore environments. For example, a more basic giant grid world maze could suffice. Extending such a grid world to a continuous maze is also interesting to see.", "relation_to_broader_scientific_literature": "The paper extends the PBRS framework by adding action-dependent terms.", "essential_references_not_discussed": "The following baseline in intrinsic motivation works should be included for a fair comparison,\n- [Automatic Intrinsic Reward Shaping for Exploration in Deep Reinforcement\nLearning](https://proceedings.mlr.press/v202/yuan23c/yuan23c.pdf) in ICML 23 and other baselines included in this paper.", "other_strengths_and_weaknesses": "- The writing could be improved in the sense that (1) the introduction and background on reward shaping are overly extended, and (2) a more intuitive explanation and examples could be used to illustrate the correctness of theorem 5.3", "other_comments_or_suggestions": "N/A", "questions_for_authors": "- Is it possible to have the same results without assumptions 5.1, 5.2? If possible, could you characterize the error your approach could induce under imperfect value estimates and imperfect state/action visitations?\n- In your proposed shaping functions, what is the input to $Q^*_{I,t+1}$? Is it the state action pair in the next time step? If so, how should we have access to it when we are still calculating the reward for $s_t,a_t$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This submission has received four expert reviews with all reviewers acknowledging the authors' responses. There is a consensus among the reviewers that the proposed reward-shaping method (ADOPS) unifies and extends previous approaches in the reward shaping literature. The reviewers found the paper generally well-written and the evidence that supports the claims in the paper convincing. Importantly, several of the reviewers' concerns/misunderstandings were addressed/clarified during the rebuttal. Among the remaining concerns, the most important is the limited experimental evaluation in different environments. This is a rather significant concern which in this case is countered by the superior performance of the proposed method against a wide range of baseline reward shaping methods in the particularly thorny (due to the scarcity of rewards) Montezuma's revenge environment. While this is enough to recommend acceptance, it limits the potential of the paper for a stronger recommendation. 

Going forward, I strongly encourage the authors to include the insights/limitations and key points from the discussion with the reviewers (the updates in the theoretical assumptions and theoretical proofs are much appreciated) in the final version of the paper as this will considerably alleviate similar concerns for the paper's readership.
Decision: Accept (poster)