Major
I'm quite torn about this submission in the sense that, while it is a nice paper, it lacks a main theoretical or empirical contribution. The experiments conducted in smaller environments are illustrative but are, by themselves, not compelling enough to demonstrate how the concept of cross values aids in accelerating Bayes-adaptive RL in more complex environments. Even one compelling experiment that shows how cross values improve upon the approaches of, for instance, (Zintgraf et al., 2020, Zintgraf et al., 2021) would really ground the paper around a culminating empirical result and take it over the edge. Alternatively, a nice set of theoretical results could also accomplish this.
While the definition of the value of current information in Equation 9 looks reasonable, I can't help but wonder if it is uniquely suited to helping accelerate BADMP learning. Certainly, the literature on PAC-BAMDP methods offers other forms of reward bonuses that do yield provably-efficient learning [12,19]. For instance, rather than integrating out randomness in both e and e', why not take e' to be the environment that has highest likelihood under b_t? Or, alternatively, rather than looking at the expected value across all environments e, perhaps it makes sense to look at the worst case value (minimizing over e) which might have implications for safe or risk-sensitive reinforcement learning? The higher level point here is that, without a corroborating theory, these definitions, while intuitive, seem heuristic and it is unclear if these are the "right" quantities to be examining and learning. Why is the augmented reward structure proposed here better than the Bayesian exploration bonus of [12] or the variance-based bonus of [19]? Notably, both of those approaches come with PAC-BAMDP/PAC-MDP guarantees, while the same cannot be said (or at least has yet to proved) of learning under the PCR.
The different in value functions shown in Equation 14 seems to align with the definition of the value of information (VOI) in the context of optimal learning [9,10,15,18]. In the context of multi-armed bandits, such knowledge-gradient algorithms based on VOI will only take an action if there is an immediate improvement in posterior reward. There is an alternative to Thompson sampling [17] which is explicitly designed to address the shortcoming mentioned on page 4: "a posterior sampling agent cannot learn how to perform actions that are not optimal in any known environment." The information-directed sampling (IDS) algorithm, while originally limited to bandits[11,13], attempts to strike the appropriate balance between information gain and regret minimization. Section 4.3.3 of [17] provides a few examples of how an exploration criterion based on VOI is still insufficient for addressing exploration; briefly, the issues boils down to the fact that information revealed at a given moment in time need not result in an immediate performance improvement to be useful, so long as it contributes to performance in the long-term. Highlighting the map example mentioned at the top of page 4, consider a nested version of the problem where an agent must navigate to two separate maps in sequence (for context, say one map to get out of some wrong building and then a second to navigate efficiently in the correct building). Acquiring information by navigating to the first map doesn't result in higher expected return, but is clearly a necessary step towards achieving higher returns and ultimately solving the task. Do the authors have any thoughts on this connection and whether or not a similar impediment arises when using PCR rewards? If the same story holds true, it would again call into question whether or not PCR rewards are the "correct" quantity for calibrating information gain. Minor
On the point of developing supporting theory for the paper, I can't help but notice that Equation 13 has the exact form of a potential-based shaping function [14], except in the context of a BAMDP rather than the traditional MDP. Have the authors contemplated this connection at any depth? To the best of my knowledge, I don't know of any papers that take the years of work on potential-based reward shaping in MDPs and considers how to invoke those ideas to accelerate BAMDP learning. An updated version of this work could build on that connection as part of a more concrete theoretical contribution. Clarity Strengths
The paper is both well-written and well-organized. The authors do a fantastic job of navigating readers through BAMDPs, cross values, predictive reward cashing, limitations, experiments, and future work. Weaknesses Major
I would have liked to see explicity algorithms with pseudocode for PCR Q-learning and PCR-TD, just to confirm my intuitions about them beyond the exposition of Sections 5-8. Minor
There is some inconsistency in the document between the use of PCR vs. PRC. I believe the authors intended to use PCR and instances of the latter are typos. Originality Strengths
The authors do a good job of contextualizing the potential of their approach in augmenting and improving recent work on Bayes-adaptive deep reinforcement-learning algorithms. Weaknesses Major
The literature review on more classic work on BAMDPs and Bayesian reinforcement learning seems lacking. For a paper that leans so heavily on these topics and offers a foundational contribution, I would expect a more nuanced discussion of the classic literature [2, 3, 8, 20, 5, 4, 6, 7, 1, 12, 16, 19] without deferring readers to the 2015 survey paper on Bayesian reinforcement learning. Minor Significance Strengths
The results do a good job of highlighting the potential utility of cross values in Bayesian reinforcement learning. Weaknesses Major
While the conceptual idea behind cross values is interesting, I suspect there is a nontrivial amount of work needed to realize its benefits (if any) in the context of deep reinforcement learning. Without any confirmation of that success yet, it is difficult to see this paper as having high impact. As mentioned above, an alternative contribution would provide supporting theory for cross values and PCR rewards, offering the community a new perspective on how to handle approximate Bayesian reinforcement learning. Minor References
Asmuth, John, Lihong Li, Michael L. Littman, Ali Nouri, and David Wingate. "A Bayesian sampling approach to exploration in reinforcement learning." In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pp. 19-26. 2009.
Bellman, Richard, and Robert Kalaba. "On adaptive control processes." IRE Transactions on Automatic Control 4, no. 2 (1959): 1-9.
Dayan, Peter, and Terrence J. Sejnowski. "Exploration bonuses and dual control." Machine Learning 25, no. 1 (1996): 5-22.
Dearden, Richard, Nir Friedman, and Stuart Russell. "Bayesian Q-learning." In Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, pp. 761-768. 1998.
Duff, Michael O. "Monte-Carlo algorithms for the improvement of finite-state stochastic controllers: Application to Bayes-adaptive Markov decision processes." In International Workshop on Artificial Intelligence and Statistics, pp. 93-97. PMLR, 2001.
Duff, Michael O. "Design for an optimal probe." In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 131-138. 2003.
Duff, Michael O., and Andrew G. Barto. "Local bandit approximation for optimal learning problems." In Proceedings of the 9th International Conference on Neural Information Processing Systems, pp. 1019-1025. 1996.
Duff, Michael O'Gordon. Optimal Learning: Computational procedures for Bayes-adaptive Markov decision processes. University of Massachusetts Amherst, 2002.
Frazier, Peter I., and Warren B. Powell. "Paradoxes in learning and the marginal value of information." Decision Analysis 7, no. 4 (2010): 378-403.
Frazier, Peter I., Warren B. Powell, and Savas Dayanik. "A knowledge-gradient policy for sequential information collection." SIAM Journal on Control and Optimization 47, no. 5 (2008): 2410-2439.
Kirschner, Johannes, and Andreas Krause. "Information directed sampling and bandits with heteroscedastic noise." In Conference On Learning Theory, pp. 358-384. PMLR, 2018.
Kolter, J. Zico, and Andrew Y. Ng. "Near-Bayesian exploration in polynomial time." In Proceedings of the 26th annual international conference on machine learning, pp. 513-520. 2009.
Lu, Xiuyuan, Benjamin Van Roy, Vikranth Dwaracherla, Morteza Ibrahimi, Ian Osband, and Zheng Wen. "Reinforcement Learning, Bit by Bit." arXiv preprint arXiv:2103.04047 (2021).
Ng, Andrew Y., Daishi Harada, and Stuart Russell. "Policy invariance under reward transformations: Theory and application to reward shaping." In Icml, vol. 99, pp. 278-287. 1999.
Powell, Warren B., and Ilya O. Ryzhov. Optimal learning. Vol. 841. John Wiley & Sons, 2012.
Poupart, Pascal, Nikos Vlassis, Jesse Hoey, and Kevin Regan. "An analytic solution to discrete Bayesian reinforcement learning." In Proceedings of the 23rd international conference on Machine learning, pp. 697-704. 2006.
Russo, Daniel, and Benjamin Van Roy. "Learning to optimize via information-directed sampling." Advances in Neural Information Processing Systems 27 (2014): 1583-1591.
Ryzhov, Ilya O., Warren B. Powell, and Peter I. Frazier. "The knowledge gradient algorithm for a general class of online learning problems." Operations Research 60, no. 1 (2012): 180-195.
Sorg, Jonathan, Satinder Singh, and Richard L. Lewis. "Variance-based rewards for approximate Bayesian reinforcement learning." In Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence, pp. 564-571. 2010.
Strens, Malcolm. "A Bayesian framework for reinforcement learning." In ICML, vol. 2000, pp. 943-950. 2000.
4 (2010): 378-403. Frazier, Peter I., Warren B. Powell, and Savas Dayanik. "A knowledge-gradient policy for sequential information collection." SIAM Journal on Control and Optimization 47, no.