Cold-Start Reinforcement Learning with Softmax Policy Gradient
Policy-gradient approaches to reinforcement learning have two common and undesirable overhead procedures, namely warm-start training and sample variance reduction. In this paper, we describe a reinforcement learning method based on a softmax value function that requires neither of these procedures. Our method combines the advantages of policy-gradient methods with the efficiency and simplicity of maximum-likelihood approaches. We apply this new cold-start reinforcement learning method in training sequence generation models for structured output prediction problems. Empirical evidence validates this method on automatic summarization and image captioning tasks.
The paper presents a new method for structured output prediction using reinforcement learning. Previous methods used reward
augmented maximum likelihoods or policy gradients. The new method uses a soft-max objective. The authors present a new 
inference method that can be used to efficiently evaluate the integral in the objective. In addition, the authors propose 
to use additional reward functions which encode prior knowledge (e.g. to avoid word repetitions). 
The paper seems to be promising from the sequence learning point of view as it can 
produce sequences of considerably higher quality. However, the authors seem to be ignorant to a large part of the 
reinforcement learning and policy search literature, please see [1,2] for good reviews of policy search with information-geometric
constraints. 
(1) The soft-max objective is common in the reinforcement learning literature. The given objective is the dual of the following 
optimisation problem: 
J = E_{p}[R] + KL(p||p_\theta). 
If we solve that for p we exactly get the sampling distribution q given in the paper. Plugging the solution back in 
the objective J yields the dual problem of the objective which is equivalent to equation 7. I think such insights
reveal much of the structure of the optimisation problem. Moreover, please note that he objective J is commonly
used in policy search, see for example the REPS algorithm, KL control, linearly solvable MDPs, trust region policy optimisation etc... There is an interesting
difference though, that commonly, we want to compute p and p_theta is the sampling distribution. In this algorithm, we optimise for 
p_theta, i.e., we change the sampling distribution. I think this connections to standard policy search algorithms need to be revealed
in this paper to provide a better understanding what the algorithm actually does. 
(2) The RAML algorithm is a special case of expectation-maximisation based policy search while the new algorithm is an 
instance of information-theoretic policy search, see [1].
Clarifying these relations should help to improve the paper significantly. 
While in general, I like the approach, I have one technical concern regarding the sampling procedure: 
The weight w_i for the reward function is either 0 (with probability p_drop) or W. The authors argue that this is 
equivalent to using a weight that is given by p_drop * W. However, this is incorrect as
E_p(drop)[exp(log p(z) + I(drop == 0) * W * reward)] is *not* the same as exp(E_p(drop)[log p(z) + I(drop == 0) * W * reward)] =
exp(log p(z) + p_drop * W * reward)] 
In fact, the distribution the authors are sampling from is rather a mixture model:
p_drop * p(z) + (1-p_drop) * exp (W * reward) / Z
This is a very different distribution from the one given in the algorithm so I do not think it is sound to use it. 
I think this issue need to be addressed before publishing the paper (maybe its also a misunderstanding on my side,
but the authors need to address my concerns and either proof my wrong or suggest a sound sampling method). Using KL trust
regions similar as in the REPS algorithms could for example be a sounder way of finding the weights w_i). 
In summary, this is in interesting paper, but I have a concern regarding the soundness of the sampling procedure which needs 
to be addressed. 
[1] Deisenroth, Neumann, Peters: A survey on policy search for robotics", FNT 2013
[2] Gergely Neu, Anders Jonsson, Vicenç Gómez, A unified view of entropy-regularized Markov decision processes, 2017