BAMDP Shaping: a Unified Framework for Intrinsic Motivation and Reward Shaping

Authors: Aly Lidayan, Michael D Dennis, Stuart Russell
Primary area: reinforcement learning
Keywords: Reinforcement Learning Theory, Bayesian Reinforcement Learning, Intrinsic Motivation, Reward Shaping, Reward Hacking

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.

Decision: accept (poster)
Reviewer scores: 8, 6, 8, 6

Reviews and discussion:
<thread>
creation date:
1729172774828

thread_type:
official_review

<thread_object>
creator: reviewer_sdzm

<content>
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. 
By decomposing value functions into value of information/opportunity (VOI/ VOO), the authors developed a new way to classify different 
The 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.

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.
Another 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.

Also, as this paper is more theory focused, I feel like some parts of the paper are not clearly/rigorously written (see questions).

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?

2. On line 323, “In environments containing finite information…”, what is the definition of information for an environment?

3. 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.

4. In figure 3, what is None? Does it make use of any exploration method?
</content>
</thread_object>

</thread>
<thread>
creation date:
1729544947741

thread_type:
official_review

<thread_object>
creator: reviewer_abdy

<content>
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.

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. 

Similarly, 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.

Finally, 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.

Some minor comments:
1) 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.
2) Figure 2 is overcrowded (making it hard to read) and needs to be simplified.
3) 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.

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730753569548

thread_type:
official_review

<thread_object>
creator: reviewer_jfjx

<content>
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.

strengths:
The paper is well-motivated: previous literature is introduced properly, and the positioning of this work is clear. 

The interpretation of IM as reward shaping in BAMDPs is novel, to the best of my knowledge. 
Also, 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:
-  too long sentences
-  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. 

I 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.

questions:
- The "RL algorithms" paragraph in Sec. 2.1 should appear together with BAMDPs from Sec. 2.3

- 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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730811042599

thread_type:
official_review

<thread_object>
creator: reviewer_kw7i

<content>
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.

strengths:
- The BAMDP value decomposition in Lemma 3.2 is to my knowledge novel. It is deceptively simple, yet seems to afford important results.

- Table 1 presents a great overview of how different IM and reward shaping methods fit together under the decomposition.

- The proposed framework of BAMPFs improve our mathematical understanding of IM and reward shaping in RL, and their known pathologies.

- Theoretical results appear novel and of high quality.

- 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. 

- 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.

- Plots in Figure 3 are very low resolution to the point of being blurry.

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. 
Can you present more examples demonstrating the impact of your results?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732073474614

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Overall Response

comment:
We thank all the reviewers for their thoughtful responses. We are glad that they found our work to be novel (SDzM,kw7i, jfJX), insightful (AbDy, SDzM), theoretically sound (kw7i, AbDy) and addressing an important challenge (jfJX,kw7i). We also greatly appreciate the constructive feedback, which has helped us improve our paper. We have uploaded a revised manuscript incorporating the feedback, with changes highlighted in blue.

In particular, a common theme among reviewers was that larger-scale experiments in more complex domains would help demonstrate the practical impact of the theory. **We have added two experiments to section 4, showing BAMPFs improve learning efficiency while preserving optimality, whereas similar pseudo-rewards result in reward hacking**. These examples also demonstrate how our BAMDP value framework can inform the design of more effective pseudo-reward functions.

- We train PPO in Mountain Car, which has a 2D continuous state comprising the car’s position and velocity. The reward is -1 at each step; 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 on the hill 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. 5c), but eventually results in reward-hacking policies that collect more pseudo-rewards by avoiding the goal (Figures 5b and 7). Converting this to classic potential-based shaping by setting $\phi(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 a 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 value clearly depends on more than the current state, so isn't a valid MDP potential- but it *is* a valid BAMDP potential $\phi(h)$. It signals the VOI of the RL agent learning how to get further uphill; because the agent sometimes surpasses its maximum displacement by chance before learning how to consistently get so 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-hacking.

- We train A2C in the Bernoulli Bandit meta-RL problem introduced by [1]. The MDPs in this domain have 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 previous arm pulled, the reward it produced, 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. The A2C meta-learner continually updates the RNN agent to maximize expected return in its 10-step lifetime, i.e., to find the RL algorithm that optimally balances exploration and exploitation. Without any shaping, A2C gradually learns to generate RL agents that try fewer arms on average, i.e., avoiding over-exploration (Fig. 3b, grey curve). This shows that it initially over-estimates the VOI of trying more arms, so we add a BAMPF to correct its prior: setting $\phi(h)$ to the total pull count of the first arm that produced a reward, decreasing the relative perceived VOI of exploring the other arm. We find it helps A2C learn lower-regret RL agents more quickly, while still converging to an optimal agent (Fig. 3b, green curve). In contrast, when this pull count is added directly as a pseudo-reward, it causes the meta-learner to converge on an agent that over-exploits and never achieves the optimal regret (Fig. 3, purple curve).

See the revised manuscript for plots & further experimental details. We hope these additional experiments more concretely demonstrate the utility of our framework

In addition to the experiments, feedback from the reviewers on the writing has helped us improve the clarity of the paper in many ways. We detail how this has been done in individual responses to the reviewers.

**Updates:**
Thank you all for a very constructive discussion period! Following reviewer AbDy's valuable suggestion, we explicitly demonstrate the use of our BAMPF framework to convert a well-known problematic IM term to a form that avoids reward-hacking, making this part of our paper more concrete. Reviewer SDzM's thoughtful, detailed feedback helped us further clarify our narrative and make our theory more precise.

[1] Wang, Jane X., et al. "Learning to reinforcement learn." arXiv preprint arXiv:1611.05763 (2016).
</content>
</thread_object>

</thread>


Metareview:
metareview:
BAMDP Shaping: A Unified Theoretical Framework for Intrinsic Motivation and Reward Shaping

Summary: This paper addresses the role of pseudo-rewards in reinforcement learning (RL) through the lens of Bayes-Adaptive Markov Decision Processes (BAMDPs). It presents a theoretical framework for understanding intrinsic motivation (IM) and reward shaping by analyzing how pseudo-rewards guide exploration through BAMDP state values, decomposed into Value of Information (VOI) and Value of Opportunity (VOO). The paper introduces BAMDP Potential-Based Shaping Functions (BAMPFs), which ensure pseudo-rewards preserve the optimality of RL algorithms and avoid reward hacking. The authors provide theoretical results showing that BAMPFs can preserve both RL and meta-RL optimality. Empirical demonstrations in the Mountain Car environment and Bernoulli Bandits domain highlight the practical utility of BAMPFs in improving learning efficiency and avoiding suboptimal exploration incentives while maintaining theoretical guarantees. 

Comments: We received 4 expert reviews, with the scores 6, 6, 8, 8, and the average score is 7.0. The reviewers are generally positive about the technical contributions of this paper. In particular, the reviewers commented that the BAMDP decomposition into Value of Information (VOI) and Value of Opportunity (VOO) is novel and insightful, and provides a unified theoretical framework for intrinsic motivation and reward shaping. This approach also offers a practical method to design pseudo-rewards while avoiding common issues such as reward hacking. The reviewers appreciated the strong theoretical approach used by the authors to address this intuitive and challenging question. The paper is also well-written. 

The reviewers have also provided some valuable suggestions to strengthen the paper. I am glad to see that the authors have already accommodated many of the suggestions into their revised version during the rebuttal period. However, there is one concern, about limited empirical results, which is the lack of larger-scale or longer-horizon examples. This concern is valid as it limits the ability to evaluate the clear practical impact of the framework. I recommend the authors to Include more experiments on MuJoCo style environments.