Policy gradient methods have achieved remarkable successes in solving challenging reinforcement learning problems. However, it still often suffers from sparse reward tasks, which leads to poor sample efficiency during training. In this work, we propose a guided adaptive credit assignment method to do effectively credit assignment for policy gradient methods. Motivated by entropy regularized policy optimization, our method extends the previous credit assignment methods by introducing a more general credit assignment named guided adaptive credit assignment(GACA). The benefit of GACA is a principled way of utilizing off-policy samples. The effectiveness of proposed algorithm is demonstrated on the challenging WikiTableQuestions and WikiSQL benchmarks and an instruction following environment. The task is generating action sequences or program sequences from natural language questions or instructions, where only final binary success-failure execution feedback is available. Empirical studies show that our method significantly improves the sample efficiency of the state-of-the-art policy optimization approaches.
This paper proposes guided adaptive credit assignment (GACA) for policy gradient methods with sparse reward.
GACA attacks the credit assignment problem by
1) using entropy regularized RL objective (KL divergence), iteratively update prior \bar{\pi} and \pi_\theta;
2) generalizing KL to f-divergence to avoid mode seeking behaviour of KL;
3) using 2 tricks to estimate the gradient of f-divergence to update \pi_\theta, a) modified MAPO (Liang et al., 2018) estimator (using two buffers), b) replacing rho_f by the inverse of tail probability (Wang et al., 2018).
Experiments of program synthesis and instruction following are conducted, to show the proposed GACA outperform competitive baselines.
Although the experimental results look promising, I have many concerns with respect to this paper as follows.
1. The organization is bad. The main algorithm has been put into the appendix. It should appear in the paper.
2. There are too many typos and errors in the paper and derivations, which quite affected reading and understanding.
For example:
in Eq. (6), what is z \sim Z? Should be z \in Z? It also appears in many other places.
in Eq. (7), there should not be \sum_{z \in Z} here.
Proof for Prop. 1, I cannot really understand the notations here. Please rewrite and explain this proof. (I can see it follows Grau-Moya et al., 2019, but the notations here are not clear.)
in Eq. (11), \bar{\pi} / \pi_\theta is used, but in Eq. (12), \pi_\theta / \bar{\pi} appeared, which one is correct? While in the proof for Lemma 2, it is \bar{\pi} / \pi_\theta. And in Alg. 1 it is \pi_\theta / \bar{\pi}. Please make this consistent.
Typos, like "Combining Theorem 1 and Theorem 2 together, we summarize the main algorithm in Algorithm 1." in the last paragraph of p6. However, they appeared as Prop. 1 and Lemma 2. Please improve the writing.
3. The mutual information argument Eq. (9) seems irrelevant here. (It follows Grau-Moya et al., 2019, but the notations in the proof are bad and I cannot understand it). Whether the solution is mutual information or not seems not helpful for getting better credit assignment. I suggest remove/reduce related arguments around Eq. (9) and (10), and make space for the main algorithm.
4. The entropy regularized objective and the KL is kind of well known. Maybe reduce the description here. And the key point is Eq. (8), which lays the foundation of iteratively update \bar{\pi} and \pi_\theta. However, Eq. (8) is the optimal solution of KL Eq. (7). Is it also the optimal solution of f-divergence used in the algorithm? If it is, clearly show that. If not, then update \bar{\pi} in Alg. 1 is problematic. Please clarify this point.
5. The 2 tricks used here for estimating the gradient of f-divergence with respect to \pi_\theta, i.e., modified MAPO estimator in Prop. 2, and inverse tail probability in Wang et al., 2018, seems quite important for the empirical performance.
However, motivation is not clear enough. First, why using two replay buffers "leads to a better approximation"? Any theory/intuition or experiment to support this claim? Second, why using inverse tail probability "achieve a trade-off between exploration and exploitation". It seems not obvious to see that. And also, explain why using this trick makes "\pi_\theta adaptively coverage and approximate prior distribution \bar{\pi}".
6. The claim that GACA recovers all the mentioned methods as special cases are questionable. For example, as in E.1, "by simply choosing \rho_f as constant 1", comparing Eq. (12) with the gradient of REINFORCE, there is a difference that REINFORCE has a reward term, but GACA does not have. Then why GACA reduces to REINFORCE? Also in E.5, the RAML objective seems wrong. There is no reward term here. Please check them.
Overall, the proposed GACA method achieves promising results in program synthesis tasks. However, there are many concerns with respect to motivation and techniques that should be resolved.
=====Update=====
Thanks for the rebuttal. I keep my rating since some of my concerns are still not resolved. In particular, "Eq. (8) is the optimal solution of KL Eq. (7). Is it also the optimal solution of f-divergence used in the algorithm?" Eq. (8) looks not the same as the paragraph above Lemma 2 "\bar{\pi} = \pi_\theta" to me. If Eq. (8) is not the optimal solution of Eq. (11), the update in Alg. 1 is somewhat problematic and other better choices exist. Since Algorithm 1 explicitly uses f-divergence, I think at least this point should be clarified by the authors rather than my guess.