Universal Option Models
We consider the problem of learning models of options for real-time abstract planning, in the setting where reward functions can be specified at any time and their expected returns must be efficiently computed. We introduce a new model for an option that is independent of any reward function, called the universal option model (UOM). We prove that the UOM of an option can construct a traditional option model given a reward function, and also supports efficient computation of the option-conditional return. We extend the UOM to linear function approximation, and we show the UOM gives the TD solution of option returns and the value function of a policy over options. We provide a stochastic approximation algorithm for incrementally learning UOMs from data and prove its consistency. We demonstrate our method in two domains. The first domain is a real-time strategy game, where the controller must select the best game unit to accomplish a dynamically-specified task. The second domain is article recommendation, where each user query defines a new reward function and an article's relevance is the expected return from following a policy that follows the citations between articles. Our experiments show that UOMs are substantially more efficient than previously known methods for evaluating option returns and policies over options.
This paper proposes and analyses "Universal Option Models", an extension of discounted occupancy functions (Ng & Russell, 2000) to "options" (Sutton et al., 1999) – high-level actions that consist of a policy and a state-dependent termination probability function. After establishing a connection between an options discounted state occupancy function and an option rewards (Theorem 1) the application of options to learning and planning in large state spaces via linear function approximation is considered. Consistency and convergence results are given (Theorems 2, 3, and 4) before the efficacy of the technique relative to an earlier option-based technique is demonstrated on two domains.In general, the paper is clearly motivated and the main ideas are presented in a logical fashion. The experimental methodology is clearly explained and the results show a clear and significant improvement over the existing method by Sorg & Singh (2010). I am admittedly not well-versed in the reinforcement learning literature but this seems to be a strong point of the paper. However, I am surprised at the lack of related reinforcement learning work between 2000 and 2010. The references only cite work on PageRank (2002)  and citation networks (2008) in the intervening years.My main concerns surround the theoretical results in the paper. The notion of a "reward-less MDP" appears in Theorems 1 & 2 but is not formally defined anywhere. A theorem that rests on a definition in "scare quotes" makes me nervous as it is not entirely clear what the theorem applies to. It would be good to do so and provide a brief discussion of what is being captured by this definition.The use of a inner product between the vectors $u^o(s)$ and $r^\pi$ at line 151 is very confusing. Just before Definition 1, $u^o(s)$ is defined to be a vector indexed by states over the second argument of $u^o$ and $r^\pi$ is also a vector indexed by states. Accordingly, my interpretation of the inner product $(u^o(s))^\top r^\pi$ would be $\sum_{s'} u^o(s, s') r^\pi(s')$ which is *not* the same as the sum in (4) for $R^o(s)$. No part of the proof of Theorem 1 in the appendix does not use the inner product notation but instead shows the return of option $o$ satisfies (4) directly. As far as I can tell, the vector form of $R^o$ is not relied upon later in the paper so I do not believe this has serious implications for the rest of the paper.Theorem 4 refers to the "Robbins-Monro conditions" but, as far as I can tell these are not given or referenced anywhere in the paper. Even if these are common knowledge in RL it is poor practice to be this imprecise when stating theorems. Furthermore, the "proof" of this result is really only a sketch. Given that there is no page limit for appendices a full proof should be provided.