An Off-policy Policy Gradient Theorem Using Emphatic Weightings
Policy gradient methods are widely used for control in reinforcement learning, particularly for the continuous action setting. There have been a host of theoretically sound algorithms proposed for the on-policy setting, due to the existence of the policy gradient theorem which provides a simplified form for the gradient. In off-policy learning, however, where the behaviour policy is not necessarily attempting to learn and follow the optimal policy for the given task, the existence of such a theorem has been elusive. In this work, we solve this open problem by providing the first off-policy policy gradient theorem. The key to the derivation is the use of emphatic weightings. We develop a new actor-critic algorithm-called Actor Critic with Emphatic weightings (ACE)-that approximates the simplified gradients provided by the theorem. We demonstrate in a simple counterexample that previous off-policy policy gradient methods-particularly OffPAC and DPG-converge to the wrong solution whereas ACE finds the optimal solution.
After rebuttal: The author addresses some of my questions in the rebuttal.  Overall, I think the paper can use better presentation of the theorems and contrast with previous results on semi-gradient theorems. For now the theory might be quite limited in its scalability to larger problems, it might be interesting to explore further how one can combine it with scalable methods in the future. I increase my rating a bit. ====== Summary: The paper proposes a new off-policy gradient form as well as a new procedure to compute the gradient using emphatic weighting. The paper also empirically compares the proposed method with DPG algorithms on a simple three state MDP problem, showing that the proposed method can learn optimal policies while DPG is stuck at local optimal. Questions: 1. Line 96. dot v_s is the gradient of v_s with respect to states or parameters? The states are discrete here so I presume it is parameters? Can authors write down the mathematical form of the gradient in the paper. 2. The author should make it more clear that the LHS of Proposition 1 corresponds to the gradient of interest. 3. What is semi-gradient? The paper did not seem to clarify what this definition is. For example, the update of DPG does follow the gradient (with some technical details to drop an additional term), does the ‘semi-‘ come from dropping such a term? General Advice: 1. Previous work. Though the paper mentions previous works on offPAC and DPG on off-policy optimization, the comparison is not made obvious and clear. Importantly, the paper did not write the mathematical equations for DPG (for example), and make it a bit difficult for direct comparison. 2. Notations and presentation. There is much notation in the paper that is not quite directly clear. I think it definitely helps to clarify interpretations of some terms in (for example) LHS of proposition1.  3. Experiments are a bit weak. The experiments could include probably some more conventional MDP systems to illustrate that the new method does not deteriorate compared with DPG/offPAC because of the difficulty in weight estimate. Current experiments only consider the three MDP system and seem a bit weak. Also, is it possible to carry out function approximation in such a setup to make the algorithm scale and applicable to more realistic system?