Optimistic policy iteration and natural actor-critic: A unifying view and a non-optimality result
Approximate dynamic programming approaches to the reinforcement learning problem are often categorized into greedy value function methods and value-based policy gradient methods. As our first main result, we show that an important subset of the latter methodology is, in fact, a limiting special case of a general formulation of the former methodology; optimistic policy iteration encompasses not only most of the greedy value function methods but also natural actor-critic methods, and permits one to directly interpolate between them. The resulting continuum adjusts the strength of the Markov assumption in policy improvement and, as such, can be seen as dual in spirit to the continuum in TD(λ)-style algorithms in policy evaluation. As our second main result, we show for a substantial subset of softgreedy value function approaches that, while having the potential to avoid policy oscillation and policy chattering, this subset can never converge toward an optimal policy, except in a certain pathological case. Consequently, in the context of approximations (either in state estimation or in value function representation), the majority of greedy value function methods seem to be deemed to suffer either from the risk of oscillation/chattering or from the presence of systematic sub-optimality.
The paper "Optimistic policy iteration and natural 
      actor-critic: A unifying view and a non-optimality result" investigates 
      policy iteration and natural actor critic (NAC) methods for approximate 
      solutions of Markov decision processes. The setting considers Boltzmann 
      policies, compatible function approximation, and unbiased estimators. The 
      authors introduce a forgetting factor in the NAC update (parameterized by 
      a weight kappa), and show that this version is identical to an incremental 
      ("optimistic") policy iteration (OPI) with learning rate kappa. By making 
      the weight kappa go to zero and decreasing at the same time the policy 
      temperature, the two algorithms tend towards a common limit corresponding 
      to the original NAC (with policies that tend to fully greedy ones). This 
      is exploited to derive insight on the two algorithms and how the 
      convergence of OPI might be established using NAC; as well as to interpret 
      the policy oscillation phenomenon in policy iteration. Then, the authors 
      show that when the temperature is not allowed to decrease to 0, the 
      unified algorithm cannot converge to any nontrivial optimal solution, for 
      any learning rate. Together, the results suggest a good OPI algorithm 
      might be obtained by allowing the parameters to tend to the limits 
      discussed above (both weight kappa and the temperature going to zero, with 
      the overall algorithm thus tending towards NAC). This is illustrated with 
      simulations in a toy problem. I think this is an insightful paper 
      and has the potential to make a significant impact in the field of 
      approximate reinforcement learning and dynamic programming. The way the 
      authors look at the problem is original. The survey of existing 
      convergence results is very nice. While the paper is well-written 
      in general, the detailed technical discussions are often rather dense and 
      not easy to read; therefore, some work to alleviate this would be well 
      spent. In particular, getting the intuition behind the discussion on the 
      relation between standard NAC and the OPI limiting case (e.g. the 
      next-to-last paragraph of Section 3) took a bit of rereading in my case. 
      I also have some non-major comments on the formalism. - The 
      authors should be careful to introduce all notations properly. E.g. J may 
      not be explained in the first paragraph of Section 2; the Qbar notation is 
      not explained there either, and also not needed (it can be introduced 
      later on near the equation where it is defined). Similarly, the natural 
      gradient formula in (6) is left unexplained. - Instead of saying "some 
      norm", it could be called as usual a p-norm and denoted ||..||_p. - 
      The readability is decreased by the use at some places of negative 
      notations rather than positives that are easier to follow, and sometimes 
      even easier to write. Example: tau does not tend to 0, instead of tau_k 
      > 0 \forall k; or r(s, a) does not tend to +-\infty, instead of |r(s, 
      a)| <= R_max which is easier to write. The statement "x < eps for 
      all eps > 0" actually defines x = 0. - I suggest introducing some 
      different notation for the rescaled versions of the parameters w, such as 
      w' or v, since this would make the change to the algorithm easier to 
      follow. Some other presentation comments: - Perhaps the 
      abstract might make explicit the fact that NAC must be modified to make it 
      equivalent to OPI - The keyword "reinforcement learning" could be 
      added somewhere early in the introduction - "In addition to that the 
      class" doesn't seem to be a well-formed sentence - Regarding 
      terminology: in "non-optimistic" policy iteration, it may also be 
      necessary to have w^_k be "complete" in the sense explained one para 
      below, in addition to kappa = 1. - "no modifications to the existing 
      algorithms are needed" -- with the exception of the forgetting factor in 
      NAC(kapppa), this should be pointed out - The difference between the 
      first and second part of Theorem 3 could be pointed out better/in advance, 
      I had to reread the passage a couple of times to understand. Also, the 
      progression from Theorem 2 to Theorem 3 might be explained in advance to 
      prepare the reader. AFTER AUTHOR FEEDBACK: I am grateful to 
      the authors for responding to my comments. My point about "no 
      modifications" was not to say that we have new algorithms in the paper, 
      but rather suggesting to admit that NAC and OPI are not immediately 
      equivalent; before that some changes to NAC to make it more general must 
      be made. I still think that saying "x < eps for all eps > 0" is 
      mathematically equivalent to saying x=0 (in the context of positive x) so 
      as the authors say, it would be good to revise the statement. I 
      keep my overall (positive) opinion about the paper.