BAMDP Shaping: a Unified Framework for Intrinsic Motivation and Reward Shaping
Authors: Aly Lidayan
Michael D Dennis
Stuart Russell
Venue: ICLR 2025 Poster (2025)
Keywords: Reinforcement Learning Theory
Bayesian Reinforcement Learning
Intrinsic Motivation
Reward Shaping
Reward Hacking
Primary area: reinforcement learning

Abstract: Intrinsic motivation and reward shaping guide reinforcement learning (RL) agents by adding pseudo-rewards, which can lead to useful emergent behaviors. However, they can also encourage counterproductive exploits, e.g., fixation with noisy TV screens. Here we provide a theoretical model which anticipates these behaviors, and provides broad criteria under which adverse effects can be bounded. We characterize all pseudo-rewards as reward shaping in Bayes-Adaptive Markov Decision Processes (BAMDPs), which formulates the problem of learning in MDPs as an MDP over the agent's knowledge. Optimal exploration maximizes BAMDP state value, which we decompose into the value of the information gathered and the prior value of the physical state. Psuedo-rewards guide RL agents by rewarding behavior that increases these value components, while they hinder exploration when they align poorly with the actual value. We extend potential-based shaping theory to prove BAMDP Potential-based shaping Functions (BAMPFs) are immune to reward-hacking (convergence to behaviors maximizing composite rewards to the detriment of real rewards) in meta-RL, and show empirically how a BAMPF helps a meta-RL agent learn optimal RL algorithms for a Bernoulli Bandit domain. We finally prove that BAMPFs with bounded monotone increasing potentials also resist reward-hacking in the regular RL setting. We show that it is straightforward to retrofit or design new pseudo-reward terms in this form, and provide an empirical demonstration in the Mountain Car environment.

Published as a conference paper at ICLR 2025
BAMDP SHAPING: A UNIFIED FRAMEWORK FOR INTRINSIC MOTIVATION AND REWARD SHAPING
Aly Lidayan, Michael Dennis, Stuart Russell University of California, Berkeley (dayan, chael dennis, russe 1) Jêcs werkeleryyyy edu
ABSTRACT
Intrinsic motivation and reward shaping guide reinforcement learning (RL) agents by adding aseudo-rewards, which can lead to useful emergent behaviors. How- ever, they can also encourage counterproductive exploits, e.g., fixation with noisy TV screens, Here we provide a theoretical model which anticipates these behav- iors, and provides broad criteria under which adverse effects can be bounded. We characterize all pseudo-rewards as reward shaping in Bayes-Adaptive Markov De- cision Processes (BAMDPs), which formulates the problem of learning in MDPs as an MDP over the agent's knowledge. Optimal exploration maximizes BAMDP state value, which we decompose into the value of the information gathered and the prior value of the physical state. Psuedo-rewards guide RL agents by re- warding behavior that increases these value components, while they hinder ex- ploration when they align poorly with the actual value. We extend potential based shaping theory (Ng et al. 1999) to prove BAMDP Potential-based shaping Func- tions (BAMPFs) are immune to reward-hacking mizing composite rewards to the detriment of real rewards) in meta-RL,, and show empirically how a BAMPF helps a meta-RL agent learn optimal RL algorithms for Bernoulli Bandit domain. We finally prove that BAMPFs with bounded mono- tone increasing potentials also resist reward- reward-hacking in the regular RL setting. We show that it is straightforward to retrofit or design new pseudo-reward terms in this form, and provide an empirical demonstration in the Mountain Car environment.
(convergence to behaviors maxi-
INTRODUCTION
A common approach to guiding RL agents in sparse reward settings is to add pseudo-rewards to the true rewards. A wide range of pseudo-rewards have been used successfully complex environ- ments (Pathak et al.) 2017 Berseth et al.) 2019 Hafner et al.)
2023); ;; more domain aagnosii terms
are typically known as intrinsic motivation (IM) while reward shaping is often more task specific
(Schmidhuber 1991: Dorigo & Colombetti 1994 Barto al. 2004). However, designing them is challenging, and they can affect performance in counter-intuitive ways leading to degenerate be- haviors (Taiga et al., | Clark & Amodei 2016). For instance, rewarding accurate prediction of the next percept may cause an agent to sit forever in front of a blank wall (Rhinehart et al.) (021)) while favoring states where the next percept is hard predict causes an agent to get stuck watching a "noisy TV" that randomly flips channels, rather than encouraging exploration as one might expect (Burda al. 2018)
Avoiding these behaviors requires understanding their root causes. We approach this by analyz- ing pseudo-rewards within a theoretical framework for how rational RI. agent should behave- the Bayes-Adaptive MDP (BAMDP) (Bellman & Kalaba 1959 Martin 1967). a generalization of Bayesian bandits (Gittins) 1979). In a BAMDP, the agent starts out not knowing what MDP it is operating in and learns more through experience. BAMDP states consist of the cumulative infor- mation gathered, i.c., the entire history ht of MDP states, actions, and rewards observed up to and including the current state of the MDP. An RL algorithm can be viewed BAMDP state to an action that updates it (Duff, 2002), and optimal RL algorithms maximize the expected BAMDP return, i.e., the expected return while exploring and learning.
policy mapping the

---

Published as a conference paper at ICLR 2025
Proxim
State Coverage
State Coverage
State Coverage
Veluu
-0.5
-1.0
(a) ((s) = --1l ||s gll.. (b) ((h) Hs h)1, i.e., the count of all unique states visited far. Over i.c., the goal proximity. training, the agent must get further from so reach states and increase ((h).
the MDP state (PBSF,[a)) [T], and BAMDP state (BAMPF.(Tb) Start and goal MDP states 80, are marked white and green; other states are colored by the pseudo-reward for transitioning there directly from so at the start of the episode. Each episode ends and is reset to So every 50 steps, 0.99.
Figure 1: Example potential-based reward shaping functions 7d' db for potentials
Within this framework, we can understand both reward shaping and IM as BAMDP reward shaping, i.e. functions over BAMDP states, that guide exploration by incentivizing behavior that leads to more valuable BAMDP states. We decompose BAMDP state value into the value of the total infor- mation collected (VOI) and the value of the current MDP state under the prior, which we call the value of opportunity (VOO). This yields a new, principled typology of pseudo-reward terms based on the different types of BAMDP value that they signal. Many IM terms, c.g., prediction error (Pathak ctt al. 2017) or information gain (Houthooft et al., 2016), can be understood as incentivizing ex- ploration by adding rewards to behavior that increases VOL. Other pseudo-rewards attempt to steer exploration by compensating for incorrect implicit VOO priors resulting from the initialization of RL algorithms. For example, goal proximity reward shaping (Colombetti et al. 1996) compensates for overly pessimistic VOO priors for states near the goal, while surprise minimization IM (Berseth) al. 2019) and joint angle violation penalties (Ji al., 2023) compensate for overoptimistic VOO estimates for risky states. We can furthermore understand how pseudo-rewards mislead exploration as resulting from aligning poorly with actual value-e.5 e.g., watching a noisy TV yields high prediction error but no valuable information.
Next, we prove conditions under which pseudo-rewards cannot be "hacked" (where RL agents con- verge to final behaviors that maximize composite rewards to the detriment of the real rewards) in both RL and meta-RL settings. Potential-Based reward Shaping Functions (PBSFs) take the form r0((s) <ds), where potential & encourages going to higher value states by encoding their desir- ability, c.g., Fig. PBSFs on the BAMDP state (BAMPFs), e.g., Fig. [b] may encode desirability of both the physical state and the total information gathered. Since they may depend the entire training history, it easy to convert most pseudo-rewards to BAMPFs. We extend results from Ng et al. (1999) to prove that BAMPFs always preserve the optimality of RL algorithms. Thus, can use BAMPF's to guide meta-RL without it converging on RL agents that are optimal for the modified rewards but the underlying domain. We empirically validate this by using BAMPF guide meta-RL agent to learn an optimal RL strategy for a Bernoulli bandits domain. Next, we return to the regular RL setting and prove that BAMPFs based on potential functions that are bounded and monotone increasing will also preserve the optimal MDP policy at convergence, i.c., no RL algo- rithm can find a hackkdg MDP policy maximizing shaped return but not real return. It still straightforward to convert many peeudo-rewards into this form, which we illustrate with case-study converting Curiosity (Pathak et al. 2017) to combat the Noisy TV problem. We finally demonstrate the practical utility of our framework in larger-scale RL experiment. We use the BAMDP value decomposition to inform the design of an effective potential function for the continuous Mountain Car environment (Brockman et al. 2016), and show that the resulting BAMPP improves exploration while avoiding reward-hacking.
BACKGROUND
2.1 MARKOV DECISION PROCESSES
Markov decision processes (MDPs) are defined by tuple M = (S, with S set of states, A set of actions, T(s ls, a) and R(r]s, a, s') transition and reward probability functions with expected reward R(s, a, s'), To (s())) an initial state distribution, and 7 discount factor (when it is
2

---

Published as a conference paper at ICLR 2025
not critical, write R. without s' for brevity). MDP policies map from current states to distributions over next actions: π (als).. The return is defined as the discounted sum of rewards G = -i= T and optimal policy 't" maximizes the expected return.
2.2 INTRINSIC MOTIVATION AND REWARD SHAPING
Intrinsic motivation (IM) and Reward Shaping are methods for guiding RI. algorithms by adding pseudo-rewards to the original reward at each step. IM functions F(hx) can depend on the en- tire history fü2 IM can depend on RL algorithms' internal states, and in general the composite reward function R(s,, at, St-1) ) + F(h(41) ) is not valid MDP reward function. Reward shaping functions are restricted to the form ((), resulting in shaped MDPs with reward function R' R'(s, a, a,s') R(s, a, 8') + F(s, a, s'). Optimal policies for a shaped MDP, i.e. maximizing composite return, are generally not optimal for the original MDP. Potential-based shaping functions (PBSFs) take the form F(s, s') = r0(s') ( ((s) and preserve optimal policies in all MDPs (Ng et al. 1999).
50000181...tt-11333 (the sequence of all transitions observed so far), thus
2.3 FORMULATION OF RL PROBLEMS AS BAMDPS
We formulate RL problems as BAMDPs, for which RL algorithms are policies. We use overlines, e.g., M, to denote the BAMDP version of any object. Our conventions are inspired by Zintgraf et al. (219)) and Guez et al. (2012).
RL algorithms lear to maximize return in MDP by repeatedly updating internal state (e.g., a Q-function estimate) while selecting actions and receiving observations. We denote them by S H + A, where H is the set of histories h, that are realizable, i.e., occur with non-zero probability for some action sequence (Abel et al. 2024). RL algorithms typically maintain a lossy memory of h, but it is sufficient statistic for internal state, encapsulating all information ă might use to choose actions. We measure the performance of æ in MDP M by its expected return while learning: JAs (T) = EM, |Σ 7 R( 4t) Bayes-optimal RL algorithm maximizes expected performance in MDPs sampled from prior p (M), i.e., ( = Ep(M) JT (#) (Singh et al. 2009). The prior represents the domain, i.c., the distribution of MDPs that the agent will encounter (c.g.. MiniGrid mazes Snevalier-Boiiverr
al., 2023) or Atari games). For clarity of exposition, we assume all MDPs possible under p(M) ) share the same A, y, so only R. T, are initially uncer- tain We use p(M)h,) to denote the posterior after updating p(M) the evidence in history h4, i.e., p( ( hha) x
A BAMDP is thus defined by tuple M = (8,A, R, R,T,To,77) where:
To,7)
state space, each state (st, ht)- A and are shared with the underlying MDPs, although internally म may sample its actions from an MDP policy ne that it learnt, i.e., # (a|s:) )) = Te (a(ss))
$ S x H. i.e., an
R(5e, a) = EporIA.) (R(s,, a)). the expected reward under the current posterior.
T(5 ax) Ep(ass,) (T az) R( [hh-1 haar7(41442l)
To((so, ho)) = (To))))T((())))) (ho = so]-
We illustrate the basic concepts of BAMDPs using the caterpillar domain shown in Fig. 2 Here, p( (M) represents how butterflies usually lay eggs on the best food source in the area, but 10% of the time a more rewarding source is nearby; upon hatching on the weed, the caterpillar does not know which MDP in and must decide whether exploring the neighboring bush worth the energy and opportunity cost. The bush's reward varying across possible MDPs manifests stochastic BAMDP dynamics at the transition where the caterpillar first observes it (c.g.. taking the highlighted ear action). After observing the reward, p(M] h2) collapses to the underlying MDP and all dynamics become deterministic (c.g., at the transitions with red highlighted arrows).
We convert settings with episodic environments train/test regimes to this form hy augmenting the state space, e-g., by adding within-episode step indices or train/test indicators.
"This formulation can be extended to POMDPs and for distributions over S. A.A. without any conceptual changes-the agent receives observations o,, and expectations are taken over additional variables as needed.
3

---

Published as a conference paper at ICLR 2025
W $ D
P(.))=011
p(M.)=0.9
w b
history h
90
w b D
BAMDP state s
150
PX0.1
8b
150
w&W W
MDP s state
21
W wdbAb
150
Figure 2: The caterpillar domain formulated as a BAMDP. Left: prior p(M) is a categorical distri- bution over MDPs M, and M2; both, all transitions are deterministic, with the curved and straight arrows corresponding to eat and go actions respectively. The caterpillar hatches at state Sw, and must decide whether to eat for guaranteed reward 21, or incur -5 reward to go to 8b. Right: truncated BAMDP transition diagram, arrows are labeled with rewards (and transition probabilities if p < 1). The stochastic transitions (from the highlighted eat action) are due to the uncertainty over the MDP; all future transitions (the highlighted arrows) become deterministic once its identity is revealed.
The expected return an RL algorithm in a BAMDP is equal to its expected return while learning in the initially unknown MDP M p(M):
[+]
BI.T
rs R(5,, ((x))
Ep(M)
EM
Σ
R. R(st, [560)] ExCMy [TM([)] = [
Thus, an optimal policy for the BAMDP #* maximizing E. [G], a Bayes-optimal RL algorithm with respect prior p(M)) i..., it explores optimally for that domain | Since E, [G] is calculated through future information states, Æ* must plan through its own learning. E.g., in Fig. 2 with large enough y, #* would deem 86 worth exploring because it stay there if it finds food, otherwise it will learn that 86 is empty and use this knowledge to return to 8w and never leave again.
PSEUDO-REWARDS CORRECT BAMDP VALUE MISESTIMATION
We first use our framework to explain how IM and reward shaping can incentivize effective explo- ration by signalling the value of BAMDP states.
3.1 THE RELATIONSHIP BETWEEN VALUE MISESTIMATION AND REGRET
RL algorithms typically act, implicitly or explicitly, to maximize a value prediction estimated from the history, which we denote by @ a). Applying the performance difference lemma (Kakade & Langford 2002) the BAMDP level shows how algorithmic regret is directly related how these estimates differ from the Bayes-Optimal value over their trajectory:
Lemma 3.1. The Bayesian regret (Ghavamzadeh et al. 2015) of algorithms acting on estimate (5 a) can be expressed as:
Ex [G| - Ex G = Ex
E - Q' (5,, as, arg max, ((L
Thus, if can add pseudo-rewards that nudge the value estimates of RL agents à such that they select actions with higher BAMDP value Q", they will explore more optimally.
"Note that, since Bayes-opting RL algorithms explore only when expected to increase return, they don't always explore enough to converge on exactly optimal MDP policies n² E.g., in the caterpillar domain. if is small enough then immediate reward dominates F, (G], 5" eats at sw rather than risking delaying rewards by checking & (sce Appendix I. for full calculations).
4

---

Published as a conference paper at ICLR 2025
3.2 BAMDP VALUE DECOMPOSITION
We can now understand the role of pseudo-rewards as directly incentivizing RL agents to go to more valuable BAMDP states. IM terms that reward novel observations or diverse actions encode the value of the information in the BAMDP state hy; these are popular because commonly used RL algorithms do not inherently account for the value of information (see Appendix C.. RL agents can also misestimate the value of physical states due to incorrect initial beliefs; many other pseudo- rewards compensate for this type of misestimated value, typically when there is significant prior knowledge about how to maximize rewards, e.g., it is advantageous for a ball-dribbling robot to be closer to the ball (Ji et al. 2023). This helpful to express as a pseudo-reward because it can be difficult to program such prior knowledge into non-tabular (e.g., deep RL) algorithms before they begin learning. We decompose the BAMDP value function into these two values, which we call the Value of Information and Value of Opportunity, respectively.
Definition 3.1 (Value of Information). The Value of Information (VOI) from state & is the increase in n expected return from 8 due to the information in hy compared to its initial beliefs:
Vi (st, he)) (((e,, hu)) - ((s,,,,))))
E.g. ht after watching TV may contain more information than he. but Vi* would be zero if that information can't help #* get higher return. Meanwhile, exploring new section of maze, even if it had no rewards, lets म focus its search on a smaller remaining area, so Vi would be positive.
Definition 3.2 (Value of Opportunity). The Value of Opportunity (VOO) from state 3, is the expected optimal value of state without having learnt anything, i.e.:
(o h₂)) = ((s,, ho).
(3)
E.g., if there is guaranteed reward at a known goal state 8g. then 8 that are fewer steps from it have higher VOO. Conversely, if walking near an icy cliff edge always has a high chance of injury, then s there have lower VOO.
Lemma 3.2 (BAMDP Value Decomposition). The optimal BAMDP value can be decomposed into the Value of Information and the Value of Opportunity:
V ((see ha)) = Vj h()), + Vo((st,h)).
(4)
We can now categorize IM and reward shaping terms by which of these components they signal (see Table T.. We can also understand the failure of pseudo-rewards to effectively guide RL algorithms as result It of them aligning poorly with the true BAMDP value. For example, negative surprise (Berseth) ct al. 2019) signals the prior knowledge that unpredictable parts of the environment have lower Vo- This is well-aligned for environments with dangerous dynamics, but fails in safe environments where unpredictability correlates poorly with negative outcomes, causing agents to stare at wall rather than exploring (Rhinehart et al. 202T). Meanwhile, entropy bonuses (Szepesvári) 2010 Mnih] 2016 Haarnoja al. 2017) signal that more VT can be gained by trying a wider spread of actions. This breaks down if the scale of the pseudo-rewards is too high, because overly random behavior is unlikely to reach interesting novel states. Thus, the bonuses must be carefully balanced with the scale and frequency of the extrinsic rewards (Hafner et al. 2023). See Appendix B for more in-depth discussion of these and more examples.
4 PRESERVING OPTIMALITY WITH BAMDP POTENTIAL-BASHR SHAPING
Section 3 provides principles for designing pseudo-rewards to guide effective exploration towards states of increasing BAMDP value. Another important desideratum for pseudo-rewards is that they do not prevent RL agents from converging on good behaviors once exploration is complete. As our algorithms become more powerful, they may get better at finding "reward- hacking" behaviors that maximize shaped rewards to the detriment of the underlying rewards we care about. This can be avoided by using pseudo-rewards that preserve optimality, i.c., guarantee that any behavior maximizing shaped rewards also maximizes underlying rewards. Using our framework, we define form of pseudo-reward which makes it easy to retrofit aseudo-reward functions, or design new terms, which preserve optimality: BAMDP Potential-basee shaping Functions (BAMPFs). We prove that the use of BAMPFS can avoid reward- hhackig in both RL (i.c., optimizing over MDP policies) and meta-RI. (i.e., optimizing over RI. algorithms) settings.
5

---

Published as a conference paper at ICLR 2025
Table 1: Typology of IM and reward shaping terms based on the value components (Value of Infor- mation Vi and Value of Opportunity Vo) they signal. Attractive signals increase with measures of underestimated value, and repulsive signals decrease with metries warning of overestimated value.
No Vö Signal
Repulsive Vo Signal
Attractive Vö Signal
Attractive
Prediction error (58
10
Empowerment
Optimism bonus 74 60)
Vi Signal
Count-based (6 10
43 43:30
30
Entropy bonus 77
Information
Capture
Subtask unlocking (34)
Skill discovery 770
(61
Info gain (36
No
V7
Surprise minimization
Goal proximity (56
Signal
Subgoal reaching
Information cost (22
(59)
75
Joint angle violation
Ball possession
(39
penalty (39)
4.1 DEFINITION OF BAMDP POTENTIAL-BASED SHAPING FUNCTIONS
Classic potential-based basee shaping guides RL agents toward more valuable MDP states by encoding their desirability with the potential function ((s) (e.g., Fig. where ((x) is the proximity to the goal state). A BAMDP Potential-Based Shaping Function (BAMPF) can guide RI. agents by encoding the desirability of BAMDP states Φ(5) (or equivalently, (())). This allows them to signal not only the MDP state value (i.e., VOO), but also the value of the information accumulated (VOI), encouraging exploration to gather valuable experiences.
Definition 4.1. (BAMPF) Let any S,A. be given. Function F' is a BAMDP Potential-Base Shaping Function if there exists a real-valued function & such that for he E H (ho).
F(h+) 7a(h)) - -0(h-11,,
where h is the first timesteps of h4- See Fig. 1b for example of simple BAMPF based on the size of the set of MDP states visited in h.
E.g., Information Gain (Houthooft et al.) 2016) expressed as the decrease in entropy of agent's belief of the MDP dynamics p(T"), i.c., H (p(T)) for y = with ((h) -)) i.c., the certainty of the posterior belief after updating on h, encouraging exploration towards states where the agent knows more about the environment. Due the expressivity of á is straightforward to convert virtually any IM or reward shaping function to BAMPF: take whatever measure of the desirability of the information and/or MDP state that is based on, and use that measure as
H (b(T)):)) can be viewed as BAMPF
4.2 BAMPFs PRESERVE OPTIMALITY IN META-RL
We first consider the use of BAMPFs for guiding meta-RL systems to discover better RL algorithms more efficiently, without misleading them converge suboptimal reward-hacking behaviors. In this setting, the meta-learner generates RL algorithms 7y. updating 0 to maximize Fg 's expected performance in MDPs sampled from p(M), with the goal of eventually meta-learning Bayes- Optimal म* Pseudo-rewards can be added to shape the returns the meta-RL agent observes, guiding to generate better ng. F.g.,, entropy bonuses could encourage generation of सy that explore wider range of actions. But if the pseudo-reward doesn't 't preserve optimality, it could cause the meta- learner to converge on a म. that explores badly with respect to the true task distribution. We extend PBSF theory to prove BAMPFs preserve optimality in BAMDPs, i.c., in meta-RL problems.
4.2.1 BAMDP POTENTIAL-BASE SHAPING THEOREM
We model the effect of pseudo-reward function F(h)) as producing shaped BAMDP M' with shaped reward Rs, a, 1)41) = R(3,, a) + F(h-1)., while S and are unchanged, i.c., h, still only con- tains the underlying rewards. This reflects the fact that F F(h.) is fully known from the start, it

---

Published as a conference paper at ICLR 2025
Winnrr Pulls BAMPF
None
Winnrr Fulls
1se Winner Pulls BAMPS
None
1st, Winner Pulls
1.8
3.5
1.7
Arms
1.6
2.5
1.5
2
Myy W
1.5
1.4
Max
1
1.3
# Algorithm Updates
1k
1k 2k
(a) Average regret the learnt RL agents as they are updated through meta- learning.
(b) Average number of arms the leamt agents try in each MDP throughout meta-lcarning.
The effect of reward shaping on A2C meta-learning an ENNN-bsse RL agent for Bernoulli Bandits with two arms, reward probabilities (0.1, 0.9) and a budget of 10 pulls. The mean and stan- dard error of 10 seeds are plotted for each condition. Without shaping. the meta-learner gradually learns to generate RL agents that try fewer arms on average, avoiding over-exploration (grey curve in 3b). The Ist Winner Pulls BAMPF (green) sets o to the pull count of the first arm that yielded a reward, helping A2C learn to exploit and achieve lower regret more quickly, while still converging to the optimal strategy. However, when this pull count is used directly as a pseudo- reward (1st Winner Pulls, purple), it causes the meta-learne to converge on an agent that over-exploits.
Figure 3:
should not be treated as information or influence the posterior. The RL algorithm observes the under- lying rewards in h,, while only the meta-learner receives the pseudo-rewards in this setting. An opti- mal algorithm for M' maximizes the expected shaped return from R', i.e., म" = arg max; E G').
We now state our main theorem that BAMPFs always preserve Bayes- Soyyes-Opimmalit..
Theorem 4.2 (BAMDP Potential-Be -aase Shaping Theorem). For a pseudo- reward function to guar- antee that the optimal algorithm for any shaped BAMDP is optimal for the original BAMDP, i.e., Bayes-optimal for the underlying RL problem, it is necessary and sufficient for it to be a potential- based shaping function on the BAMDP state.
Proof Sketch. For sufficiency, we show that the & form a telescoping sum, reducing to a constant.
For necessity, we construct a BAMDP such that when F - (70² Φ) is nonzero, different actions maximize the shaped and extrinsic returns. The proof follows Ng et al. (1999) but rewards impact the BAMDP state, making it more complex than for regular MDPs; see A.I for full proofs.
Thus, if the meta-learner converges to an RL algorithm #* that learns optimally for the BAMPF- shaped rewards, this algorithm will also always explore optimally with respect to the true reward distribution. Meanwhile, we use pseudo-reward function that is not BAMPE, there will be settings where n" explores sub-optimally. We extend this result to prove that BAMPFS also preserve approximate optimality of RL. algorithms in Appendix A.2
4.2.2 EXPERIMENT: SHAPING META-RA -L ON BERNOULLI BANDITS
We demonstrate this result in the Bernoulli Bandit meta-RL problem introduced by Wang et al. 2016). Every MDP in p(M) has two arms, one with reward probability 0.1 and the other 0.9 (randomly assigned), and a budget of 10 pulls. At each step an RNN-based RL agent observes the last arm that was pulled, its payout, and how many pulls it has left, and chooses which arm to pull next. After 10 pulls, the episode ends and a new MDP is sampled from p(M). The meta-RL algorithm, A2C
2016), continually updates the RNN agent maximize expected return in its 10-step lifetime, i.e., to find the RL strategy that optimally balances exploration and exploitation with respect to p(M). ). Fig. 3bb shows how without shaping (the grey curve), the meta-learner gradually learns to generate RL agents that try fewer arms average, i.e., avoiding over-exploration. This shows that the meta-learner initially ever-estimates the VOI of trying more arms, so we could add BAMPF to correct its prior. The 1st Winner Pulls BAMPF sets @(h) to the total pull count of the first arm that produced a reward, decreasing the relative perceived VOI of exploring the other arm. Fig. 3b (green curve) shows it helps A2C learn more exploitative RI agents more quickly, and

---

Published as a conference paper at ICLR 2025
Fig. Balsha shows that these agents achieve lower regret more quickly, while it doesn't 't prevent eventual convergence to an optimal agent. In contrast, when this pull count is used directly as a pseudo- reward (purple curve). it causes the meta-learner to converge
agent that exploits too heavily and never achieves the optimal regret, because whenever the = 0.1 arm is by chance the first winner, the shaped return is maximized by continuing pull it, regardless of its future payouts. See Appendix for full experimental details.
4.3 PRESERVING OPTIMALITY IN RL WITH BAMPFS
Now we turn our attention to the common RL setting, where an RI. algorithm learns an MDP policy to maximize return. A certain natural type of BAMPF also resists hacking at the MDP level. These are BAMPFS based on & that are bounded monotone increasing functions over time, i.c, @hh,,) S ((h,,) for all realizable histories at training steps t < t2 (so he, is prefix of hz2).
Theorem 4.3. If the pseudo-rewards added to an MDP can be expressed as a BAMPF with a bounded potential that is monotone increasing over time, it will eventually preserve approximate optimality in the MDP, i.e.
Ve 0 3H H: B, Bx
(6)
where L is the training step, E. [G] denotes expected unshaped return of an MDP policy n, bh is policy maximizing the shaped return at step t, and π² is an optimal policy for the undertying MDP
Proof Sketch. The BAMPF rewards form a telescoping sum over any MDP episode, leaving a single policy-dependent term: é at the final step of the episode. Because @ is bounded and monotone, there must be a final step in training H where it increases by at least c, after which the artificial advantage it can give the chosen policy is less than Therefore the optimal policy in the shaped MDP must be less than e worse than the optimal policy in the true MDP. See Appendix A.3 for the full proof. 11
This class of BAMPF naturally includes intrinsic motivation terms that signal the total value of information gathered so far, e.g., count- based rewards (Bellemare et al. (016) or information gain (Houthooft et al., 2016), and they are simple and intuitive to design. For example, take a single-state MDP with 100 levers only one of which yields reward when pulled. A bounded mono- tone á could be the number of unique levers tried so far, encoding the VOI from having explored more levers. Fig. 4al shows how, when applied to DQN, the BAMPF reward converges to constant as more levers are tried. Fig. 4b shows how this BAMPF causes the agent to try more levers on average than without pseudo-rewards (which relies purely doesn't tt prevent DQN from converging to the optimal policy, i..., pulling the correct lever at every step (Fig. 4c). Meanwhile, an entropy bonus (the entropy of the last 10 lever pulls, which isn't BAMPF) makes the agent oscillate between pulling the correct lever to get the extrinsic reward, and pulling other levers increase the entropy bonus, which achieves higher shaped rewards but lower true rewards than pulling the correct lever at every step.
e-rredyy exploration). And yet, it
4.3.1 EXPERIMENT: SHAPING RL IN MOUNTAIN CAR
We now demonstrate the benefits of BAMPFs in a more realistic setting: with PPO (Schulman et al. (017) in the Mountain Car environment (Brockman et al. 2016) which has a continuous state comprising the car's position and velocity. The reward is -1 at each timestep; each episode lasts 200 steps or ends early if the car reaches the goal. The car starts in a valley, and to reach the goal (the flagpole in Fig. Sap it must build momentum by first moving up the opposite slope. Thus, displacement from the lowest point in the valley is an intuitive shaping reward to signal the VOO of being further uphill in either direction. We find this helps PPO reach greater displacements early in training (red curve in Fig. Fig. but eventually results in reward-hacking policies that collect more pseudo-rewards by avoiding the goal (Figures 5b and 9). Converting this to classic potential-based shaping by setting d(s) to the displacement, we find it preserves optimality but doesn't help learning (blue curve in Fig. 5b). possibly because the further uphill the car gets, the more negative PBS rewards it soon receives when it rolls back. We can understand these failures as a result of the fact that displacement is too weak signal for the true VOO in Mountain Car. Instead, we could signal VOI by rewarding the maximum displacement so far, which doesn't penalize temporary decreases in displacement. This depends more than the current state, it isn't valid MDP potential
8

---

Published as a conference paper at ICLR 2025
Entropy
BAMPF
None
Entropy
BAMPF - None
Entropy
BAMPF
Nore
Prcudo reward valure
Unique lever pulls
Correct lever pulled?
60
0.8
15
10
MMp MMw.mmm
40
0.6
5
0.4
20
Step
Step
AALM MA
100 200
300
400
100
200
300
400
100
200
300
400
(a) Psuedo-reward values over time.
(b) Levers tried over time.
(c) Correct lever pull fraction over time.
Figure 4: The effect of bounded monotone BAMPF and entropy bonus pseudo-rewards on DQN in a I-state MDP, where in 100 total levers gives reward 10 when pulled. None refers to DQN without any pseudo-rewards. The BAMPF potential is the count of unique levers tried, and the Entropy reward is 10x the entropy of the last 10 lever pulls. The setting is non-episodic with = 0.9. The mean and standard error of 32 seeds are plotted for each condition. See Appendix [F for full details,
Displacement - None Displacement PBS
Max Displacement BAMPF
-20
True Return
Secothed Max Disp Displacement
Current displacement
0.8
-60
0.6
-180
Step
Step
-200
50k
100k
150k
50k
100k
150k
200k
(a) Visualization of the environment.
(b) Episodic extrinsic returns of agents (c) Exponentially smoothed maximum
trained with each pseudo-reward type.
displacement over training.
Figure 5: The effect of pseudo-rewards on PPO in Mountain Car; the mean and standard error of 10 seeds are plotted for each type of reward shaping. Displacement rewards the current x displacement of the car, Displacement PBS is potential-base state potential Φ(s), and Max Displacement BAMPF uses the exponentially smoothed maximum displacement over training (5c) as the BAMDP state potential <(h). With Displacement the agent learns a reward-hacking policy that avoids the goal to collect more pseudo-rewards (see Fig. 99) while the BAMPF helps PPO learn to reach the goal more quickly while preserving optimality (bb)
shaping with the current displacement as the MDP
but it is a valid BAMDP potential @(h)). It is bounded due to the finite width of the environment, and as the maximum monotonically increases throughout training. It signals the VOI of the RL agent learning how to get further uphill; because sometimes surpasses its maximum displacement by chance before learning how to consistently get that far, we apply exponential smoothing. Fig. 5c (green curve) shows the resulting BAMPF gets the agent to explore further more quickly, and Fig. 5b shows it learns to reach the goal and maximize true rewards sooner while avoiding reward -hacadin..ning.... See Appendix for full experimental details.
4.3.2 CONVERTING SHEUDO-REWARDS TO RESIST REWARD- -ACKKNG IN RL
Although virtually any pseudo-reward can be cast as a BAMPF, the monotonicity condition doesn't 't naturally include non-cumulative functions of just the latest behavior, e.g., prediction error (the pre- dictability of the latest observations) or entropy bonuses (the entropy of the latest policy) which can fluctuate up or down. However, these terms would still preserve optimality if they could be converted to the sum of bounded monotone increasing BAMPF and a classic PBSF E.g., Curiosity (Pathak et al. 2017) rewards the error of a learnt dynamics model in predicting the latest observations, to encourage continually seeking novel experiences while improving the dynamics model. The non- monotone component that encourages visiting novel states could be captured by a PBSF with ((s) equal the error of a fixed model's prediction of features of s, similar to RND (Burda et al. 2018). The value of improving the dynamics model can be captured by a BAMPF with Φ(h) equal to the maximun accuracy so far of the dynamics model fixed set of transitions. To prevent stagnation,

---

Published as a conference paper at ICLR 2025
the fixed model and transition set could be refreshed regularly between batch updates- long as they can't t change within an episode, optimality will be preserved. This form of Curiosity would not be susceptible to the Noisy TV Problem, since the dynamies model's accuracy @(h) could not increase indefinitely while watching TVV, and even if the fixed model's s error 6(s) were higher at the TV.[Ng et al. (1999)'s result guarantees that policy can't maximize total shaped return by staying there. See Appendix for a more detailed exposition and numerical demonstration.
5 RELATED WORK
Theory of Intrinsic Motivation Oudeyer & Kaplan (2007) categorize IM as knowledge- competence-based morphological, and evaluate them by their exploration (leading exploratory and investigative behavior) and organization (leading to structured and organized behavior) poten- tials, which are similar to the effects of signalling Vo and V,. Singh et al. (2009) propose an evolutionary framework for rewards as maximizing expected fitness over a distribution of environ- ments, concluding that optimal reward depends regularities across the distribution and properties of the learning agent. Aubret et al. (023) propose an information-theoreti taxonomy of IM, but this only captures IM terms signalling value of information; they don't ion't consider the prior environment distribution and so cannot explain how pscudo-rewards should be designed for a given domain.
Extensions of Potential-Based Reward Shaping Devlin & Kudenko (2012) and Forbes et al. (024) extend PBS theory to potential functions that vary over time, including functions of the history, showing that they also preserve the optimal MDP policy. However, Devlin & Kudenko 22012)ss ' proof omits the episodic setting, and Forbes et al. (2024) modify the potential at the last step of each episode to cancel out all prior pseudo-rewards. This inappropriate for potentials mea- suring the value of information, since observations from episode do not lose all value once the episode ends. [Fck al. (2016) extend PBSFs to POMDP planning, defining potential functions over POMDP belief states and categorizing them as Domain-dependent and share similarities to Vo and Vr. Kim et al. 2015) propose BAMDP potential-bet based shaping specifi- cally for model-based Bayesian RL method, although they do not prove that the PBS theorem still holds for BAMDPs (which is non-trivial, because rewards influence the BAMDP state) and do not consider the broader implications for developing pseudo-rewards for any RL algorithm.
which
See Appendix for an extended discussion of related work.
6 DISCUSSION
By formulating RL problems as BAMDPs, we formalize how intrinsic motivation and reward shap- ing help exploration by signalling the value of BAMDP states, which we decompose into the value of information and the value of opportunity. This allows us to characterize the roles of existing pseudo-rewards, explains when they impede exploration as misalignment with these values, and provides principles for designing new terms to guide learning in any given domain. This framework also gives us tools to tackle reward-hacking i.e., to avoid incentivizing RL agents to converge on suboptimal final behaviors. We extend potential-basee shaping theory to propose BAMPFs, a form of -eeudd- that can avoid reward- reward-hacking both in the typical RL setting, by preserving the optimality of the learnt MDP policies, and in meta-RI., by preserving the optimality of the learnt RI. algorithms. Although it is manual process, it is straightforward to design and convert many exist- ing pseudo-rewards into this form, as we illustrate with a case-study converting a prediction error IM term to avert the Noisy TV problem. Our experiments in the Mountain Car RL environment and Bernoulli Bandits meta-RL RL domain demonstrate the utility of our framework for designing practical pseudo-reward functions which both improve learning efficiency and avoid reward-hackir
ACKNOWLEDGMENTS
We would like to thank Cameron Allen, Justin Svegliato and Christian Guckelsberger for insightful discussions, and Benjamin Plaut, Micah Carroll, Niklas Lauffer, Hanlin Zhu and David Abel for feedback on drafts. We are also grateful to Cameron and Niklas for implementation advice. This material is supported in part by the Center for Human Compatlle AI (CHAI) and the Fannic and John Hertz Foundation.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
David Abel, André Barreto, Benjamin Van Roy, Doina Precup, Hado P van Hasselt, and Satinder Singh. A definition of continual reinforcement learning. Advances in Neural Information Pro- cessing Systems, 36, 2024.
Ferran Alet, Martin F Schneider, Tomas Lozano-Perez, and Leslic Pack Kaelbling. Meta-learning curiosity algorithms. arXiv preprint arXiv:2003.05325, 2020.
Cameron Allen, Neev Parikh, Omer Gottesman, and George Konidaris. Learning Markov state ab- stractions for deep reinforcement learning. Advances in Neural Information Processing Systems, 34:8229-8241, 2021.
Arthur Aubret, Laetitia Matignon, and Salima Hassas. An information-theoreti perspective on intrinsic motivation in reinforcement learning: a survey. Entropy, 25(2):327, 2023.
Andrew G Barto, Satinder Singh, Nuttapong Chentanez, et al. Intrinsically motivated learning of hierarchical collections of skills. In Proceedings of the 3rd International Conference on Develop- ment and Learning, volume 1 112. pp. 19. Citeseer, 2004.
Marc Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. Advances in Neural Information Pro- cessing Systems, 29, 2016.
Richard Bellman and Robert Kalaba. On adaptive control processes. IRE Transactions on Automatic Control, 1(2):1-9, 1959.
Glen Berseth, Daniel Geng, Coline Devin, Nicholas Rhinehart, Chelsea Finn, Dinesh Jayaraman, and Sergey Levine. SMIRL: Surprise minimizing reinforcement learning in unstable environ- ments. arXiv preprint 191..550 2019.
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. OpenAl gym. arxiv. arXiv preprint arXiv:/606.0/5400 10, 2016.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. arXiv preprint arXiv: 18/0. /2894, 2018.
Georgios Chalkiadakis and Craig Boutilier. Coordination multiagent reinforcement learning: A Bayesian approach. In Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 709-716, 2003.
Maxime Cheieeier-Boisvertt, Bolun Dai, Mark Towers, Rodrigo de Lazcano, Lucas Willems, Salem Lahlou, Suman Pal, Pablo Samuel Castro, and Jordan Terry. Minigrid & Miniworld: Modular & customizable reinforcement learning environments for goal-oriented tasks. CoRR, abs/2306.1 13831, 2023.
Jack Clark and Dario Amodei. Faulty reward functions in the wild, 2016. com/ http:///eaaaeeeeaaaateeeeeaaaaaa functionn
URL https:
Marco Colombetti, Marco Dorigo, and Giuseppe Borghi. Robot shaping: The hamster experiment.
In Proceedings of ISRAM, volume 96, pp. 28-30, 1996.
Tim Cooijmans, Milad Aghajohari. and Aaron Courville. Meta-value learning: general framework for learning with learning awareness. arXiv preprint arXiv:2307.0888 2023.
Richard Dearden, Nir Friedman, and Stuart Russell. Bayesian Q-learning. AAAIAAAI, 1998:761- 768, 1998.
Sam Michael Devlin and Daniel Kudenko. Dynamic potential-based reward shaping. Proceedings of the 1 1tth International Conference on Autonomous Agents and Multiagent Systems, pp. 433- 440. IFAAMAS, 2012.
Marco Dorigo and Marco Colombetti. Robot shaping: Developing autonomous agents through learning. Artificial intelligence, 71(2):311-370, 1994.

---

Published as a conference paper at ICLR 2025
Yan Duan, John Schulman, Xi Chen, Peter L Bartlett, Ilya Sutskever, and Pieter Abbeel. RL Fast reinforcement learning via slow reinforcement learning. arXiv preprint arXiv:1611.02779 2016.
Michael O'Gordon Duff. Optimal Learning: Computational procedures for Bayes-adaptive Markov decision processes. University of Massachusetts Amherst, 2002.
Adam Eck, Leen-Kiat Soh, Sam Devlin, and Daniel Kudenko. Potential-based reward shaping for finite horizon online POMDP planning. Autonomous Agents and Multi-Agenl Systems, 30:403- 445, 2016.
Ben Eysenbach, Russ R Salakhutdinov, and Sergey Levine. Robust predictable control. Advances in Neural Information Processing Systems, 34:27813-27825, 2021.
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. arXiv preprint D0XXv:/802000770 2018
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. International Conference on Machine Learning, pp. 1126-1135. PMLR, 2017.
Jakob N Foerster, Richard Y Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. Learning with opponent-learning awareness. arXiv preprint (10X.00:70990432 2017.
Grant Forbes, Nitish Gupta, Leonardo Villalobos-Arias, Colin M Potts, Arnav Jhala, and David L Roberts. Potential-based reward shaping for intrinsic motivation. arXiv preprint arXiv:2402.07411, 2024.
Mohammad Ghavamzadeh, Shie Mannor, Joelle Pineau, Aviv Tamar, al. Bayesian reinforcement learning: A survey. Foundations and Trends@ in Machine Learning, 8(5-6):359-483, 2015,
Dibya Ghosh, Abhishek Gupta, and Sergey Levine. Learning actionable representations with goal- conditioned policies. arXiv preprint arXiv: 18X1v8/811.07819 2018
John Gittins. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society Series B: Statistical Methodology, 41(2):148-164, 1979.
Karol Gregor, Danilo Jimenez Rezende, and Daan Wierstra. Variational intrinsic control. arXiv preprint (xXi::6611007000 2016.
Marek Grzeš. Reward shaping in episodic reinforcement learning. In Proceedings of the 16th Con- ference Autonomous Agents and MultiAgent Systems, AAMAS '17, pp. 565-573, Richland, SC, 2017. International Foundation for Autonomous Agents and Multiagent Systems.
Arthur Guez, David Silver, and Peter Dayan. Efficient Bayes-adaptive reinforeement learning using sample-based search. Advances in Neural Information Processing Systems, 25, 2012.
Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep based policies. In International Conference on Machine Learning, pp. (352-1361) PMLR. 2017.
Danijar Hafner. Benchmarking the spectrum of agent capabilities. arXiv preprint 20x0::0000 2021.
Danijar Hafner, Jurgis Pasukonis, Jimmy Ba, and Timothy Lillicrap. Mastering diverse domains through world models. arXiv preprint arXiv:2301.04 1004 2023.
Rein Houthooft, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. VIME: Variational information maximizing exploration. Advances in Neural Information Processing Systems, 29, 2016.
Ronald A Howard. Information value theory. IEEE Transactions on Systems Science and Cybernet- ics, 2(1):22-26, 1966.
12

---

Published as a conference paper at ICLR 2025
Matthew Thomas Jackson, Chris Lu, Louis Kirsch, Robert Tjarko Lange, Shimon Whiteson, and Jakob Nicolaus Foerster. Discovering temporally-aware reinforcement learning algorithms. arXiv preprint arXiv:2402.00588 2024.
Yandong Ji, Gabriel B Margolis, and Pulkit Agrawal. Dribblebot: Dynamic legged manipulation in the wild. In 2023 IEEE International Conference on Robotics and Automation (ICRA), pp. 5155-5162 IEEE, 2023.
Leslie Pack Kaelbling, Michael I. Littman, and Andrew W Moore. Reinforcement learning: A survey, Journal of artificial intelligence research, 4:237-285, 1996.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, pp. 267-274,
2002.
Hyeoneun Kim, Woosang Lim, Kanghoon Lee, Yung- Noh, and Kee- Bee-Eung Kim. Reward shap- ing for model-based Bayesian reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Alexander Klyubin, Daniel Polani, and Chrystopher L Nehaniv. Empowerment: A universal agent- centric measure of control. In 2005 JEEE Congress on Evolutionary Computation, volume I, pp. 128-135. 135. IEEE, 2005.
Robert Tjarko Lange. gymnax: A JAX- reinforcement learning environment library, 2022a. URL http::/ com/ htt//Rooeettaaage gymnax
Robert Tjarko Lange. Training and speed evaluation tools for gymnax, 2022b. //githuub.com//oobetrtl.... gatpe///aaaanggegngagga/aa www.:yblieess.e
URL https:
Youngwoon Lee, Andrew Szot, Shao-Hua Sun, and Joseph Lim. Generalizable imitation learn- ing from observation via inferring goal proximity. Advances in Neural Information Processing Systems, 34:16118-16110, 2021.
Kevin Li, Abhishek Gupta, Ashwin Reddy, Vitchyr H Pong, Aurick Zhou, Justin Yu, and Sergey Levine. Mural: Mcta-learning incertinnty-waan rewards for outcome-driven reinforeement learning. In International conference machine learning, pp. 6346-63565 PMLR, 2021.
Dennis V Lindley. On measure of the information provided by experiment. The Annals of Mathematical Statistics, 27(4):98--0055 1956.
Sam Lobel, Akhil Bagaria, and George Konidaris. Flipping coins estimate pseudocounts for exploration in reinforcement learning. In International Conference Machine Learning, pp. 22594-22613, PMLR, 2023.
Yecheng Jason Ma, Shagun Sodhani, Dinesh Jayaraman, Osbert Bastani, Vikash Kumar, and Amy Zhang. VIP: Towards universal visual reward and representation via value-implict pre-training. arXiv preprint arXiv:2210.00030. 2022.
James John Martin. Bayesian Decision Problems and Markov Chains. John Wiley and Sons Ltd, 1967.
Vladimir Mikulik, Grégoire Delétang, Tom McGrath, Tim Genewein, Miljan Martic, Shane Legg, and Pedro Ortega. Meta-trained agents implement Bayes-optimal agents. Advances in Neural Information Processing Systems, 33:18691-18703, 2020.
Volodymyr Mnih. Asynchronous methods for deep reinforcement learning. 110.0036 2016.
arXiv preprint
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529-55 533,,39,9933 2015.
Shakir Mohamed and Danilo Jimenez Rezende. Variational information maximisation for intrinsi- cally motivated reinforcement learning. Advances in Neural Information Processing Systems, 28, 2015.
13

---

Published as a conference paper at ICLR 2025
Andrew Y Ng. Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In Ieml, volume 99, pp. 278-287. Citeseer, 1999.
Pierre-Yve Oudeyer and Frederic Kaplan. What is intrinsic motivation? A typology of computa-
tional approaches. Frontiers in neurorobotics, 1:108, 2007.
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In International Conference on Machine Learning, pp. 2778-2787. PMLR, 2017.
Sujoy Paul, Jeroen Vanbaar, and Amit Roy-Chowdhury. Learning from trajectories via subgoal discovery. Advances in Neural Information Processing Systems, 2019.
Jian Qian, Ronan Fruit, Matteo Pirotta, and Alessandro Lazaric, Exploration bonus for regret min- imization in discrete and continuous average reward MDPs. Advances Neural Information Processing Systems, 32, 2019.
Nicholas Rhinehart, Jenny Wang, Glen Berseth, John Co-Reyes, Danijar Hafner, Chelsea Finn, and Sergey Levine. Information is power: Intrinsic control via information capture. Advances in Neural Information Processing Systems, 14:10745-10758 2021.
Stwart Russell and Eric Wefald. On optimal game-tree search using rational meta-reasoning. In IJCAL, pp. 334-340. Citeseer, 1989.
Stuart Russell and Eric Wefald. Principles metareasoning. Artificial intelligence, 49(1-3):361- 395, 1991.
Ilya O Ryzhov and Warren B Powell. The value of information in multi-armed bandits with expo- nentially distributed rewards. Procedia Computer Science, 4:1363-1311 1372, 2011.
Christoph Salge, Cornelius Glackin, and Daniel Polani. Changing the environment based on em- powerment intrinsic motivation. Entropy, 16(5):2789-281)) 2014a.
Christoph Salge, Comelius Glackin, and Daniel Polani. Empowerment-an introduction. Guided
Self-Organization: Inception, pp. 17, 2014b.
Jürgen Schmidhuber. A possibility for implementing curiosity and boredom in model-building neu- ral controllers. In Proc. of the International Conference Simulation of Adaptive Behavior: From Animals to Animats, pp. 222-227, 1991.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint 1rXiv:1707.06347, 2017.
Ramanan Sekar, Olch Rybkin, Kostas Daniilidis, Pieter Abbeel, Danijar Hafner, and Deepak Pathak. Planning to explore via self-supervised world models. In International Conference on Machine Learning. pp. 8583 8592. PMLR, 2020.
Archit Sharma, Shixiang Gu, Sergey Levine, Vikash Kumar, and Karol Hausman. Dynamics-awer unsupervised discovery of skills. arXiv preprint arXiv: /907.01657 2019.
Pranav Shyam, Wojciech Jaskowski, and Faustino Gomez. Model-based active exploration. In International Conference on Machine Learning, pp. 5779-5788. PMIR, 2019.
Herbert Simon. Dynamic programming under uncertainty with a quadratic criterion function. Economelrica, pp. 74-81, 1956.
Satinder Singh, Richard L Lewis, and Andrew G Barto. Where do rewards come from. In Proceed- ings of the annual conference of the cognitive science society, pp. 2601-2606. Cognitive Science Society, 2009.
Jonathan Sorg, Satinder Singh, and Richard L Lewis. Variance-based rewards for approximate Bayesian reinforcement learning. arXiv preprint /rXiv:/203.355 2012.
Henry Sowerby, Zhiyuan Zhou, and Michael L Littman. Designing rewards for fast learning. arXiv preprint arXiv:2205. /5400, 2022.
14

---

Published as a conference paper at ICLR 2025
Richard Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances Neural Information Processing Systems, 12, 1999.
Csaba Szepesvári. Algorithms for reinforcement learning, Synthesis Lectures Artificial Intelli- gence and Machine Learning, 4(1):1-103, 2010.
Adrien Ali Taiga, William Fedus, Marlos Machado, Aaron Courville, and Mare G Belle- mare. On bonus-based exploration methods in the arcade learning environment. arXiv preprint arXiv:2109.11052, 2021.
Sebastian Thrun and Lorien Pratt. Learning to learn: Introduction and overview. In Learning to Learn, pp. 3-17. Springer, 1998.
Jane X Wang, Zeb Kurth-Nelson, Dhruva Tirumala, Hubert Soyer, Joel Leibo, Remi Munos, Charles Blundell, Dharshan Kumaran, and Matt Botvinick. Learning reinforcement learn. arXiv preprint arXiv:1611.05765 2016.
David Warde-Farley. Fariee,Farey Tom Van de Wiele, Tejas Kulkarni, Catalin Ionescu, Steven Hansen, and Volodymyr Mnih. Unsupervised control through non-parametric discriminative rewards. arXiv preprint
2018.
Christopher John Cornish Hellaby Watkins. Learning from delayed rewards. PhD thesis, Cambridge University, Cambridge, England, 1989.
Jin Zhang, Jianhao Wang, Hao Hu, Tong Chen, Yingfeng Chen, Changjie Fan, and Chongjie Zhang. Metacure: Meta reinforcement learning with empowerment-driven exploration. In International Conference on Machine Learning, pp. 12600-12610, PMLR, 2021.
Zeyu Zheng, Junhyuk Oh, and Satinder Singh. On learning intrinsic rewards for policy gradient methods. Advances in Neural Information Processing Systems, 31, 2018
Luisa Zintgraf. Kyriacos Shiarlis, Maximilian Igl, Sebastian Schulze, Yarin Gal, Katja Hofmann, and Shimon Whiteson. VARIBAD: A very good method for Bayes-adaptive deep RL via meta- learning, arXiv preprint 1rXiv:1910.083-45 2019.
Haosheng Zou, Tongzheng Ren, Dong Yan, Hang Su, and Jun Zhu. Reward shaping via meta- learning. arXiv preprint 19Xiv:1901.093300 2019.
Haosheng Zou, Tongzheng Ren, Dong Yan, Hang Su, and Jun Zhu. Learning distribbtin re- ward shaping with meta-learning. Proceedings of the AAA! Conference Artificial Intelligence, 35(12): 2021. doi: 10. v1.60//aai.33511...777.
A POTENTIAL-BBSHD SHAPING PROOFS
A.1 MAIN THEOREM
Theorem 4.2 (BAMDP Potential-Based Shaping Theorem). For pseudo-reward function to guar- antee that the optimal algorithm for any shaped BAMDP optimal for the original BAMDP, i.e., Bayes-optimal for the underlying RL problem, it is necessary and sufficient for it to be potential- based shaping function on the BAMDP state.
Proof. (Sufficiency) Denote the original BAMDP M = (8, R,T, with optimal algorithm i.e., it is identical to M except for its shaped reward function R' (3, a, 3441) = R( a) + F((+11) = R(3,, + + @(h).. So model the pseudo-rewards being added to the RL algorithm's 's reward signal internally, rather than entering through the history in the BAMDP state &,, We denote the optimal algorithm for M by "
n* and the shaped BAMDP as M' R
15

---

Published as a conference paper at ICLR 2025
a
S1
Sa
r=2'
r=
a
F
S2
Figure All edges have probability 1, and only action a is applicable from 82 and 8a-
Abbreviating (he)) to os, we can now express the expected return of an algorithm in M in terms of the underlying return it would achieve in M:
Ex [G'] TT.
Σ D' 'l' (5t, ae 51t1)
ET To.m
Σ (R (3), 701-1 100
-ET
Σ yd ((((), at)
+ EE
0o + Σ r 22)
1=1
Eg [G] Φu
Plugging this into the definitions of the Bayes-optimal algorithms for M and M:
मh E arg max E. (G')
*
(8)
= arg max E [G] 00
arg max E [G| π
We prove that if pseudo-reward function F(h) not BAMPF, then there exists BAMDP reward and transition functions such that no Bayes-optimal algorithm for the shaped BAMDP is Bayes-optimal in the original BAMDP.
Proof. (Necessity) Our proof follows Ng et al. (1999)'s 's proof of necessity, but is more complex because the BAMDP state contains the entire history. Assume F is not a BAMPF We need to show that can construct T, R such that no optimal algorithm in shaped BAMDP M' is also optimal in M. Define ((h) = Ere 7 F(h(aDs,))tz) for all with 8a E S,a a E A, where a0s, denotes the trajectory segment from taking action a, receiving reward 0 and transitioning to state sa. (a0s.)++1 denotes the trajectory formed by repeating this segment t + 1 times, and h (a0ss)++1 the history formed by concatenating h with (a0s=)t-1- By assumption of
being BAMPF, there exists valid transition between two BAMDP states (s1, h1), (82, h E S via some action E A yielding reward r' such that 7o(hta'''ss (2)) - ((h,) * F(hja'r's2) 82). Define A F(h,a'''ss - - a 52) (hh,) We now construct M with no uncertainty over R, i.e., p(M) is concentrated on a single MDP M. illustrated in Fig. 6 this M, we have T(s (1, a) = T(s2l$1, a') 1.0. and from 82 and sa the only applicable action leads to So with probability 1. The initial MDP state $1, so for $1 h, to realizable in this environment hn is the length sequence 81. Let R(s1, a) = r' A/2, R((), a') =r' R( elsewhere. Then we have
16

---

Published as a conference paper at ICLR 2025
((), = A/2 d()
((1,,1)))) = r 4/22+ Σ (((((((as)))tt)))
1=
=r' 4/2 - ((1))
= =r' + +/222-1 4 F(had''ss - -
= +'' F (2) 76(h1a'r'ss - A/2
("((s),)i). r' + F(hjd'rssp) + Σ F'lid'''ss (a00s))ct1)
=v' + P(hia'r'ss) (
Hence
if 0 otherwise
a' if 0
x" #"((s1, h1))
*"((s1,11))
d'
a otherwise
A.2 NEAR-OPTIMAL ALGORITIIMS ARE NEARLY INVARIANT TO BAMPFS
We now extend our results to approximately optimal algorithms, first providing an overview of the results and proof sketches before diving into the full proofs.
A.2.1 APPROXIMATE OPTIMALITY COROLLARIES
Corollary A.1. With BAMPF shaping, a near-optimal algorithm म5 for M' will also near-optimal when applied to M, i.e.
E G EGG [G']
<E
Ex- [G] RG G <e
(10)
Proof Sketch. Because BAMPF shaping shifts BAMDP returns by constant, lower shaped return E= [C') corresponds directly [G] decreasing by the same amount. See A.2.2 for the full proof.
Another form approximate optimality is the maximization of return over a finite horizon We can also upper-bound the regret as a function of k. Definition A.1 (k-step optimal). We define RL algorithm as k-step optimal for BAMDP if it maximizes the expected k-step return:
# E arg max ET.T Σn R((3,, 7' (((B,,((3)) x3x))
(1I)
#
Corollary A.2. F is a BAMPF with potential function of maximum magnitude &max and the extrinsic reward has maximum magnitude Rmaxe then the k-step optimal algorithm for the shaped BAMDP, n.. has regret bounded by 2 (dmax Runxx (tmaxx=_)) )-y) ) in the underlying BAMDP, i.e.
Egg G S 2²th (Omax + Rmax 7 - 7)
Exg [G]
(12)
Proof Sketch. The telescoping o summed over horizon l leaves a trailing term of r dx from the last step, which allows bound #t's k-step regret compared to at in terms of Φmax.. The regret of ng compared to the fully Bayes-optimal algorithm # is bounded by the worst-case regret after step k. giving bound in terms of Rmax. See A.2.2 for the full proof.
17

---

Published as a conference paper at ICLR 2025
A.2.2 FULL PROOFS
The result in Equation 7 tells us that a near-optimal algorithm for M' will also be near-optimal in M because the return is just shifted by constant.
Corollary A.I. With BAMPF shaping, near-optimal algorithm of for M' will also be near-optimal when upplied to M, i.e.
Eg -
- [G'] <E = Ex [G]
15 G <e
(10)
Proof.
Ex. - = Ex [G] 00 (En G ob)
(13)
E=- [ E+ G
Eg- [G] E [
Now to prove Corollary A.2 we first introduce the following Lemma:
Lemma A.1. F is BAMPF with potential function of maximum magnitude Qmax then the k-step optimal algorithm for the shaped BAMDP, 2t. has k-step regret bounded by 2* Prnx in the true BAMDP:
max]o(h)]=
Ómax
EFj [GR] Eaz:(Ga) 2
(14)
8.h
Proof. First, observe that when PBSF rewards are summed over a finite horizon, all but the potentials of the first and last timesteps cancel out:
k-1
(70041 - o.)= - +
Σ
( Φx) + 7 on
(15)
t=1
= Φz
Thus, following the same steps Equation we can express the k-step return of an algorithm in the shaped BAMDP as:
E ('+a] E [ + =r Φx) Φ0-
(16)
And the k-step optimal algorithm in the shaped BAMDP can be expressed as:
n = arg max E G' = arg max E [Gx] + 17,(17*0 sh)
(17)
Evaluating this expression at मं. and applying the bound on the potential function, we get:
E [Gx] + F [T max E. [x( Ej,ah* b (u)
(18)
2 max E& [G&] 7* Omax
Erg [Gu] 7* @max
Rearranging the above inequality and applying the bound once
get:
[Gk] Eeqg(Ga) S x Ømax + (T (xx)
(19)
< 2- Omaxx
18

---

Published as a conference paper at ICLR 2025
Corollary A.2. F is BAMPF with potential function of maximun magnitude Quaz- and the extrinsic reward has maximum magnitude Rmax- then the k-step optimal algorithm for the shaped BAMDP, Thk has regret bounded by 20 Rimax T-,) in the undertying BAMDP, i.e.
Ex. [G] Exy [G] S 27th (Anaax + Rmax 7 -
1
(12)
Proof. Since magnitude of the reward is bounded by Rmax, can upper bound the expected return of πh by the optimal k-step return Bag [Gk] plus the maximum return from step k + onwards:
Eg- [G] I |R
[Gk] + t 1 1-y REuxx
(20)
S [Ga] + 2- Ommx + +7 x+41 R Rmaxs
where we applied Lemma A.1 substitute Ezz the second line. Meanwhile, the full expected return of मī can be lower bounded by its k-step return plus the minimum return from step onwards:
k+1 1
E [G] 2 Bay [Gx]
1- Rinax
(21)
En- [G] -7 Ømax -y Rmaxxs
where we substituted the Ex.(Grt [G in the first line using the result in Equation 20
Remark. For RL algorithms that have a minimum resolution at which they distinguish returns, BAMPF shaping ceases affect their behavior once they optimal over long enough hori- zon. More precisely, we call an RL. Algorithm that does not distinguish returns less than d apart d-insensitive. For k high enough that 2 Qmax < d, all k-step optimal d-insensitive algorithms in BAMPF-shaped BAMDP are behaviorally equivalent to their counterparts in the original BAMDP.
A.3 BOUNDED MONOTONE INCREASING POTENTIALS PRESERVE MDP OPTIMALITY
Theorem 4.3. If the pseudo-rewards added to an MDP can expressed as a BAMPF with bounded potential that is monotone increasing over time, it will eventually preserve approximate optimality the MDP, iee.
> HE H E Eg- -G
(6)
where t is the training step, Ex [G] denotes expected unshaped return of an MDP policy पं is policy maximizing the shaped return at step and n² is an optimal policy for the underlying MDP.
Proof. We first introduce lemma to bound the maximum increase in the potential function:
Lemma A.2. If à bounded and monotone, then for any RL algorithmm and finite some point in time H at which & has changed by 8 or more for the last time, and thus all fulure values of (he)) must be within of each other, i.e.:
have
Va, 0, At
3H (0(h+40)) o(hi)<<8 VE H.
(22)
Proof. Because the sequence of ((h;) is bounded and monotone, the Monotone Convergence The- orem tells us that it is convergent. For all convergent sequences S,,
v6 > 0 HE
1Se0 - -S d Vt H,
(23)
where S. is the infimum or supremum of the sequence. Finally, because the sequence monotone have [StAt S.15 SSx0 S,|, therefore |St+Ar S 8.
19

---

Published as a conference paper at ICLR 2025
We will use this lemma to bound the artificial advantage any policy output by the RL algorithm can get due to shaping, and thus show that any policy chosen to maximize shaped return is still near-optimal for the real return.
We proceed by expressing the expected return of policy 9े output by я and shaped by the BAMPF training step i, E,,, [Gr] (i.e., the expected discounted sum of both pseudo-rewards and extrinsic rewards that मe achieves in one episode; G² also varies with t because the BAMPF varies over time), in terms of the unshaped return Er, [G] (i.e., the discounted sum of extrinsic rewards that the same policy achieves in one episode) and the episode length N:
Ex, [G]] = E,, [G + (0(h++1) - 6(he) + +2 ((14)))))))))))))))))))))))))))) - v0(h+11)... + + (be+N)) (24) ER, [0((
= B [G] <(ha)) M.,,
We use this to express the difference in shaped return between MDP policy me that was output by the RL algorithm at step t, and any other MDP policy if we rolled them out at training step t, in terms of the difference in their unshaped returns:
VT E.,, [. - E, [G]]
(25)
= Ex, Ex, [G]
(hh)) ) + ? Ex (x((4()) E [G] o(h)) - - Bx [x((()(
= E. - + + (E,,, (6(++++)))))))))))))())((()))( E, [=(ő(h(+N)])
one side of Equation 25 is nonnegative, the other side must also be nonnegative, thus:
E [G]] 2 E,, [G']]
E G E, [G]
(L [bh++N)] E, (0(h++)))
(26)
Because Te was output by the RL algorithm, ((he+N) is part of its sequence of Φ that has al- ready converged. So Lemma A.2 gives us Ex, (x,(o)))4))) < o(he) + Mcanwhile, because ó is monotone increasing function of time, have E, [o(h++]]] 2 o(hz) for all æ. Applying these inequalities to the lower bound in 26) we can bound how much worse n, can be than any other policy if achieves higher shaped return:
E [G]]
E2 G")
En
G
2
E3 [G] (B., [d(h-N)) E3 [o(h++N)))
(27)
F [ 7 (o(he) + o(he))
> Ex [G] -,
where at the final line we used the fact that 7 S 1. Thus, if the RL algorithm arrives at Th that maximizes return shaped by bounded monotone increasing BAMPF at time t > H, then me must also approximately maximize return in the underlying MDP, i.e.,
Vπ n [G])
E. [
VT Ex [G]
E
(28)
We finally plug in the actual optimal policy for the original MDP x* the right hand side to get our approximate-opiimality wtw.aaattt-opiiilllli-eeeeiiigi result:
E E [G] En- [G]
(29)
Remark. This proof relies on all episodes being the same length. To handle MDPs with variable episode lengths, when episode ends early all remaining BAMPF rewards that would have been added from the rest of the episode should added at the terminating step. See Appendix for an example.
20

---

Published as a conference paper at ICLR 2025
B EXAMPLES OF PSEUDO-REWARU VALUE SIGNALLING
B. PURE VOO SIGNAL
These pseudo-rewards help when Vö has large influence on Q" but the RL algorithm's (implicit or explicit) value estimate is misaligned with it. This often happens when there is significant prior information of the relative values of reaching states in M, which the algorithm is not initialized with, thus the pseudo-reward is often quite task or domain-speciftt E.g., RL agents may underestimate value near the goal before first discovering the goal reward, overestimate it near the icy cliff edge before first experiencing a fall. Attractive or repulsive Vō signal can correct RL algorithms that under overestimate VOO, respectively.
B.1.1 ATTRACTIVE VOO SIGNAL
These terms help where the RI agent underestimates the value of getting to certain states, by re- warding it for reaching them. A common example is goal proximity-bssed reward shaping (Ng et al.) al. 1999 Ghosh et al. 2018 Lee et al.) 2021] Ma et al. 2022); which rewards each step of progress towards a goal in problems where the true reward is only at the goal itself. The goal location varies across MDPs in p( M) but is fully observable from the initial state, therefore going towards it yields no information and thus does increase Vi, but is Bayes-optimal because maximizes Vo. An RL algorithm that is not initialized with this prior information would not prioritize going towards goal over any other state, and would have to discover the sparse reward there through blind trial and error. Shaping rewards compensate for this, incentivizing behavior that approaches the goal.
Another common example with the same underlying mechanism is rewarding points scored in points-based-victon games like Pong. But if winning is not purely points-based, this is not nec- essarily good signal for Voj e.g.. Clark Amodei (2016) found an agent learned to crash itself to maximize points, when the true goal was to place first in the race.
1.1 REPULSIVE VOO SIGNAL
Psuedo-rewards based on repulsive Ve signal help when the agent would take suboptimal actions because it overestimates the Value of Opportunity, again due to missing domain knowledge, by penalizing behavior going to states with lower Vg- Examples are negative surprise or information- cost-based IM (Berseth et al.) 2019 Eysenbach et al. 2021) which give negative rewards based on the unpredictability of the states and transitions experienced. This is beneficial, assuming:
1. Unpredictable situations are undesirable in that domain, e.g. for driverless cars where is dangerous drive near other erratic vehicles, robotic surgery, where it is dangerous to use unreliable surgical techniques with highly variable outcomes.
2. The RL algorithm does not apriori expect danger in unpredictable states and thus overesti- mates the Vo of exploring them; it could learn to avoid them by getting into accidents and receiving negative task rewards, but that would be very costly in the real world.
These rewards help RL algorithms by decreasing their estimates of the value of going to these dangerous states, better aligning them with their true value Q", they return safety before getting into accidents.
More formally, negative surprise works under the assumption that on the distribution of trajectories the agent actually experiences, surprise almost always correlates well with negative outcomes. An example where this assumption wouldn't 't hold is Times Square were a popular and safe destination for the driverless taxi, but the unpredictability of all the adverts were included in the surprise penalty. This measure of surprise correlates poorly with negative outcomes in trajectories through Times Square, it would increase regret by making the agent unnecessarily reroute around it. In this problem, the signal for V/ must be more specific-oni only penalizing surprise with respect to things that could cause accidents, such the positions of other vehicles.
21

---

Published as a conference paper at ICLR 2025
B.2 ATTRACTIVE VOI SIGNAL
Many intrinsic motivation terms are intended to reward behavior that gains valuable experience, reaching states with more valuable information in ht. These are helpful for RL algorithms which don't account for the utility of gathering information (e.g., see section C in problems containing information of significant value that is not immediately rewarding to collect. Note that different types of information are valuable in different types of problems, i.c., for different p(M), and this determines which form of IM provides the most helpful signal for Vy-
Prediction Error-based IM (Schmidhuber 1991 Pathak et al., 2017) rewards experiences that are predicted poorly by models trained on h4- This helps when unpredictability given hy is good signal for the value of the information gained from the observation- thus, for IM based on dynamics models there must be minimal stochasticity (stochastic transitions are always unpredictable but yield no information) and in general most information must be task-relevand (so the information gained has value).
Count-based IM (Bellemare et al. 2016 Burda et al. 2018 Lobel et al. 2023) provide a reward bonus for visiting states that have been visited less frequently, or the case of large continuous state spaces pseudo-counts are used to group similar states into the same bucket. For example, Burda et (2018) observed dynamics prediction error failing in the 'noisy TV' problem, where a TV that changes channels randomly maximizes the intrinsic reward despite providing no information. This motivated their design of RND, which only predicts features of the current state an estimate for how many times that state, similar states, had already been visited. However, these types of IM can be counterproductive when the novelty of a state is poor signal for how valuable it is to explore it, e.g. an "infinite TV problem" " where the TV has infinite unique channels that provide useless information.
Entropy bonus IM is proportional (Szepesvári) 2010; Mnih 2016 Haarnoja et al., 2017). This increases the estimated return more stochastic π, so can be understood as adding in the value of exploring a wider range of actions. This helps when RI algorithms get stuck in local maxima, but breaks down if the scale of the intrinsic rewards is too high, because overly random behavior is unlikely to reach interesting states, or could even be dangerous, c.g., if the increase in entropy when the robot overextends its joints outweighed the negative extrinsic rewards from the damage that does, it could encourage the robot to destroy itself. Therefore must be carefully balanced with the scale and frequency of the extrinsic rewards (Hafner et al. 2023
the entropy of the MDP policy's ' action distribution
Mulual Information-bused skill discovery (Sharma et al., 2019: Warde-Farley et al. 2018 Eysenbach et al. 2018) rewards the agent based on the mutual information between the skills (temporally correlated sequences of actions) it learns and the resulting states. The higher this mutual information, the more diverse and controllable the skill set. It's a good signal for Vi in RL problems where this is a good measure for how useful the set of skills is for maximizing return, which also depends on the choice of representation used for the skills and states.
Information Gain is a measure of the amount of information gained about the environment (Lindley 1956). Info gain-based IM has led to successful exploration in RL (Sekar et al. 2020 Houthooff et al. 2016 Shyam et al. 2019); it is good signal for V in problems where all information about the MDP is usetul for maximizing return. But it could be a distraction in environments with many irrelevant dynamics learn about, since the quantity of information gained would not always align with the value of that information.
B.3 COMPOSITE SIGNAL
Finally, we analyze more complex pseudo-rewards that signal combination of both Vi and V
B.3.1 ATTRACTIVE VOI, REPULSIVE VOO
The Empowerment of an agent is typically measured the mutual information [(s': a between its actions and their effect on the environment (Klyubin et al. 2005) Salge et al.) 2014a Gregor et al. 2016). In prior work, this was generally understood motivating agents move the states
22

---

Published as a conference paper at ICLR 2025
of "maximum influence" (Salge et al. 2014b Mohamed & Jimenez Rezende 2015), e.g., the center of the room, or the junction of intersecting hallways. However, this does not always explain the full story. |Mhamedd & Jimenez Rezende (2015) found that in problems with predators chasing or lava flowing toward the agent, Empooerment motivates it to barricade itself from the lava or avoid the predators- even when this requires holing up in tiny corner of the room. We understand this by decomposing Empowerment into the sum of attractive V, and repulsive Vo signals:
[(s'; a(s) = H(als) H(assss')
(30)
where we can view (als) as adding attractive signal for Vi, similar to Entropy Regularization, encouraging the exploration of different actions such the barricade-placing action. Meanwhile -H -H (a)s, s') adds repulsive signal for Vö. similar to Negative Surprise, signalling that states where the agent is caught or engulfed (which results in the agent's actions ceasing to have any predictable effect on the environment) have low value, and thus should be avoided. Empowerment intrinsic motivation has mostly been tested in small finite environments, but this decomposition suggests its potential for lifelong learning in open-ended worlds, where it can encourage the exploration of a wide range of possibilities while staying out of danger.
Similar to Empowerment is Information Capture (Rhinehart et al. 202 where the intrinsic re- ward is based on the expected entropy of the belief distribution (encouraging exploration) minus the entropy of the latent state visitation distribution (which is low when the agent has "stabilized" the environment by controlling it and creating niche for itself).
B.3.2 ATTRACTIVE VOI AND ATTRACTIVE VOO
Another example of a composite value signal is pseudo pseudo-rewards rewards based on the principle of optimism in the face of uncertainty, e.g. [Sorg et al. (2122) Qian et al. (2019). Rather than just rewarding novel experiences, they aim to reward actions where there is high upper confidence bound on the possible value they could lead to. Thus, these types of pseudo-rewards encourage gaining information about the value of states and actions (signalling VOI), and/or reaching more valuable states (signalling VOO).
Reward bonuses for completing necessary subtasks for the first time, c.g. the first time successfully chopping wood used in Crafter (Hafner (221), ). is more example of composite value signal. adds both the value of discovering how to complete the subtask (because more wood will be needed) and the value of being one step closer to the ultimate objective of mining the diamond (one less woodblock needed to build a pxck-axe). This adds the prior knowledge that in all worlds under p( M), wood is prerequisite for diamonds, and that it is valuable learn how gather new types of resources.
C CERTAINTY-EQUIVAAIE RL ALGORITHMS UNDERESTIMATE THE VALUE OF INFORMATION
Section showed how we can understand many IM terms as encouraging and directing exploration through encoding the value of the resulting information. This type of IM is so popular because many commonly used RI. algorithms under-estimate the value of information; we now introduce a model of these algorithms to formalize this within the BAMDP framework. Many RL algorithms, from policy-based methods like policy gradient (Sutton et al. 1999; Schulman et al. 2017) to value-based methods like Q-Learning (Watkins) 1989 Mnih et | 2015), avoid the intractability of belief-space planning by acting as beliefs are fixed. We formalize this objective with the RL algorithm #
Definition C.1 (Certainty-Equivalent RL Algorithm). At each step, the rithm He follows the MDP policy maximizing its estimated expected return under current beliefs
Algo-
n ((s,, hx)) E arg max (VT
(31)
*The idea of certainty equivalent solutions goes back Simon (9566) and was also descrihed by Duff
b002) as the best reactive policy with respect to # beliefs
Note that this is focused on exploitation- other than IM, ad-hoe methods such as epsilon- or Boltz- exploration may also be used encourage exploration (Kaelhling et al. 1996).
23

---

Published as a conference paper at ICLR 2025
where (.) denotes how #" interprets its experience, which could be anything from distribution over world models maintained by updating prior, to a point estimate of Q* maintained by training a randomly initialized neural net on batches sampled from h, (Mnih et al., 2015). For ease of notation we use ny and de interchangeably, since n, is only used at step & to output a,
For example, policy gradient algorithms like Reinforce sample actions from an MDP policy =g. i.e., π Reinffrre ((st, ha)) = Te where Th is learnt by gradient updates towards maximizing the ex- pected returns R() of the trajectories that it generates, i.c. J(0) Er~ [R])) The algorithm estimates (0) from environment interactions so far, i.e. he, so [0] = (k) (Er [R(T)]] where (he) is concentrated on a point estimate of J(0). If, as model, we assume that policy gradient were to maximize (Ø) between each interaction, then we find that it matches the behavior of To:
arg max, [(e = arg max, (B [ [R(T)]] = arg max, Bor(h.) (V=())(V((()) [V"
(32)
The Certainty- algorithm effectively estimates the value as:
Q(5., a) = max; (h,) a) + (8)-+))]
(33)
Comparing this to the optimal value (s, a) E [R(s;, a) -V he+1))], we see that, even assuming accurate beliefs (h,,, p(M hhe), the Certainty-Equivalle algorithm still misses value from the ability to learn from the information in h. because with (*((++1) it assumes it would still follow the same π from st when in reality would have updated it with the latest observation. F.g., if 8s in Fig. 2 was observed to be empty, H" would update æ to return to 8., forever, resulting in higher return than calculations). Thus, adding pseudo-rewards signalling VOI can compensate for this underestimation, causing the algorithm to predict higher value for behavior leading to valuable information.
kept following the same и back to 86 (see section 1.2 for the
D CURIOSITY CASE STUDY
D.1 BACKGROUND
The Curiosity intrinsic reward introduced by Pathak et al. (2017) is equal to the following error:
F(hs) ? ||((s++1; he) - he)441;h))11.
(34)
where ē($:41; ht) is the output of a forward dynamics model, and e($1413 he) is state encoder.
The encoder extracts features the state that can be influenced by the agent, by minimizing the error of learnt inverse dynamics model i that predicts the action from the encoded state transition:
à = i(((s;; hx), e($ 1: h,);
(35)
The forward dynamics model d predicts the encoded next state given the current action and encoded state:
6($ h2) = d(e(sti hx),, hz),
(36)
and is continually trained to minimize the error of its prediction (as calculated in Equation 34
Curiosity uses this error to estimate the novelty of (and hence the added VOI from observing) states and transitions, assuming the error will decrease for the same observations as d is updated. The Noisy TV problem occurs when the environment contains a screen that flips to random images every time a particular action taken: watching TV doesn't increase VOI, but d's error is highest and never decreases while watching. Thus, an RL algorithm trained with Curiosity is incentivized to produce a reward- -aakking policy that maximizes the total shaped return by watching TV.
Burda et al. (2018) mitigate this issue with Random Network Distillation (RND) by predicting fea- tures of the current state rather than the next state. This would not get distracted by noisy transitions such the TV flipping randomly between few preset images, but it could get trapped forever in front of a TV that incremented through an infinite set of novel images. It could also neglect parts of the environment with novel dynamics, if the transitions are between less novel-looking states.
Curiosity's 's encoder and dynamics models are all trained on the history, so it could be converted to BAMDP potential-based shaping function by directly using the error the potential function
24

---

Published as a conference paper at ICLR 2025
((h,) = [|ē(s)41; - - h.)1l Though this would be fine for meta- it wouldn's preserve optimality for RL because is not monotonic. E.g., in the Noisy TV problem the prediction error always increases when watching TV and decreases upon looking away, because the prediction error of the totally random next image on the TV is higher than the error from exploring the rest of the environment.
D.2 IITENTIAL-BASEDD SHAPING FUNCTION + BOUNDED MONOTONE BAMPF CONVERSION
We could try to capture the same type of dynamics prediction-based IM of Curiosity while pre- serving optimality, by splitting it into potential-basee shaping function plus a bounded monotone BAMPF: The PBSF can capture the part that is non-monotone: the novelty of the current state, while the BAMPF encourages observing novel dynamics that improve the dynamics model, by using its overall accuracy as the potential.
Rewarding Novel States: We could use PBSF with dss) equal to the error of fixed model f's prediction of fixed features f of s (similar to RND), encouraging visiting unfamiliar states:
o(s.) (s)) f(s:)11
(37)
Even if this error were higher at the TV, Ng al. (1999's 's result guarantees that policy can't maximize its total shaped return by staying there.
Rewarding Novel Dynamics: could signal the total VOI at he (see Definition 3.1 with the reduc- tion in prediction error of the forward dynamics model compared to its initial error at ho, which we call Accuracy for brevity. Setting ((h,) to this would encourage the agent seek novel transitions to improve its predictions. We calculate the errors over a fixed set of transitions T, so that Accuracy bounded and should generally be expected to monotonically increase:
Aec(ha)= := [T]
Σ (7.. ((s'; h -1((ssh e(s;; h
(38)
To guarantee that it monotonically increases, we can set ((ho) = Aco(ha) and make subsequent ((h,) the exponentially smoothed maximum accuracy far:
5(h++1) = 0., 0.5 max (ō(he), Acc(he+1))
(39)
Even if TV-wtchhin transitions were in set T, 56h%)) could not increase indefinitely by any signif- icant amount while watching TV, so the agent would not be incentivized to watch TV forever. The total intrinsic reward would simply be the sum of the PBSF and BAMPF:
(b((0)1) + ()he+1)) (0(st) + o(h.)).
(40)
To prevent stagnation, every few batches could update f (e.g.. by training it minimize its error over states visited in the new batches), and we could refresh T (e.g.. with transitions that the dynamics model predicted the most poorly in the new batches). What matters for avoiding reward hacking that the RL agent's choice of policy for the next episode can't 't affect f within the episode (so ((s) remains a function of only the current MDP state), and that T is fixed for enough episodes for d(h) to converge.
D.3 NUMERICAL DEMONSTRATION
We concretely demonstrate the conversion of Curiosity (Pathak et al.) 2017) to an optimality- preserving PBSF + bounded monotone increasing BAMPF with simple numerical experiment. We recreate the Noisy TV problem with the MDP shown in Fig. 7 with three available actions: left, right, and watch TV. The left and right actions deterministically transport the agent into the adjacent state that direction (looping back to SO and S7 when no such state exists). The watch TV action has effect in all states except S1 and S2, where it randomly transports the agent to either S1 or
25

---

Published as a conference paper at ICLR 2025
p=0.5
80
52
86
S7
p=0.5
p=0.5
Figure 7: A discrete MDP recreating the Noisy TV Problem. Transitions deterministic and rewards are O except where labeled explicitly. Taking the watch TV action from state S1 or S2 results in stochastic transition to either state (red arrows).
$2 with equal probability. Thus, randomly flipping between S1 and S2 corresponds to watching Noisy TV. The initial state is SO and the only reward is obtained at S7.
No state feature encoding is needed for this small discrete state space, so lear forward dynam- ics model (( 0zz he) directly on the states based on all the observed transition counts:
1141th, = d(s,, az h4) == arg max No. (s,a, a,,'s))
(41)
where Nr. (s, a, s') denotes the number of (s, s') transitions observed so far. After observing any transition only once this model will predict it correctly- except for watching TV states S1 S2, where it will have a 50% chance of being correct no matter how many more observations it makes.
The states are represented integers between and 7, so we calculate the prediction error by taking the absolute distance. Thus, our Curiosity intrinsic reward is:
F(h+) " $141:h, 8t+1/-
(42)
Training a tabular e-greedy Q-learning agent (episode length 8, 0.95), we find that with 1) > 4. agent reliably converges on a policy that watches TV rather than collecting the rewards S7. Fig. [a (purple curve) shows it achieves almost real return, while Fig. 8b shows it achieves high shaped return, which must be almost entirely from the Curiosity rewards. Fig. [d] shows it estimates lower value for going right at state S3 (exploring further from S0) than left (back to the TV).
To convert Curiosity into a form that preserves optimality, we split it into a PBSF with o(s) equal to the error of fixed model's prediction of features of (similar to RND (Burda et al. 2018) to encourage visiting more novel states, plus a BAMPF with bounded monotone @(h) equal to the maximum accuracy of the dynamics model more novel dynamics.
fixed set of transitions, encourage observing
For the PBSF component, we again use the identity function as the feature encoding of the state fst) = and for our fixed prediction model we use the following:
f(st): if s; 0 S(()) - 1, if < < <
f(x))
(43)
f(st) 3, otherwise
and again use the absolute distance for the error, so our PBSF potential is ((x)) = 1f(s)) [(v))
Here represents model that is already very "familiar" with the initial state SO, somewhat familiar (but still making an error) with the closest states S1, S2, S3, but equally unfamiliar (i.e., making the same large error) with all other states.
For the bounded monotone BAMPF component, we used fixed set T transitions from states S1-S5, including multiple TV-watching transitions. This represents possible set of less well- predicted transitions collected the intermediate stages exploration. Again skipping the encoding and using absolute distance, calculate Accuracy with d (the same dynamics model used for
26

---

Published as a conference paper at ICLR 2025
Pseuto-Reene Reward Type
Curisiity PBS BAMPF
BAMFF
Psoudo Type Curcaiity PBS BAMPF
7.5
PES
Retumms
Retums
Curlecity
BAMP
5.0
None
FBS
0091
Curiosity
2.5
0.0
0.2
-25
0.0
5.0
200
400
600
RO0
1000
200
4.00
800
1000
Episode
Ephande
(a) Episodic real return over training.
(b) Episodic shaped return.
2-
Stodthed Predit diltoo
2.04
01320-9/341
Preudh-Seward Type
-1-
Pse Pre.ato-Rewar Type
Curinsity PB5 BANPT
Curissity PES GAMPE BAMP?
BAMP?
PSS
Curlosty
100
125
150
175
100
200
300
400
500
Epliode
Spisode
(c) Exponentially smoothed maximum prediction accuracy.
(d) Estimated Q
right) Q(3,,
Figure 8: Curiosity intrinsic rewards (purple) cause the agent to learn a reward-hacking policy that maximizes its shaped return by watching TV, the expense of the true return. Meanwhile, convert- ing Curiosity into the form of potential-bast based shaping function plus bounded monotone BAMPF (green) improves exploration without resulting in a suboptimal policy. Each component individually (yellow and blue) also helps learning and preserves optimality. The mean and standard error over 20 training runs plotted for each condition.
Curiosity), as:
Acc(he) = IT| Σ (f [dss, ho) s'1-Id(s, -sl..
(44)
We finally set @(h) to the exponentially smoothed maximum accuracy so far following Equation 39 Fig. [c shows how evolves training. We scale the BAMPF by 5 to get it into the same order of magnitude as the extrinsic reward function.
Fig. 8a shows how using this converted form of Curiosity (green curve) helped the Q learning agent discover how to reach the rewards at S7 more quickly, without incentivizing a suboptimal policy. Each component used individually (blue and yellow curves) also helps learning and preserves opti- mality, as expected. Fig. [d shows how they increase the Q learning agent's estimate of the value of exploring further (going right) from state S3 long before any real rewards have been received, whereas without any pseudo-rewards (grey curve) it doesn't 't estimate that exploring further has any more value than going back until actually starts reliably achieving the real rewards at S7.
Thus, we have converted the problematic curiosity IM term to pseudo-reward with the same ex- ploratory benefits, but without the costs reward- hwward-ackingg
E MORE RELATED WORK
Value of Information The classical notion of the value of information originates in decision theory (Howard) 1966). Early work in metareasoning for tree search considers the utility the information resulting from computation (Russell & Wefald, 1989 1991). Dearden et al. (1998) first applied the concept to RL, computing an approximation to the value of information to help select the Bayes- optimal action. They upper bound the "myopic value of information" for exploring action by the
27

---

Published as a conference paper at ICLR 2025
expected Value of Perfect Information, i.e. the expected gain in return due to learning the true value of the underlying MDP's (s, a) given prior beliefs. Chalkiadakis & Boutilier (2003) described as the value of the change in beliefs quantified by its impact on future decisions but they do not derive an expression for it. Ryzhov & Powell| ( define the value of information of pulling bandit
BAMDP Q values as including the value of information-deeiee
the expected resulting increase in the believed mean reward of the best arm, and derive an exact expression for bandits with exponentially distributed rewards.
Reward Shaping and Meta-RL Meta-Learning has been used to learn intrinsic motivation and reward shaping functions for RL (Zheng et al., 2018 Zou al., 2019; [Aet et al. 2020 Li et al. 2021 Zou et al., (202).. but so far few existing works use reward shaping or intrinsic motivation to guide the meta-learner itself (Zhang et al. 2021 and the preservation of optimal RI. algorithms has not previously been investigated.
Learning Awareness The idea of planning through learning has appeared across RL such as in Bayesian RL and meta-RL (Thrun & Pratt 1998] Duan et 2016; Finn et al., 2017; Mikulik al.) 2020 Jackson et al. 2024) and multi-agent RL [Foerster et al. 2017 Cooijmans et al. 2023).
F LEVER BAMPF DETAILS
We used the DQN implementation from Allen al. (021), with the default hyperparameters except due to the shorter time horizon used. This agent uses apsilon-greedy exploration, with c = 1 for the first 20 steps, decaying linearly to 0.05 over the next 100 steps (according to the schedule 1 - 0.95 * min(0.01 20), 1.0)). The None condition with no pseudo-rewards relied purely on this epsilon-greedy behavior for exploration. In this lifelong setting, the network is updated at every step with a batch of transitions from the full trajectory so far. The value of y used by both DQN and to define the BAMPF was 0.9. The Entropy Bonus intrinsic reward was calculated as - 10H (A) where H (A) is the entropy of the categorical distribution of the last 10 lever pulls.
peeps_inittii and watpaaypeeiiddd100
G BERNOULLI BANDITS META-RL DETAILS
We run the Bernoulli Bandits environment and A2C implementation in Gymnax (Lagge 2022a keeping all the default hyperparameter values except for changing the number of pulls in an episode to 10. The discount factor used for the BAMPF is 0.8, matching the discount factor used by A2C.
Following Wang et al. (2166), we define the regret of an RL algorithm as ΣT= - Mo,
Ei= 0.9 Mar. where '* is the expected reward of the optimal arm and Na, is the expected reward of the arm chosen at time t, so always pulling the optimal arm yields regret O, and only pulling half of the time (performance at random chance) has regret 4.
No rescaling was performed on either the BAMPF or the non-BAMPF pseudo-reward functions, since they were already of the same order of magnitude as the extrinsic rewards.
To handle the finite time horizon, we followed the approach of Grzes (2117) and set @(h10) = at the final (10th) step of each RL algorithm's trajectory, which ensures that the ø still sum to constant over the trajectory to preserve optimality, and intuitively represents the fact that the final BAMDP state has no value, since the agent cannot collect any more rewards from it.
H MOUNTAIN CAR DETAILS
We run Mountain Car implemented in Gymnax (Lange 2022a) using the PPO implementation from (Lange, 2022b), keeping all the default hyperparameter settings. The MountainCar environ- ment itself has discount factor so the reported return is simply the sum of the rewards in each episode, but the PPO algorithm uses discount factor y = 0.99 so this was the discount used for both the potential-based based shaping and the BAMPF. To handle the finite episode lengths, the approach of Grzeš (2117) for the potential- based shaping, setting o(s,) = 0 when s, is the last step in episode, ensuring that it preserves optimality within each episode. For the BAMPE at
again follow
28

---

Published as a conference paper at ICLR 2025
Displacement None Displacement PBS
Max Displacement BAMPF
100
1ep0 Return
50
-50
-100
-150
-200
Step
50k
100k
150k
200k
Figure 9: The (undiscounted) shaped episodic return for PPO trained with each type of pseudo- reward (mean and standard error of 10 seeds).
the last step each episode we multiply (h;) by ? 2000- (where te is the within-episode time- step and the maximum episode length is 200). This corresponds to adding up all the remaining BAMPF rewards that would have been added between that time-step and the final step if the episode hadn't been truncated (where in the remaining steps the history remains frozen at h4 since experiences are collected). Our formula for exponential smoothing (a = 0.5) on the maximum displacement is:
(45) where M, denotes the exponentially smoothed maximum displacement training step Sat is the x position of the car at time / and -0.5 is the position of the lowest point between the two hills. Note that this is still bounded and monotone increasing after smoothing. Our PPO implementation runs 16 copies of the environment in parallel; we maintain a separate M, for each copy (whenever an episode ends, M, carried over the next episode in that environment copy) and plotted the mean over the 16 values of M, in Fig. Sc
=,= 0.5 max
- smxl) + 0.5M,
For each form of pseudo-reward, we scale by constant be on the same order of magnitude as the environment rewards. For the BAMPF and PBS, we scaled it by 10, and for Displacement (non- PBS version) we scaled by Note that whether Displacement preserves optimality is sensitive to this scaling factor, but the BAMPF version preserves optimality no matter the scale.
I CATERPILLAR PROBLEM ANALYSIS
1.1 BAYES-OPTIMAL POLICY VALUES
we describe the behavior for the Bayes-optimal algorithm: for large enough 7 should check Sy first, then stay there forever if it find food, or else return to sw forever. Here we work through the math with 7 = 0.95
In section 2.3
From Sp. the optimal RL algorithm म* would take the action maximizing expected return under its knowledge hg. If were to stay and eat at sw, then h would contain more information than hg. so #* would make the same choice again and eat forever. In that case, it would get return of 1-y 420.
म" were instead to first go to sp and try to eat there, its expected return would be:
5 + yE E ((s,, bat)),
(46)
where the first term is the energy cost of traveling. Now to calculate the second term we take an expectation over p(M). i.e., take the weighted of the returns of an optimal RL algorithm in the presence and absence of food at sy:
EIQ" (18b, /11), eat)] = 0.1 + 0.9(0 - 5- + + 21
150
637,
(47)
where the first term is the return it finds food and thus eats at s; forever, and the second is the return if finds no food and then goes back to eat at s. forever. Plugging this into 46 we get total
29

---

Published as a conference paper at ICLR 2025
expected return of 600. Since this is greater than 420, the Bayes-optimal RL algorithm म* would follow this strategy.
1.2 CERTAINTY-EQUIVALEE ALGORITHM VALUE CALCULATIONS
In section describe how the Certainty-Equivalle RL algorithm would act in the caterpillar MDP example. Here we go through the full calculations.
Algorithm #", assuming had the correct prior p(M), would estimate the values of following vari- ous as follows:
goes to the bush and stays there: P [TT (sw)] = - + 0.1 x 150 1-y 280
aitt alternates between the plants: Ep(Ar) [V Mate (8w)) = -- = -110
Ti eats at the weed forever: P ( (s
1- =420; and would go from 86
so Ep(M)[V[= (s.]] = -5 + 7420 = 394
Teat always cats wherever it is. Ep(N)) [V (sw))
21
420 and
(V 0.1 x 150 I- 300
Because Tw gets the highest estimated value, H" would choose to follow it, thus never learning about the bush and staying at the weed forever.
As example of æ underestimating its own value, take its estimate of its value of eating from (sb, ho), i.e. if it were at the bush with no additional information. assumes it would follow the best MDP policy under current information at the next step matter what found at sb. which is still Tw giving estimate:
(48) However, this significantly underestimates the value. If Æº ate at and found no food, it would update to The to go and eat at sw, and if it did find food it would update to a æ that continues cating 86. This corresponds much higher true value:
((1,,, ho); eat) = FP)(M) [Rssw eat) + (VV" (8b)] 0.1
150 394 = 369
150
2172
((sb, ho), eat) 0.1
+ 0.9(-5y
637
(49)
1-
30


Reviews:
[{"review_id": "kobtdAlNxw", "reviewer": "Reviewer_kw7i", "summary": "The paper presents a theoretical framework that allows us to study both intrinsic motivation and reward shaping together in a unified way. This affords us the analysis of well-known intrinsic motivation and reward shaping methods, and their pathologies. They show that both intrinsic motivation and standard reward shaping can be lifted onto the Bayes-adaptive MDP level, where they together form different ways to do reward shaping for the BAMDP. Then prove that any standard IM and reward shaping method that corresponds to a potential-based shaping in the BAMDP should lead to Bayes-optimality in the underlying problem.", "questions": "Overall, I think this is a good paper, providing good insights into IM and reward shaping. However, I think it would have benefitted from showing its impact with studying more examples of different IM and reward shaping terms, demonstrating how we can study their pathologies. \nCan you present more examples demonstrating the impact of your results?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The BAMDP value decomposition in Lemma 3.2 is to my knowledge novel. It is deceptively simple, yet seems to afford important results.\n\n- Table 1 presents a great overview of how different IM and reward shaping methods fit together under the decomposition.\n\n- The proposed framework of BAMPFs improve our mathematical understanding of IM and reward shaping in RL, and their known pathologies.\n\n- Theoretical results appear novel and of high quality.\n\n- Paper is written clearly and it is easy to read.", "weaknesses": "- The empirical result is illustrative, more than demonstrative. A bigger-scale experiment would have been better. Specifically, I would appreciate a longer-horizon example. It can be tabular. \n\n- The theoretical results are heavy on definitions, to the point of sounding circular. Specifically, the Theorem 4.3. is not really surprising, and follows from applying the definition of potential-based shaping to BAMDPs. Although I agree that it is more complicated than the standard MDP case.\n\n- Plots in Figure 3 are very low resolution to the point of being blurry.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "zQrtKIVYdN", "reviewer": "Reviewer_jfJX", "summary": "This paper studies the problem of reward modeling based on intrinsic motivation (IM) and reward shaping. Although IM generalizes reward-shaping functions in the standard MDP setting, it can still be expressed as reward-shaping in the BAMDP setting. Leveraging the fact that potential-based reward shaping functions (PBSFs) preserve optimal policies under any shaping, an extension to BAMDPs is proposed. This leads the authors to introduce BAMPFs, which are potential functions at the level of BAMDP: there, the state becomes the MDP history or a learning algorithm. A result shows that asymptotically stationary potential functions preserve optimal policies. This hints at how one should model the reward function in complex tasks such that the learned policy does not exhibit undesirable side-effects.", "questions": "- The \"RL algorithms\" paragraph in Sec. 2.1 should appear together with BAMDPs from Sec. 2.3\n\n- Did the authors consider extensions of their method to \"realistic\" environments? Do they already have an algorithm that leverages this BAMPF idea in deep RL?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper is well-motivated: previous literature is introduced properly, and the positioning of this work is clear. \n\nThe interpretation of IM as reward shaping in BAMDPs is novel, to the best of my knowledge. \nAlso, it serves a practical objective, namely, reward modeling for complex RL tasks, a critical problem that is particularly challenging.", "weaknesses": "The paper is sometimes hard to follow:\n-  too long sentences\n-  technical words are used already from the abstract without being introduced or explained. It took me several readings to understand what is going on in this paper. \n\nI am unfamiliar with most of the related work (just the BAMDP part) so I cannot fully assess the quality of this submission. I know that BAMDPs are hard to work with, in terms of interpretability and tractability, but proposing experiments on a bandit problem seems insufficient for a mature publication.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "tgjqQx6c3a", "reviewer": "Reviewer_AbDy", "summary": "The authors propose a unifying decision-making framework that incorporates the concepts of intrinsic motivation, reward shaping, and potential functions. In particular, they propose a Bayes-adaptive MDP (BAMDP) framework that can reformulate intrinsic motivation and reward shaping as BAMDP potential-based shaping functions, thereby avoiding some of the known pitfalls of these methods. They show that this MDP framework satisfies important theoretical properties that make it possible to find an optimal policy, and provide an empirical experiment in support of this.", "questions": "Is there a type of intrinsic motivation and/or reward shaping that cannot be converted into a BAMDP potential-based shaping function? In other words, do these items have to conform to some sort of form or adhere to a certain set of assumptions?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper provides a theoretically-sound framework that is able to incorporate the essence and advantages of intrinsic motivation and/or reward shaping while avoiding some of the known pitfalls of these methods. The decomposition of the value function into two components is insightful and interesting. The paper is generally well-written, and the technical concepts are explained in a relatively clear manner.", "weaknesses": "My biggest concern with this paper is the lack of empirical experiments. While it is reasonable to expect that a theoretical paper such as this one will not have as many experiments, having a single experiment with only a single state is a bit underwhelming. In particular, it would be useful if the authors included at least one other, more complicated experiment that further illustrates the usefulness of their framework. Ideally, the additional experiment(s) would show and contrast how the BAMDP avoids the reward-hacking (or similar) behavior that can occur with intrinsic motivation and/or reward shaping. \n\nSimilarly, it would be useful if the authors could provide a case study showing how a well-known, problematic instance of intrinsic motivation or reward shaping can be converted into a BAMDP potential-based shaping function. I understand that the authors provided a generic, brief overview of this process in lines 315-320, however having a specific example of a well-known, documented instance of reward-hacking (or similar) that would be alleviated by their framework would greatly solidify the arguments presented in this paper.\n\nFinally, the limitations of the framework could use more discussion. In particular, it would be useful to have an example of intrinsic motivation and/or reward shaping (if any) that cannot be converted into a BAMDP potential-based shaping function. This would better characterize the usefulness and applicability of the framework. Ultimately, any potential user of the framework needs to be able to infer from this paper under what conditions the framework should or should not be used.\n\nSome minor comments:\n1) Figure 1 is hard to read. In particular, the caption should be more descriptive, it is not clear which individual plots belong to ‘a)’ vs ‘b)’, and the color scale should have a title.\n2) Figure 2 is overcrowded (making it hard to read) and needs to be simplified.\n3) Each item in Table 1 should have a reference/citation attached to it, especially since some of the items are not mentioned in the main text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "yaJYnH5j7v", "reviewer": "Reviewer_SDzM", "summary": "This paper investigates the design of pseudo-rewards (e.g., intrinsic motivation, reward shaping) and when it can lead to unwanted side effects. To achieve this, the authors first cast the problem into a meta-learning problem by considering the effect of pseudo-rewards at the scale of RL algorithms using the BAMDP framework. \nBy decomposing value functions into value of information/opportunity (VOI/ VOO), the authors developed a new way to classify different \nThe authors also showed that the optimality of an RL algorithm is preserved if and only if the pseudo-rewards belong to the class of potential-based reward shaping in the corresponding BAMDP.", "questions": "1. In section 3.2, the authors draw connections between IM, VOI, and VOO. However, it’s not clear to me how IM is related to VOI or VOO quantitatively. Also, what are the definition of attractive/repulsive signals?\n\n2. On line 323, “In environments containing finite information…”, what is the definition of information for an environment?\n\n3. I’m not sure if Def 4.2 is well-defined. Consider the same single-state MDP/potential function defined on line 364, except that now there are infinitely many levers. In this case, whether the potential function is settling is going to depend on the policy, that is, the potential function is settling if the policy has non-zero probabilities on finitely many levers (independent of time), and will not be settling otherwise.\n\n4. In figure 3, what is None? Does it make use of any exploration method?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The idea of studying pseudo-rewards in the meta-learning setting is very original and interesting. The main theoretical result which says that pseudo-rewards can preserve optimality of an RL algorithm if and only if they are potential-based is very insightful and might be useful for designing new generations of exploration methods.", "weaknesses": "My main concern is that most of the performance guarantee results are proven at the scale of meta-learning, and it is not clear to me whether this actually solves the “reward-hacking” problem at the scale of individual MDPs, which is the main motivation of the paper. For example, if only 1 out of 100 of the MDPs suffers from the noisy TV problem, then the optimal RL algorithm in this case might simply “sacrifice” that MDP by using a novelty-based approach to explore more efficiently in the rest of the MDPs if the rewards from these MDPs far outweigh the ones from the noisy TV MDP.\nAnother minor weakness is that the paper mostly focuses on the invariance properties of the class of BAMPFs, and it remains unclear what are the advantages/disadvantages of choosing a specific BAMPF, which limits the practical relevance of the paper.\n\nAlso, as this paper is more theory focused, I feel like some parts of the paper are not clearly/rigorously written (see questions).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)