RL Algorithms are Information-State Policies in the Bayes-Adaptive MDP

We thank reviewer 6FQX for their feedback, which has helped us improve our paper. We have addressed their concerns with several edits to the writing, as indicated by the blue text in the updated manuscript. Specifically:

• Motivation and contribution The reviewer pointed out that the motivation and contribution of the paper were unclear. We motivate BAMDPs as a way to formally specify RL problems, allowing us to analyze RL algorithms just like MDPs allow us to analyze policies. This radically different perspective makes it straightforward to derive many insights and analyze the extent to which RL algorithms successfully navigate the explore-exploit trade-off, and which naturally has many implications for the design of RL algorithms. We have concretized this more in the abstract and introduction to make our work’s motivation and contribution clearer.
• Unfocused presentation We have moved the less directly applicable section on potential-based shaping to the appendix to focus the story around the more practical insights.
• Lack of practical examples We flesh out and further emphasize practical examples in our manuscript, specifically:
  • Our framework can be used to inform the design of better RL algorithms - it shows that guaranteeing convergence to the optimal policy for the underlying MDP is generally undesirable because it comes at the cost of over-exploring, and algorithms should instead be designed to explore exactly when that is expected to increase return. This is a radical departure from the mainstream view in RL of convergence to the optimal MDP policy as the gold standard. We have emphasized this more in the abstract, introduction and optimality sections.
  • We also flesh out the Negative Surprise example in the Effects of Reward Shaping section, clarifying exactly what assumptions of the algorithm and task distribution must hold for Negative Surprise rewards to be beneficial, to show how our framework provides practically useful insights for reward shaping design.

We address their additional questions below.

• Modeling RL problems with BAMDPs instead of MDPs The reviewer questioned the use of BAMDPs, rather than MDPs, to model RL problems outside of meta-learning. BAMDPs are necessary to fully specify RL problems because the underlying task MDP cannot capture the initial uncertainty and information-gathering that RL algorithms do to learn to maximize return, whereas these are baked into the BAMDP transition function and augmented state space. To reuse existing MDP theory on RL algorithms, we must frame RL problems as MDPs in which the algorithms act like policies, but RL algorithms are not valid policies in the task MDPs because they learn from experience, and thus select actions based on more than just the current task MDP state.
• Hand-written information-state policies We have amended this vague use of language. Information-state policies are policies that act on states augmented with the information gathered thus far. Hand-written refers to the fact that they are explicitly hard-coded by the RL practitioner rather than learned or otherwise optimized.

We greatly appreciate reviewer 6FQX taking the time to consider our response and the updates to our manuscript.

We understand the remaining concern about directly demonstrating practical use. It is now clear to us that it would greatly benefit the reader to see the BAMDP value decomposition we derived applied outside of our toy Caterpillar problem, in a way that demonstrates the practical relevance to AI designers. We have fleshed out our example of how the value signaled by “Empowerment”-based intrinsic motivation (measured as mutual information) can be decomposed into two terms signaling the Value of Opportunity (represented as a negative surprise term) and the Value of Information (represented as an entropy bonus term). To highlight this usage we have moved it from the appendix up into the main text (in the Effects of Reward Shaping section), and mentioned this corollary in the introduction. We find that our decomposition provides a new perspective on the empirical behavior of “Empowerment”-driven agents, more accurately describing the observed behaviors than the prior interpretation of it motivating agents to seek states of maximum influence [1].

Specifically, since Empowerment signals a positive Value of Information for exploring a wide range of actions, and a negative Value of Opportunity for unpredictable transitions. The latter component explains why we see empowerment-driven agents barricade themselves in corners to avoid danger: upon dying they respawn in random locations, which is highly unpredictable. Though this is counterintuitive behavior looking like “Empowerment,” it is directly evident when observing the value decomposition.

We believe this has greatly strengthened our paper by clearly demonstrating to readers how our framework can be leveraged to gain significant novel insights on a practical example.

[1] Mohamed, S., & Jimenez Rezende, D. (2015). Variational information maximisation for intrinsically motivated reinforcement learning. Advances in neural information processing systems, 28.

We thank reviewer 7dtM for their thorough and insightful review; we are glad that they find our framework to be interesting and novel, and see the potential of this perspective for understanding RL and significantly advancing the field.

We also greatly appreciate the reviewer’s constructive feedback, which has helped us improve our paper. We have addressed their concerns with several edits, as indicated by the blue text in the updated manuscript. Specifically:

• Vagueness/lack of formality We understand that we have not been sufficiently precise in our use of language, and have replaced or defined vague language throughout the paper, specifically:

  • Manually programmed algorithms refers to algorithms that are explicitly hard-coded by the RL practitioner rather than learned or otherwise optimized. We have removed the use of this language in the paper, as it appears to be more confusing than helpful.
  • Information state policies refers to policies that act on states augmented with the information gathered thus far (intended as a shorthand to describe BAMDP states in the abstract and introduction to readers who aren't already familiar with BAMDPs)- we have added this clarification to the manuscript.
  • The true p(M) refers to the distribution of tasks that the algorithm would encounter in practice; we have replaced it with this more precise language, and also added more explanation in the definition section to clarify the meaning of p(M) when using the BAMDP to model RL problems in practice

• Potential based shaping We understand the reviewer’s perspective that this theory is less obviously useful because we would not need to shape a BAMDP policy that is already Bayes-optimal; preserving optimal behavior is merely a nice additional property for a reward shaping function to have, though it doesn’t tell us how effectively it would reduce the regret of a suboptimal policy. We updated this section to clarify this point, and have moved the section to the appendix to focus the story around the more practical insights. But we believe it is still a useful demonstration to the reader of an immediate application of our framework to reuse existing MDP theory for RL problems, which does not require any more definitions or formalisms beyond the BAMDP itself.

• Key contribution and novel implications The reviewer expressed concern that the key contribution of the work is not obvious, and many of the implications and insights derived from the framework are not novel. We have amended the abstract and introduction to make it clearer that casting RL algorithms as BAMDP policies is the key contribution, providing a radically different perspective that makes it straightforward to derive many insights and analyze the extent to which RL algorithms successfully navigate the explore-exploit trade-off, and which naturally has many implications for the design of RL algorithms. We highlight two novel implications here:

  • Guaranteeing convergence to the optimal policy for the underlying MDP generally comes at the cost of over-exploring, and algorithms should instead explore exactly when that is expected to increase return. This is a radical departure from the mainstream view in RL that convergence to the optimal MDP policy as the gold standard. We have fleshed this out more in the abstract, introduction and optimality sections
  • Although intrinsic reward is indeed motivated by the general idea that knowledge has value, it was not previously possible to formalize exactly which knowledge has how much value for a given RL problem, and as a result practitioners struggle with intrinsic rewards producing counterproductive behavior because they do not assign value correctly for the problem they’re used in (e.g. the noisy TV problem). The BAMDP framework allows us to formalize exactly what value intrinsic rewards should be signaling in terms of the task distribution and properties of the learning algorithm, so we can design them more accurately. We should have made this point clearer in the Effects of Reward Shaping section- we address this by diving deeper into the Negative Surprise example in the Effects of Reward Shaping section, clarifying exactly what assumptions of the algorithm and task distribution must hold for Negative Surprise rewards to be beneficial, to demonstrate the non-obvious insights our theory can provide RL practitioners trying to design appropriate shaping functions.

We greatly appreciate reviewer 7dtM taking the time to consider our response and the updates to our manuscript.

We find reviewer 7dtM’s suggestion to show a more substantial usage of our value decomposition to be very insightful. It is now clear to us that it would greatly benefit the reader to see the value decomposition applied outside of our toy Caterpillar problem in a way that demonstrates the practical relevance to AI designers. This has driven us to flesh out our example of how the value signaled by “Empowerment”-based intrinsic motivation (measured as mutual information) can be decomposed into two terms signaling the Value of Opportunity (represented as a negative surprise term) and the Value of Information (represented as an entropy bonus term). To highlight this usage we have moved it from the appendix up into the main text (in the Effects of Reward Shaping section), and mentioned this corollary in the introduction. We find that our decomposition provides a new perspective on the empirical behavior of “Empowerment”-driven agents, more accurately describing the observed behaviors than the prior interpretation of it motivating agents to seek states of maximum influence [1].

Specifically, since Empowerment signals a positive Value of Information for exploring a wide range of actions, and a negative Value of Opportunity for unpredictable transitions. The latter component explains why we see empowerment-driven agents barricade themselves in corners to avoid danger: upon dying they respawn in random locations, which is highly unpredictable. Though this is counterintuitive behavior looking like “Empowerment,” it is directly evident when observing the value decomposition.

Again, we thank the reviewer for leading us to this realization and we believe this has greatly strengthened our paper by clearly demonstrating to readers how our framework can be leveraged to gain significant novel insights on a practical example.

[1] Mohamed, S., & Jimenez Rezende, D. (2015). Variational information maximisation for intrinsically motivated reinforcement learning. Advances in neural information processing systems, 28.

We thank reviewer t2gv for their thoughtful review. We are glad that they found our formulation interesting and original, and saw the value in our use of this perspective for characterizing reward shaping functions.

We highly appreciate the reviewer’s detailed feedback, which has greatly helped us improve the paper (edits indicated by blue text in the updated manuscript). In particular:

• Practical implications We have made the practical implications of our framework much clearer and more concrete:

  • We highlight more in the abstract, introduction and optimality sections the powerful implications our framework has for the design and development of improved RL algorithms: guaranteeing convergence to the optimal policy for the underlying MDP generally comes at the cost of over-exploring, and algorithms should instead be designed to explore exactly when gathering that additional information is expected to increase return. This is a radical departure from the mainstream view in RL of convergence to the optimal MDP policy as the gold standard.
  • We dive deeper into the Negative Surprise example in the Effects of Reward Shaping section, clarifying exactly what assumptions of the algorithm and task distribution must hold for Negative Surprise rewards to be beneficial, to demonstrate the non-obvious insights our theory can provide Rl practitioners trying to select the appropriate shaping function

• We have also fixed the use of \citep and \citet, added a more representative reference for regret bounds, and added the full stop after the last bullet in the introdution.

• Motivation The reviewer questioned the benefit of using the BAMDP, because they are known to be generally intractable to solve. We should have made it clearer that we never intend to solve the BAMDP directly, we simply use it as a conceptual framework to model and analyze the behavior of RL algorithms. We don’t think solving the BAMDP is necessarily a good approach to designing optimal RL algorithms- heuristic approximate RL algorithms can be very effective. The BAMDP is valuable because it allows us to formalize what these algorithms should ideally aim to approximate, clarifying when the approximations are appropriate, and giving insights into how to design them- for instance how to shape their rewards to approximate the optimal Q function. We have made this more clear in the introduction.

• Question 1 The reviewer questioned the validity of the BAMDP formulation, citing the existence of provably efficient RL algorithms which appears incompatible with the intractability of the BAMDP. We thank the reviewer for pointing out these efficient algorithms; we have amended our statement about theoretical RL aiming to converge with unlimited interactions, and clarified our own vague use of “efficient”. We used “efficient” to mean making the optimal exploration-exploitation trade-off, so neither over-exploring past the point of diminishing returns, nor exploiting before having enough information to get high rewards. Algorithms that find the optimal MDP policy in polynomial time complexity are not necessarily efficient in this way- always finding this optimal policy often comes at the cost of over-exploring. If the discount factor were high enough that finding the optimal MDP policy is not over-exploration and if we made those same assumptions of underlying structure, then we would arrive at the same results in our framework as a special case.

• Question 2 The reviewer questioned the assumption of a prior over MDPs in the formulation of RL problems. Our use of the word prior should have been clearer- by prior we mean the distribution of tasks the RL algorithm will encounter. We have amended the definition in the BAMDP section and changed language in other places that p(M)/the prior is mentioned to clarify this. An RL algorithm is useful insofar as it performs well on the types of tasks it’s expected to encounter in practice, while it does not matter if it performs poorly on very unrealistic tasks. RL algorithms and reward shaping functions are always designed with specific types of task in mind, and evaluated on such tasks (e.g. maze navigation, atari games, driving simulators) i.e. assumptions about the task distribution are central in the design and evaluation of virtually all RL algorithms, even though this is often not stated explicitly. The task distribution may not be expressible in closed form, but we do not need to construct and solve the BAMDP directly- we show in the Effects of Reward Shaping section how simple features of this distribution can be used to inform the design of helpful reward shaping functions.

I want to thank the authors for their detailed response and for updating the manuscript following reviewers' comments.

Can I ask them to develop more on the following claim:

This perspective implies that RL practitioners should not design algorithms to converge to the optimal task policy, instead they should be designed to explore exactly when gathering further information is expected to maximize overall return.

Why this is not included already in the various notions of regret minimization?

I am sorry for my late reply. Hopefully, there is stil enough time for a quick clarification.

We thank reviewer h87r for their generally positive assessment of our work and its writing. We’re glad they found our perspective to be creative and insightful, and saw the significant benefits of our framework to the RL theory community, as well as the value the characterization of reward shaping can bring to RL practitioners.

We understand their concern about the need for more explicit direct practical applications of the ideas, so we updated the manuscript to show more clear and concrete practical implications. Specifically,

• in the abstract, introduction and optimality sections we highlight a powerful implication our work has for the design of RL algorithms, i.e. that exploring until finding the optimal policy for the underlying MDP is not the optimal approach for the problem itself, and algorithms should instead explore if and only if further information is expected to maximize overall return. This is a radical departure from the mainstream view in RL of convergence to the optimal MDP policy as the gold standard.
• In the Effects of Reward Shaping section we have expanded on the negative surprise reward shaping example, to show more concretely how an RL practitioner could determine when it is beneficial- i.e., when the vast majority of surprise correlates well with negative outcomes on the distribution of trajectories the agent actually experiences.

We address their questions in detail below:

• $R(r_t|s_t,a_t)$ is included in the BAMDP transition function because the history component $h_t$ of the BAMDP state includes all the rewards received over the agent’s trajectory. This captures how the RL algorithm learns the reward function $R$ from its interactions with the task MDP. This remains a pdf because the product $T(s_{t+1}|s_t,a_t)R(r_t|s_t,a_t)$ is equal to the joint probability of transitioning to MDP state $s_{t+1}$ and receiving reward $r_t$.
• The main innovation of this paper was this new conceptual perspective, the use of which makes analysis of RL algorithms very straightforward. We updated the manuscript to emphasize this point.
• Our analysis in the Effects of Reward Shaping section should be predictive of the experimental performance of agents, for each type of shaping function and corresponding conditions on the task distributions described- e.g. adding prediction error rewards will improve performance in problems where the prediction error of an observation is an accurate signal for the value of that observation’s information content. We updated the manuscript fleshing out the negative prediction error example in this section to make this more concrete.