Zero-Shot Transfer with Deictic Object-Oriented Representation in Reinforcement Learning
Object-oriented representations in reinforcement learning have shown promise in transfer learning, with previous research introducing a propositional objectoriented framework that has provably efficient learning bounds with respect to sample complexity. However, this framework has limitations in terms of the classes of tasks it can efficiently learn. In this paper we introduce a novel deictic objectoriented framework that has provably efficient learning bounds and can solve a broader range of tasks. Additionally, we show that this framework is capable of zero-shot transfer of transition dynamics across tasks and demonstrate this empirically for the Taxi and Sokoban domains.
Summary of paper  This paper introduces Deictic Object-Oriented MDPs, which define MDP dynamics in terms of effects that are relative to a particular "central" object (i.e. deictically defined). A variant of DOORMAX is introduced for the efficient learning of DOOMDPs and their use to guide exploration for sample-efficient MBRL. Finally, experiments demonstrate that the deictic and object-oriented nature of the models can facilitate effective transfer between tasks that share the same dynamics schema.  Technical Quality  As far as I am able to tell the paper is technically sound. DOOMDPs and DOORMAX_D are well-defined and well-motivated. The experiments effectively support the claims that deictic predicates permit the compact representation (and correspondingly efficient learning) of domains with varying numbers of objects.  Clarity  I found the paper to be well-written. The OOMDP framework is highly technical and notation-heavy, and I appreciated the authors' efforts to aid in the reader's comprehension with concrete examples. One place I noticed where this might be improved was in Section 2.2. I found it very difficult to take in the entirety of the framework so quickly and was wishing for a running example to make components concrete. I wonder if the authors would consider interleaving the description of the Taxi domain with the definition of DOOMDPs? I don't think it would require a big change in space usage, but might help the reader make sense of the framework as it is described rather than having to circle back later and map the examples to the general description.  Originality  The paper is fully open about the fact that these findings build heavily upon existing theory and algorithms (particularly POOMDPs and DOORMAX). There is a novel contribution, though. First, conceptually, the paper threads a needle between a purely propositional system, which of course suffers when the number of objects can change, and a fully first-order system, which would negatively impact learnability. The observation that deictic predicates can yield some of the benefits of a first-order framework without incurring its costs is not entirely novel in the history of logic-based systems of course, but it is, as far as I know, novel in the context of OOMDPs. Second, the paper offers a particular instantiation of this idea, working through the details of how deictic predicates would be defined and learned.  Significance  I would say that the practical significance of this paper is rather low. Though appealing in many ways, OOMDPs are not to the point where they can be applied to problems of genuine interest -- they require far too much prior domain knowledge and do not fail gracefully when their biases are not reflected in the environment. Expanding the reach of OOMDPs from small, idealized toy problems to bigger, idealized toy problems is not going to change current practice.  However, I do think there is something to be said about exploring the edges of what a model with strong generalization can achieve. Rmax showed that sample efficient RL was possible, and this work continues a thread extending that analysis to richer and richer state spaces, where the structure is exploited to avoid dependence on the size of the state space, and now can be shown to facilitate generalization from easy problems to much larger and complex problems as the deictic operators allow for the expansion of the number of objects. So from a broader view of MBRL, this paper plants a theoretical flag that says "if you could have a model like this, you could enjoy some massive benefits." To the extent to which the paper teaches us about what we could possibly hope to achieve with MBRL, and what model properties might be necessary to get there, I think it may be of interest to the community.  Overall  I found the paper to be well-written and engaging. It represents a non-trivial extension to existing work. Its contributions are largely conceptual and theoretical and not likely to immediately impact practice. Nevertheless, the findings do expand what is possible in the context of provably efficient MBRL and explore a type of model-structure that may be more generally valuable.  ---After Author Reponse---  Having considered the other reviews and the author response, I still feel that this paper offers a novel and worthwhile contribution in formalizing the deictic setting as a middle ground between fully propositional and fully relational representations. I don't think this result would necessarily have a big impact practically (OOMDPs are hard to scale) or conceptually (I think it is already widely understood that representations like this are desirable) but I do think the results in this paper teach us something about the theoretical boundaries of efficient RL and that's worth having in the literature, so I still tend to vote for acceptance.