Guided Adaptive Credit Assignment for Sample Efficient Policy Optimization
Authors: Hao Liu
Richard Socher
Caiming Xiong
Venue:  (2020)
Keywords: credit assignment
sparse reward
policy optimization
sample efficiency

Abstract: 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 more general 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 \textsc{WikiTableQuestions} and \textsc{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.

Under review conference paper at ICLR 2020
GUIDED ADAPTIVE CREDIT ASSIGNMENT FOR SAMPLE EFFICIENT POLICY OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
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 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 more general credit assignment named guided adaptive credit Designment(GACan The benefit of GACA is principled way of utilizing off-policy samples. The elfectiveness of proposed algorithm is demonstrated on the challenging VIETTIBlEQUSTTOON and WIKSQL 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 failess execution feedback is available. Empirical studies show that our method significantly improves the sample efficiency of the state-of- state-of-the-art policy optimization approaches.
INTRODUCTION
Deep reinforcement learning (RL) provides a general framework for solving challenging goal-oriented sequential decision- problems, it has recently achieved remarkable successes in advancing
the frontier of AT technologies (Silver et al. 2016 Mnih & Kavukcuoglu 2013 Silver et al.] 2017
Andrychowicz et al., 2017). Policy gradient (PG) (akaade 2002 Mnih et al. 2016 Schulman
et al. 2015) one of the most successful model-free RL approaches that has been widely applied
to high dimensional continuous control, vision-based robotics, playing video games, and program
synthesis (Liang et al. 2018 Guu et al. 2017: Bunel et al., 2018).
Despite these successes, a key problem of policy gradient methods is that it often suffers from high sample complexity in sparse reward tasks. In sparse reward tasks, there only a binary signal which indicate successful task completion but without carefully shaped reward function to properly guide the policy optimization. A naive yet effective solution to address this challenge is by exploring many diverse samples and re-labelling visited states as goal states during training (sce e.g. (Andrychowicz eet al. 2017 Pong et al.] (201)). Regardless of the cost of generating large samples and the bias introduced during comparison, in many practical applications like program synthesis, it may not even be possible to compare between different states. A variety of credit assignment techniques have been proposed for policy gradient methods in settings where comparison of states is not available
(See e.g. [iang et al. 2018 Agarwal et. al. 2019 and Norouzi et al. 2016).
In this work, we focus entropy regularized reinforcement learning. Instead of directly optimizing the RL objective, which is hard in sparse reward tasks, we sort to optimize policy to approximate a learnable prior distribution called guiding prior distribution. By using so-called f-divergence (Csiszár

---

Under review conference paper at ICLR 2020
et al, 2004 Liese & Vajda 2006 Nowozin al, 2016 Wang al. 2018) which defines broad class of divergence(e..g. KL and reverse KL divergence) that are sufficient to fully characterize the distributions under consideration, we construct class of gradient estimator that allow us to generalize previous credit assignment methods. The neat property is that the gradient estimator can adaptively optimiie policy based on divergence wetween itself and the prior distribution. is natural to expect this more flexible gradient estimator provide an adaplive trade-off wetw different credit assignment methods, in addition, it also has a good property such that all off- samples are utilized to compute gradient, which yield powerful credit assignment. Our approach tremendously extends the existing credit assignment used including REINFORCE (Sutton et al.
2000
Williams 1992), maximum marginal (MM))))ood(MMM)) (Dempster et al. 1977 Gun et al.
2017
MAPO
(Liang et al. 2018), iterative maximum likelihood Liang et al. 2017 Abolatia
2018), and RAML Norouuzi et al., 2016
We evaluate our hot on variely of lasks, including the challenging WIKISQL (Zhong et al. 2017 and WINTTABLEQUESTIONS (Pasupat & Liang, 2015) program synthesis benchmarks, and an instruction following navigation task TEXT |Agarall et al. 2019]. Our experiments show that GACA greatly improves the sample efficiency of the entire policy optimization, and leads to significant higher asymptotic performance over previous state-of-tho-art methods.
2 BACKGROUND
2.1 REINFORCEMENT LEARNING AND POLICY OPTIMIZAIION
Reinforcement learning (RT.) considers the problem of finding an optimal policy for an agent that interacts with an uncertain environment and collects reward per action. The goal of the agent maximize its cumulative reward. Formally, this problem process over the environment states E S and agent actions & Z, with the environment dynamics defined by the transition probability T(s'|s, 2) and reward function r(st, 21); which yields reward immediately following the action 2, performed in state 8t. The agent's action & is selected by a conditional probability distribution (=(ss) called policy.
be viewed as Markov decision
In policy gradient methods, we consider a set of candidate policies <=(=|)) parameterized by and obtain the optimal policy by maximizing the expected cumulative reward or return
((0) (m (r(s,))],
where Pa (s) E Prpss s) is the normalized discounted state visitation distribution with discount factor 7 E [0, 1).
2.2 SPARSE REWARD REINFORCEMENT LEARNING AND CREDIT ASSIGNMENT
Auto-regressive model often used as a policy many real world applications including program synthesis and combinational optimization (Liang et al. 2018 Guu et al. 2017 In this work, we consider the following form of policy distribution.
II [x]
(z(2)5)) so)
TT Bct.8))
(1)
where zςz ($1..... .........))) 2-1) denotes prefix of the action sequence Su Z denotes some context information about the task, such as initial state or goal state (Andrychowica et al. 2017). And To(2)s0) (o) satisfy Vz E 2 (a(2)))) 2 0 and (= 1.
In environments where dense reward function is not available, only small fraction of the agents' experiences will be useful to compute gradient to optimize policy, lcading to substantial high
2

---

Under review conference paper at ICLR 2020
sample complexity. Therefore, it is of great practical importance develop algorithms which can Iearn from binary signal indicating successful task completion or other unshaped reward signal. In Section we will describe method to efficiently utilize high-reward and zero-reward trajectories this challenge. We will evaluate the method on program synthesis and in- structions following navigation, both are particular sparse reward tasks. Figure 1 shows example of sparse reward program synthesis. The model needs to discover the programs that can generate the correct answer in given context and generalizes over un- seen context.
Rank
Player
County
address
Nicky English
Tipperary
2
Mark Corrigan
Offaly
"Which player
Joe Hennessy
Kerry
ranked the most?"
Finbarr Delaney
Cork
R(z)
5
Nicky English
Tipperary [(Execute(z)
Adrian Ronan
Kilkenny "Nicky English")
7
Nicky English Tipperary
Figure 1: An example of the program synthesis task, where an agent presented with context so consists of natural language question and a table, and is asked to generate a program (21. 22, ... 22, 2n). The agent receives a reward of if exccution of z on the relevant data table leads to the correct answer y (e.g., "Nicky English")).
We consider goal-conditioned rein- forcement learning from sparse re- wards. This constitutes a modification to the reward function such that it depends a goal G, such that r(z, 8 G R. Every episode starts with sampling a state-goal pair from some distribution p(#0. g). Unlike the state, the goal stays fixed for the whole episode. At every time step, action is chosen according to some policy n, which is expressed as a function of the state and the goal, π : S x G + Z. Therefore, we apply the following sparse reward function:
[1 F()
r(z, 9, 8)
(2)
{0, otherwise
where g is a goal and F(z) denotes evaluating action sequence on the task that controls when the goal is considered completed. The objective is given by
[(0) E.g - g. so)] Bxo.orp(so.a) Bzwz/r(z, mo)oo()(so)
(3)
= -m Ee Bl-z/r(2, 8p) II <( Zet, 8o)],
(4)
where И is the length of the trajectory. We can calculate the gradient of Equation with REIN- FORCE (Williams) 1992 and estimate it using Monte Carlo samples.
VoJ(O)= = E. Ppo.0~~((000)) E Vo log no (2)s0))((, g, so)],
55)
Unfortumately, since the search space of programs is very large, most samples z have reward R(z) thus have no contribution to the gradient estimation in Equation 5 Besides, because the variance of
score function estimators is very high, is challenging to estimate the gradient Equation with a small number of successful programs. Previous method Liang et al. (2018) propose to estimale gradient as a combination of expectations inside and outside successful programs buffer, however it's still restricted to use successful programs only, and suffers from high sample complexity.
3 METHOD
In this section, we fist introduce entropy regularized reinforcement learning and describe optimizing policy via minimizing discrepancy between itself and prior in Section 3.1 and then introduce Icarnable prior to guide policy optimization in Section 3.2 finally we introduce a class of flexible adaptive gradient estimator Section 3.3
3

---

Under review conference paper at ICLR 2020
3.1 ENTROPY REGULARIZED REINFORCEMENT LEARNING.
We consider a general entropy regularized objective (Ziebart et al. 2008 which favors stochastic policies by augmenting the objective with the relative entropy of the policy,
(())
9o + (T)
(6)
where regularization weight, (x(o(())))) is the entropy regularization term. Entropy based policy optimization is a general framework that has gained many successes in variety of tasks (see e.g.. Haarnoja et al. 2018 Teh et al. 2017). Maximizing Equation O is equivalent to minimizing the Kullback Leibler discrepancy between policy To Te(z(so) and an energy based prior distribution.
Lemma 1. Mazimizing Equation 0 is equivalent to minimizing the following objective,
L(0) s Ez (ADLL (To(Z)so))] * exp exp ((1((2g.00) (x
V(sul)
(7)
is 'soft-version' of value function, serving as a nor- malization constant here. From Equation we aim to approximate the distribution 7(z) with a distribution from family {TO (z](0) Gj; where 0 is the parameter that we want optimize, and (2(08))) is represented as an autoregressive policy in Equation [ In environments where only sparse reward function is available, only a small fraction of the agent's samples will be useful to compute gradient to optimize policy, thus Equation @ often leads to a substantial sample complexity. Equation soems would be a better objective since all of the agent's 's samples can contribute to the minimization of KI-divergence, however, for a given Su, the prior distribution is simply binary value function over which not suitable. Intuitively, we would like F(z) weighs higher on 'almost success" action sequences z and weighs lower on 'far from success' action sequences z.
where (s0) = A log fag ex,(
3.2 GUIDING PRIOR DISTRIBUTION.
In this part, we will describe how to learn the prior distribution #(z) to guide policy optimization.
Proposition 1. Given policy Te(2)s)), new guiding prior distribution R(z) that minimizes the discrepancy in Equation is given by,
F(z) E pp. [To(Z[so)],
(8)
and the minimization of Equation equals to mulual information belween so and
Esp.g~p(s0.0) [KL (TT(Z]50) || #(z))] = I(s0:z)
(9)
Proof. See Appendix C for details.
Proposition 1 indicates that alternatively optimizing to and 7(x) leads to a complex mixture distribution of 7 (z), increasing the expressive power of prior for credit assignment. Since Equation S minimizes DKL (TO (z]s)) F(z)) and leads to mutual information between so and therefore the entropy regularized objective becomes the following mutual information regularized objective,
((Ø)
so) - Al(us
(10)
Equation 10 draws connection with rate distortion theory (Shannon 1959 Cover & Thomas,
2012
intuitively, the policy no (z))s) is encouraged to discard reward-irrelevant information in context. so subject to a limited channel capacity given by T(so; 2). In the next section, we will present a class of gradient estimator that can adaptively update policy distribution to approximate the guiding prior.
4

---

Under review conference paper at ICLR 2020
3.3 ADAPTIVE GRADIENT ESTIMATION.
While DKL (Z) (()) is the typical divergence measure widely used in variational inference and reinforcement learning (see e.g. Wainwright et al. 2008 Abdolmaleki et al., 2018 Hoffman et al. 2013), it often leads to model collapse because of its mode-sceking property. Therefore, often gives a suboptimal model [0(2)s)). It therefore natural to consider alternative divergence measures. We approach this problem by minimizzng the general
directly optimizing Equation 7
f-divergence {Ali & Silvey 1966:
Morimoto 1963 between ((z) and Tz(2 (()])))) f-divergence includes
a large spectrum of divergences e.g.. KL and reverse KL divergence) and is shown be powerful
in various settings [Nowozin et al. 2016
Wang et al. 2018 Ghasemipour et al. 2019
((2)
s()]
(r( || no To 80))
E. (elot(
(11)
where f: R2 RR is any twice-differentiable convex function. Tt can be shown by Jensen's inequality that Dr(p |I g) 2 O for any p and q. Further, if f(t) is strictly convex at t = 1, then Tz (z))))))) (F(
implies #(z) = ne (z)))))). We use stochastic optimization to minimizing Equation then gradient of Equation 11 is given by:
Lemma 2. Assume f is differentiable convex function and log (o(2(s)) is differentiable w.r.t. 0. For f-divergence defined in equation 17 we have
To (2) (z|
VoDr(a(2) (o(2)so)) = - -E (aloo)
Ps
Va log T2(2
(12)
(z)
where py(() (() (()).
Proof. See Appendix B for details or Wang et al. 2018
Equation 12 shows that the gradient of f-divergence between (0(28))) and #(z) can be specified through Ps or f. In next section, we will describe how to adaptive choose Ps or f based on the discrepancy between (z(2))0) and (z). Since the space of Z is enumerable and the environment is deterministic, the expectation over z ~ (0(2)))) can be efficiently computed through sampling in replay buffer. We proceed to describe how to estimate this gradient with samples.
3.4 FINAL ALGORITHM.
Given Equation 12 it's natural to ask how to estimate the gradient, naive way is simply store past. trajectories in replay buffer and sample random mini-batch from to compute the gradient. However this approach suffers from the fact that large fraction of sampled trajectories have zero-reward, which leads to high sample complexity. We propose to save high-reward trajectories and zero-reward trajectories into two separated replay buffers and estimate the following gradient:
Given replay buffers B and C for saving high-reward and zero-reward trajectories, an unbiased and low variance estimation is given by,
Proposition 2.
voDr(T(Z)
mo(2]so))=
To (2(50) (z)
AT (To(2(8))
Wgg WggB PS
Vo log (z) WeB (2)2)
Vo log (z(ss) (13)
T (z)
5

---

Under review conference paper at ICLR 2020
where wB and wB represent the total probability of trajectories in replay buffers and C respectively, wg + we 1, and
az 1x)= = = (o(2ss))/wB
izE B
if fz E B if z E
IZEC No (2)
(14)
To(z)so)/we
Proof. Soe Appendix D for details.
The gradient estimation uses high-reward trajectories thus T0(280)) will not forget them, the estimation also utilize zero-reward trajectories in the past, which improves sample effi- ciency. The corresponding framework shown in Figure ? Note that different from MAPO where they also use a buffer to save successful programs, Equation 13 differs in that all off- policy samples can be used to estimate gradient, which leads to a higher sample efficiency.
We follow Wang et al. (0188) in choosing f-divergence such that achieve a trade-off between exploration and exploitation, specifi- cally, let {z,) } be drawn from buffers B and C and w; = π (221(80)/T(z)) then we substitute Pf (F)(())))/=(2) mate tail probability given by n The benefit of doing this is policy distribution no (z)s)) can adaptively coverage and approxi- mate prior distribution F(z).
High Program Bufler
Gradient Estimation using GACA
update with gradient
Zaro remard Programs ams Buffer
with the inverse of approxi- f)-
sampling polrcy
_
samplig poicy
Actor sampling with updated poiryy
In practice, to overcome cold start problem in sparse reward policy optimization, we fol- low Liang al. (2018) to clip Wg a given range such that = max(wx, wi) and wys min(ws, w.) where wi S Wh- Note that Equa- tion 13 generalizee previous work in credit assign- ment including REINFORCE, MML (Dempster
Figure 2: Overview of GACA: consists of mul- tiple actors for sampling and storing high reward episodes into buffer B and zero reward episodes into buffer C, gradient is estimated at central learner periodically using samples from both B,
based on Equation 13
ct al. 1977 Berant al. 2013 Guu et al. 2017
MAPO Liang et al. 2018), RAML Norouui et al. 2016) and IML (Liang et al. 2017 Abolata
et al. 2018). It is natural to expect this more fiexible gradient estimator provide
adaptive
trade-oll between different credit assignment. methods and can yield powerful credit. assignment. Due to page limit, we leave discussions and proofs around generalization in Appendix
[ Combining
Proportion and Proportion 2 together, we summarize the main algorithm in Algorithm
4 EXPERIMENT
We first introduce the set up of experiments, then evaluate GACA on two sparse reward program synthesis benchmarks WIKITABLEQUESTIONS and WIKISQL, and an instruction following sparse reward navigation task.
4.1 EXPERIMENTAL SETUP
TULEUQABLEURSSTINN Pasuuat & Liang 2015) contains 2,108 tables and 18,496 question-answer pairs build from tables extracted from Wikipodia. WIKISQL (Zhong al. 2017 is recent
6

---

Under review conference paper at ICLR 2020
Algorithm 1 Guided Adaptive Credit Assignment for Sample Efficient Policy Optimization
Require:
Training data p(5o: g), random initialized policy Te (2(2(s0), uniform initialized prior ((z),
high-reward and zero-reward trajectory buffers B and C, and clipping thresholds wy and wn. repeat
Sample initial states and goals {80.g) from data distribution p(so,.))
Collect trajectories with ma(2(=0) given {*o, g) and push trajectories into replay buffers and C accordling to their rewards.
Draw } from buffers and C through stratified sampling, compute wy and we Compute tail probability n
= t), where w, (Zz ())
Update policy distribution no (0(2880) with Equation 13 by substituting PJ (2))(()))) with the inverse of tail probability
Compute new guiding prior distribution Fzz) (so.gr((so.g) [Te(2])))]
until converge early stop
large scale dataset on learning natural language interfaces for databases. It contains 24,241 tables extracted from Wikipedia and 80,654 question-proge pairs. is annotated with pro- grams (SQL). In both datascts, qucstion-answen split into train, validation, and test sets. Examples of generated pro- grams are shown in Fig- ure 5 The policy needs to generate correct pro- grams from binary feed- back, making these two benchmarks very challeng-
ing. We also evaluate
GACA on instruction fol- lowing navigation environ- ment TEXTWORLD (Agar wal et al. 2019). The task instruction following navigation in a maze size N x N with K deadly traps distributed randomly over the maze. An agent given need language instruction which outlines an optimal path that the agent can take to reach the goal, the agent needs to generate a sequence of actions and the agent receives a reward of succeeds in reaching the goal within certain number of steps, otherwise 0. An example of this task For details experiments, refer Appendix F
41.
1998
1300
500
1000
Traazng Sigp
Trazzng
MAPO
Figure Comparing GACA and baselines on benchmarks. The plot is average of runs with bar of one standard deviation.
shown Figure 5
4.2 COMPARING GACA WITH BASELINES
Firstly, we compare GACA with several bascline mothods that are special cases of GACA, to show the effectiveness of guiding prior and adaptive gradient estimation. We briefty introduce each baseline method here and leave the detailed discussion and proof of generalization in Appendix E REINFORCE: REINFORCE maximizes expected return, we use on-policy samples to estimale the gradient V.JRL = Exa.gr-p(so.))) (0)))((()s))..... V log Te (z) (r, 9)]-
IML: Iterative maximize likelihood (Liang et al. 2017 Abolafia et al. 2018) uniformly maxi- mizes the likelihood of all the high-reward trajectorics past experience, the gradient is given by
7

---

Under review conference paper at ICLR 2020
VIJ/ML -xo.gmpp(so.s) EeEB Ve log (e(2(s))r(z, so.9).
RAML: Reward Augmented Maximum Likelihood (Norouzi al.
2016) is a more general variant
of IML, which weights oft-policy samples with an energy based prior distribution in Equation
JRAML Eso.gr-((o..)) (z>2=(z) log To (0(2))))r(2 80. g), where T(z)
exp (+(2z, 80 g) (())).
MML: Maximize Marginal Likelihood (Dempster et al., 1977 Berant. et al., 2013 maximizes
the marginal probability of the replay buffer B. The gradient of JMML is given by VoJUML.
E gg EEES Eeen #o(E)e))
xa(a)s)) (((a)ea)" r(z, Su. log Te(z)s)).
MAPO PAPOO/MARE MAPOX: Momory Augmented Policy Optimization (Liang et al. 2018) is a recent method for reusing high-reward trajectories, it maximizes the expected reward and estimate the gradient with off-policy high-reward trajectories: VaJMAPO = (1 (evettt))))))e Vo log No (2) (0: 80. + aBZass (oosss(Vn Vo To (z)))))r)z, 80, g)l, where is weight equals to the total probability of high-reward trajectory in buffer B. MAPOX (Agawaal ct al. 2019) improves MAPO by rumning MAPO on data collected by IML.
a a))ppp..r-pp(e (z))())))
WIKI WIRITABLEQUESTIONN
WIKISLL Test
Dataset
Method
Val
Test
Improvement
Val
Improvement
REINFORCE
< 10
< 10
< 10
< 10
IML
35.4
36.8 + 0.4
+7.8
69.3 0.5
7..1
+ 6.2
RAML
35.4
35.9
+8.7
57.5
0.3
+14.9
MML
3.3 0.7
+4.9
6.2
7.17
+5.6
MAPO
4.1
42.8
+1.8
71.9
7.1
+3.8
МАPOX
42.5
0.4
+1.1
7.5
74.9
+1.4
GACA w/o GP
13.80..4
44.2
74.6
0.2
GACA w/o AG
0.5
44.1 1 0.3
74.9 0.3
75.2
GACA
45.1 1 0.3
44.6 1 0.2
75.7 1 0.3
76.3 0.1
Table 1: Comparison to various credit ussignment methods on WIRTTABLEQQESTTONS and WIKIQQL benchmarks. We report accuracy, and its standard deviation test sets based 5 runs.
We first compare GACA with its various special cases sparse reward program synthesis benchmarks, results are shown in Fig- ure 3 and Table ! the comparison shows that noticeably improves upon previous methods in terms of both sample efficiency and asymptotic performance significantly by performing better crodit assigmment. The ablation study shows that both adaptive gradient estimation(AG) and guiding prior(GP) improve performance. The improvement over MAPO demonstrates that reusing all off-policy trajectories can greatly improve policy, the improvement over IML. and MAPOX shows that encouraging exploration with reverse KL-divergence is not enough because it's simply impossible to
Method
Val.
Test
Oracle
95.7(+1.3) 92.6))
MAPO 73.1(+2.11 68.5(12.6)
MeRL 75.3(+1.66 (2.2
BoRL
83.0(+3.6) 74.5(12.5)
GACA
87.3(+4.1) 80.1
Figure 4: Evaluation of GACA on TEXTWORLD with state-of-the-art. explore such large state space, while guiding prior and adaptive gradient estimation provide efficient way exploration and exploitation. We also analyzed a trained model qualitatively on program synthesis tasks and see that it can generate fairly complex programs, see Appendix G for some examples of generated programs. Our experiments follow the settings of MAPO (Liang et al. 2018) and McRL (Agarwal al. 2019 refer Appendix for more details experiments.
4.3 COMPARING GACA WITH STAEE-OF-TIEE-AT
We present the results on sparse reward program synthesis in Table and Table 2 The results of TEXTWORLD are shown in Table g GACA outperforms most recent stato-of-tho-art methods BoRL
8

---

Under review conference paper at ICLR 2020
and MeRL proposed Agarwal al. (2019) by large margin. The results demonstrate the efficacy of the proposed credit assignment compared to previous SOTA credit assignment methods. We would like point out that GACA is general method and can be combined with these techniques to further boost performance.
Method
E.S.
Val.
Test
Method
E.S.
Val.
Test
MAPO
1
42.3
42.8
-5.8
MAPO
71.9
72.5
+6.3
MeRL
1
44.1
43.2
55.4
MeRL
74.9
74.8
+4.0
BoRL
1
42.9
43.8
-4.8
BoRL
74.6
74.2
+4.6
MAPO (ensemble)
10
46.3
2.3
MAPO (ensemble)
10
74.9
+3.9
MeRL (ensemble)
10
46.9
-.77
MeRL (ensemble)
10
77.1
+1.7
GACA
45.1
44.6
GACA
75.7
76.3
GACA (ensemble)
10
48.6
GACA (ensemble)
10
78.8
Table Evaluation GACA with state-of-the-art
Table 3: Evaluation of GACA with state-of-the-at on WIKISQL.
on WIR/LABLEQUESTTINS..
5 RELATED WORK
Credit assignment is critical part of various sequential decision making methods. Guu et al. (2117) builds connection between REINFORCE and MML by proposing hybrid approaches to take advantages of both MML and REINFORCE. Entropy based policy optimization is widely used in reinforcement learning (Ziebart et al. 2008 Schulman et al. 2017), recently entropy based off off-policy policy optimization is also proposed to approximate optimal policy distribution by minimizing the
Kullback-Leibler((( Leibler (KL) divergence between policy and optimal distribution (Haarnoja al. 2018).
Norouzi et al. (2016) considers an alternative direction of the KL divergence, where samples from exponential payoff distribution are used to estimate gradient. Recent work Grau-Moya also propose to learn the prior distribution for Q-lcarning and show that this leads to mutual information regularization. Experience replay is widely used in sparse reward reinforcement learning in order to exploit past. high reward orctss (Gangwani el al. 2019 Liang et al. 2018 Oh el al. 2018: Abolafia et. al., (018)). (Andyychowis et al. (2017) proposes to re-label visited states as goal states during training. More recent. progress includes meta-learning the reward(such as discount factor) (Xu et al. 2018). Weber et al. 2019 provides a comprehensive review credit assignment methods in stochastic computation graph. Recently, there
(2019)
surge of interest in applying policy optimization in program henis through sparse supervision (Krishnamurthy et al. 2017 Guu ct al. 2017 Liang et al. 2017 2018 Agarwal ct al. 2019). GACA differs from previous methods by
enabling reusing oll-policy samples through learned prior and generalized gradient estimation.
6 CONCLUSION
We developed the Guided Adaptive Credit (asigument(GACA)) a new and general credit assignment method for oblaining sample elliciency of policy oplimization in sparse reward setting. Our method generalizes several previous approaches. We demonstrated its practical advantages over existing methods, including MML, IML, REINFORCE, etc, several challenging sparse reward tasks. In the future, we will investigate how to extend GACA to stochastic environments and apply it to robot learning from binary reward foedback. We would also like to point out that our method can be useful in other challenging tasks with deterministic environments such as combinational optimization and structural prediction where credit assignment from binary foedback remains major challenge.
9

---

Under review conference paper at ICLR 2020
REFERENCES
Abbas Abdolmaleki, Jost Tobias Springenberg, Yuval Tassa, Remi Munos, Nicolas Heess, and Martin Riedmiller. Maximum a posteriori policy optimisation. In International Conference on Learning Representations, 2018.
Daniel A Abolafia, Mohammad Norouzi, Jonathan Shen, Rui Zhao, and Quoc V Le. Neural program syuthesis with priority queue training. arXiv preprint 2Xiv:1801.03520 2018.
Rishabh Agarwal, Chen Liang, Dale Schuurmans, and Mohammad Norouzi. Learning to generalize from sparse and underspecified rewards. ICML, 2019.
Syed Mumtaz Ali and Samuel D Silvey. A general class of coefficients of divergence of one distribution from another. Journal of the Royal Statistical Society: Series B (Methodological), 28(1):131-142, 1966.
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojciech Zaremba. Hindsight experience replay. In Advances in Neural Information Processing Systems, pp. 5048 5058, 2017.
Jonathan Berant, Andrew Chou, Roy Frostig, and Percy Liang, Semantic parsing on freebase from question-answer pairs. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pp. 1683-1544, 2013.
Rudy Bunel, Matthew Hausknocht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Lever- aging grammar and reinforcement learning for neural program synthesis. arXiv preprint Xrxiv:1805, 04276, 2018
Thomas M Cover and Joy A Thomas. Elements of information theory. John Wiley-Sons, 2012.
Imre Csiszár, Paul C Shields, et al. Information theory and statistics: A tutorial. Foundations and Trends in Communications and Information Theory, 14):4117-228, 2004.
Arthur P Dempster, Nan M Laird, and Donald B Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Sociely: Series B (Methodological), 39(1: 1 1-22, 1977.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Volodymyr Mníh, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, Tain Dunning, et al. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. In International Conference on Machine Learning, pp. 1406 1415, 2018.
Tanmay Gangwani, Qiang Liu, and Jian Peng. Learning self-imitating diverse policies. In Interna- tional Conference on Learning Representations, 2019.
Seyed Kamyar Seyed Ghasemipour, Richard Zemel, and Shixiang Gu. A divergence minimization perspective on imitation learning methods. arXiv preprint 1rXim:1111.02255 2019.
Jordi Gran-Moya, Felix Leibfried, and Peter Vrancx. Soft q-laarning with mutual-information regularization. In International Conference Learning Representations, 2019.
Kelvin Gun, Panupong Pasupat, Evan Liu, and Percy Liang. From language to programs: Bridging reinforcement learning and maximum marginal likelihood. In Proceedings of the 55th Annual Meeting of the Association for Computational Lónguistics (Volume 1: Long Papers), pp. 1051-1062, Vancouver, Canada, July 2017. Association for Computational Linguistics. doi: 10.18653 P17-1097.
10

---

Under review conference paper at ICLR 2020
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In ICML. PMLR, 2018.
Malthew D Hoflman, David M Blei, Chong Wang, and John Paisley. Stochastic variational inference.
The Journal of Machine Learning Research, 14(1):1303 1347, 2013.
Sham M Kakade. A natural policy gradient. In Advances in Neural Information Processing Systems, pp. 1531-1538, 2002.
Diederick P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Jayant Krishnamurthy, Pradeep Dasigi, and Matt Gardner. Neural semantic parsing with type constraints for semi-structured tables. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pp. 1516-1526, 2017.
Chen Liang, Jonathan Berant, Quoc Le, Kenneth D. Forbus, and Ni Lao. Neural symbolic machines: Learning semantic parsers on freebase with weak supervision. In Proceedings of the 55th Annual Meeting of the Association for Compulational Linguistics (Volume 1: Long Papers), pp. 23 33.
Association for Computational Linguistics, 2017. doi: 10. 10.18653/ ///55//1//111 11/P17-1003.
Chen Liang, Mohammad Norouzi, Jonathan Berant, Quoc Le, and Ni Lao. Memory augmented policy optimization for program synthesis with generalization. Aduances in Neural Information Processing SystemssNeurIIPS) 2018.
Friedrich Liese and Igor Vajda. On divergences and informations in statistics and information theory. IEEE Transactions on Information Theory, 52(10):4394 4412, 2006.
Andriy Mnih and Koray Karukcuoglu. Learning word emboddings efficiently with noise-contrastive estination. In Advances in neural information processing systems, pp. 2265 2273, 2013.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference on machine learning, pp. 1928 1937, 2016.
Tetsuzo Morimoto. Markov processes and the h-theorem. Journal of the Plyysical Sociely of Japon, 18(3):328- 321-33118131113 1963.
Mohammad Norouzi, Samy Bengio, Navdeep Jaitly, Mike Schuster, Yonghui Wu, Dale Schuurmans, ct al. Reward augmented maximum likelihood for neural structured prediction. In Advances In Neural Information Processing Systems, pp. 1723-1731. 2016.
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan: Training generative neural samplers using variational divergence minimization. In Advances in newral information processing systems, pp. 271 279, 2016.
Junhyuk Oh, Yijie Guo, Satinder Singh, and Honglak Lee. Self ioff-imitation learning, In ICML, 2018
Panupong Pasupat and Percy Liang. Compositional semantic parsing on semi-structured tables. In Proceedings of the 53rd Annual Meeting of the Association for Compulational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp- 1470-1480. Association for Computational Linguistics, 2015. doi: 10.3115/v1 111111//11P1-111//
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in Py Torch. In NIPS Autodiff Workshop, 2017.
11

---

Under review conference paper at ICLR 2020
Vitchyr H Pong, Murtaza Dalal, Steven Lin, Ashvin Nair, Shikhar Bahl, and Sergey Levine. Skew-fit: State-covering self-supervised reinforcement learning. arXw preprint arXiv:1003 NXN:19030006988 2019.
John Schulman, Sergey Levine, Philipp Moritz, Michael I. Jordan, and Pieter Abbeel. Trust region
policy optimization. International Conference on Machine Learning, 2015.
John Schulman, Xi Chen, and Pieter Abbeel. Equivalence between policy gradients and soft q-learning- arxi preprinl arxi: 00011004.00000 704400440, 2017.
Claude E Shannon. Coding theorems for a discrete source with fidelity criterion. IRE Nat. Conv. Rec, 4(142-163):1, 1959.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Autonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484 489, 2016.
David Silver, Julian Schrittwieser, Karen Simonyan, Toannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676)3354, 2017.
Richard Sutton, David A McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in neural information processing systems, pp. 1057-1063, 2000.
Yee Teh, Victor Bapst, Wojciech M Czarnecki, John Quan, James Kirkpatrick, Raia Hadsell, Nicolas Heess, and Razvan Pascanu. Distral: Robust multitask reinforcement learning. In Advances in Newral Information Processing Systems, pp. 1496-4506, 2017.
Martin J Wainwright, Michael Jordan, el al. Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning, 1(1-22 (1-2):1 305, 2008.
Dilin Wang, Hao Liu, and Qiang Liu. Variational inference with tail-adaptive f-divergence. In Advances in Newral Information Processing Systems, pp. 5742 5752, 2018.
Théophane Weber, Nicolas Heess, Lars Buesing, and David Silver. Credit assignment techniques in stochastic computation graphs. arXiv preprint 1901.090000111 2019.
Ronald J Williams.
Simple statistical cradient-followigg algorithms for connectionist reinforcement learning, Machine learning, 8(3-4):229 256, 1992.
Zhongwen Xu, Hado P van Hasselt, and David Silver. Meta-gradient reinforcement learning. In Advances in Neural Information Processing Systems 31, pp. 2396-2407. 2018.
Victor Zhong, Caiming Xiong, and Richard Socher. Seq2sql: Generating structured queries from natural language using reinforcement learning. CoRR, abs/ 1709.00103, 2017.
Brian D Ziebart, Andrew Maas, Andrew Bagnell, and Anind K Dey. Maximum entropy inverse reinforcement learning. In Aaai, volume 8, pp. 1433 1438. Chicago, IL, USA, 2008.
12

---

Under review conference paper at ICLR 2020
A PROOF OF LEMMA
Proof. To derive Lemma consider the KT. divergence between mo(2|0)) and #(2) exp (1, (s)))), where ((so) log Ja-z exp(r(z,g, so)/A) is 'soft-version' of value function, serving as normalization constant here.
DkL (no (z)
F())
(x
[log Te (z((s))) (z)ss) log [()]]
(x
lo (o) r(zz., so) / log (ss)
Ex (x/s0) (Z))s)(z))o) r(z, 9, s0) //1| log ((5),
Rearranging,
E Ex so) [r(z, 9. sa)] + All (To
DDKL (To(Z)))) #(2) A log (so),
thus maximizing left hand side E (g)zo(a)ou) (r(2, + XH (z(so)) is equivalent to minimizing DkL (Ta(Z[s)) #(2)).
B PROOF OF LEMMA 2
Proof. To derive Lemma
2 consider that VoTT(Zz(s)) =o(2)3)) Vo log (z(20))) then we have
(aD)(#(z) || (z(2)s0))
F(2)
a(z)
Egg Bgg
Vof
+
Vo log To (2)
(z(ss)
TT( (z)
t (z))
#(z)
a(2)
Emo (x|s0)
V
+
Vo log To (2|su)
(z)(s0) (0)
Te (z) (s))
Te(())0)
क (z)
(z)
T(z) (T(2)
(xls0))
Vo log (z( +
Vo log To (2(2))))
(e(2)))))
(z(2)s))
(T)(2)0))
म (z)
=EEno(eloo)
log (2(
(7)()))))
where pf(1) = (1()) f()..
For convex function f, we have (1) 2 0, which implies ()) (')))) 2 0 on Le RR. thus of is monotonically increasing function on R4. If p is strictly increasing at t = 1, we have f is strictly convex at = 1, which guarantces (p q) imply p p= q.
C PROOF OF PROPOSITION
Let p(so) and p(z) denote the distribution of 8o, and z respectively, for notation simplicity, we omit g in the following derivation and simply use so p(5o) to represent 8o, 9 E p(so. g), and denote
13

---

Under review conference paper at ICLR 2020
7 (z) Bss)p(so) (TTO (z)(2))))], then we have
DKL (T0))))) p(5o)p(z)) (pT.((())) ((5))((2))
(()55)
Boo Benz log
p(50)p(z)
p(su)p(z)5))
- Be- log
p(so)
Tz))
Booop((s) Banz Bane log
p(z)
{z))
Expop(so) Benz log
p(z)
Ex DKL (#( || p(z))
0,
thus F(2) = E spmpp(e ( (2) [/00000]]]]]]) = arg mi)) (2o((o(50)To((lbo) p())))())) Substituting #(2) in E Exprp(so) (KL (z) p(5o)p(z))) we have
DRL. (p( (F) ((s0))
E Eoo z) log p(s0.21 z) p(so)p(z)
=)):
Thus B [z)(2))) (mo(
is the solution of the minimization objective, and DKL ((((5)))( || (z)) equals mutual information between state and action.
D PROOF OF PROPOSITION 2
Proof. To prove Equation 13 is an unbiased estimation Equation 12 note that we can either enumerate replay buffers B and C when the size of buffers small approximate sampling from both buffers according to the spocified ratio. any case, this gives us a stratified sampling estimator of Equation 12 which is unbiased and low variance.
E PROOF OF GENERALIZATION OF PREVIOUS CREDIT ASSIGNMENT METHODS
In this section, we discuss the connection between GACA and each credit assignment method, we will show that GACA is unified form of existing credit assignment method. Firstly, we summarize existing method in Table 4 it.
Then we describe each method and give proof of how to reduce GACA
E.1 REINFORCE:
REINFORCE maximizes the expected reward and estimate the gradient with on-policy samples JRL= Eso.graioo Ea-aa(()s 80. 9), the gradient of REINFORCE objective given by V (ea.grrp(so.g) (z Vo log no (z)so)r(z, 80.9). Apart from high variance issue in REINFORCE, also suffers from sparse reward because reward r(z, 8o. is low for most trajectories In contrast, GACA utilizes off- off-policy samples and still maintain unbiased gradient estimate. GACA reduces to REINFORCE by simply choosing Py constant 1.
14

---

Under review conference paper at ICLR 2020
Method
Optimization gradient
REINFORCE
V&JRL- -ss.g-p(Soos) B (m)so) ko) (V log (zl) 9) To 7z(z) (80)
MML
V VOJMML -Bgp.er((so.s)
Σ BEB To (2) r(z. su 9) Vo log To (2|su)
#EB
IML
VOJIML = E p(50.))) EZEB Vo log To (z) 80:9) 9) VAJMAPO Peo.grplonng [1
E Ee V log (2) s0.9)l
MАPO, МΑPOX
+
Vo log No (2)s0)))(())))) 80. 9) [0
RAML
VOJRAML E 50.g Ez log To (z ())
VoDr T
To 8o)) = wg 2 PS (To
Ve log To (z|su)
GACA
wwc +w (2]x)s (To (z|ss) V log (z)
Table The optimization gradient for various credit assignment algorithms. GACA generalizes existing methods by f-divergence based adaptive gradient estimation.
E.2 MML:
Maximize Marginal Likelihood(MMM)) (Dempster et al. 1977 Berant al. 2013 maximizes the marginal probability of the replay butter B, the objective of MML is given by JAML Exp.g~p(so.g) log ExEr To (o)r(z, so.g). The gradient of JAMI. has the form:
To (z(2))))
VaJuMI. (.o.grp(eo..))
V log (ogso(z)s))
(15)
BEB To (2)80)
2EB
Taking step in the direction of JMML ue-weights the probability of high-reward trajectory and thus attempts to up-weight each reward-earning trajectory. More discussion of this objective can be found in (Guu et al.) 2017 Liang et al. 2018).
Choosing wi = Equation 13 and clearly there exists a monotonically increasing function Ps satisfy P [u(a) sol
To (2
Choosing such py, GACA reduces to MML.
LEE (2
E.3 IML:
Iterative maximize likelihood[IML) [Lingg et al. 2017 Abolafia et al. 2018) uniformly maximizes the likelihood of all the high-reward trajectories in past experience. The objective is given by
JIAL. = F.. grrpenn(()) Faan n llgg na (0)0 80, g)]. The gradient. of IMT. is given by
VeJIML = _x
V log (z
(16)
ZEB
Choosing Ps = and be expressed as optimizing policy distribution by minimizing the reverse KL divergence between the parameterized policy distribution and an optimal policy distribution, i.c., DKL Dxl(=*1(=) where x² is the optimal distribution. It's well-known that reverse KL-divergence promotes model-covering, thus IML secks to explore diverse samples thus will have higher chance of collecting high-reward trajectories Recent work MAPOX (Agarwal et al. 2019 exploits this property of IML by running IML to collect diverse samples for training.
in Equation 13, GACA reduces to IML. For each given 80, 9, IML can
15

---

Under review conference paper at ICLR 2020
E.4 MAPO, MAPOX:
Memory Augmented Policy Optimization(MAPO) [Liang et al. 2018 is recent method for reusing high-reward trajectories, it maximizes the expected reward and estimate the gradient with off- off-policy high-reward trajectories. The gradient of MAPO is
VeJMAPO = -so.o--((soon) [[1 - Ex Vo log To (z(z)))))(,, so.9)
+ a
Σ
Vo log No (2))))))(( 80.
(17)
ZEB
where a is a weight equals to the total probability of high-reward trajectory z buffer B.
MAPOX (Agarwal et al. 2019: improves MAPO by running MAPO on trajectories collected with TMI. for exploration. As shown previously, IML. can be viewed as minimizing 'reverse' KT. divergence between policy distribution (2(()))) and the prior distribution, thus TMT, promotes exploration.
When choosing Pf #(2) log( #(x) and setting wg 1, GACA reduces MAPO.
(o(
E.5 RAML:
Reward Augmented Maximum Likelihood(RAML) Norouzi et al. 2016) is a more general variant of IML, which weights off off-po samples with energy based prior,
VoJRAML
1 22- log To (z (o)))))r(z s0, g)1
(18)
where a(z) exp (r(z, so. g) - V()))) is the energy based prior distribution defined in Equation Similar to IMI, for each given Su.9. 9. RAML can be expressed as optimizing the policy distribution by minimizing the KI. divergence between the parameterized policy distribution and energy based optimal policy distribution defined as exp (1 (0: g) V(z))). The gradicnt estimation Z, only few of them are high-reward and most trajectories cannot guide the policy learn good behavior, thus RAML sulfers from high sample complexity. Choosing
is over possible trajectories
Ps( [0(2]/0] To(2|s)]
=(x)
=(x) and wg 1 in Equation
13 GACA reduces to RAMI.
F EXPERIMENTS DETAILS
For WIR/TABBEEQURSTIONS, we follow the construction in Pasupat & Liang 2015 for converting a table into a directed graph that can be queried. The rows and cells are converted to graph nodes while column names become labeled directed edges. Each batch includes samples from 25 examples For WIKISLL, we follow the setting in Liang et al. (2018) for choosing the sampling batch size. Our model use a seq2seq model as Te (z(ss)) and two key-variable memory as high-reward buffer B and zero-reward buffer C, and associated with domain specific language interpreter (Liang al. (017)). Table shows a comparison GACA with varions baselines on two challenging sparse reward program synthesis tasks, where we also present an ablation study of each technique GACA. Specifically, we studied the performance of GACA w/o AG which represents GACA without adaptive gradient esti- mation(Section. 3.3), and GACA w/ GP which represents GACA without guiding prior In detail, GACA w AG means use standard KI-divergence to calculate gradient in Eq f-divergence, while GACA w/ GP means don't learn the prior policy distribution as in X but fix
prior(Section (Section 3.2).
13
instead
prior policy distribution to the energy based distribution as in 7 Our code is based open source implementation of MAPO (Liang el. al. 2018) which implements a distributed act.orllaarner archi- tecture Espeholt et al. (2018) Lo accelerate sampling through distributed actors. We also use open source code from MeRL [Agarwal et al. 2019), tail-adapted variational inference (Wang et al. 2018).
Our experiments follow the settings of MAPO (Liang et al. 2018) and MeRL (Agarwal et al.
2019
16

---

Under review conference paper at ICLR 2020
We port their code to PyTorch (Paskke et al, 2017 and implement GACA on top of them to conduct experiments. We will release the code later. Gradients are estimated and periodically updated through central learner (Espeholt et al. 2018). For TEXTWORL.DH we use set of 300 randomly generated environments with training and validation splits of 80% and 20% re- spectively following Agarwal et al. (019 The agent ovaluated on 300 unseen test environ- ments from the same distribution. An example of TEXTWORLD is shown in Figure 5 We used the Adam Optimizer (Kingma & Ba, 2015 for WIKISQL, WIKITABLE, and TEXTWORLD. We performed hyper- parameter sweeps via ran- dom search over the interval (10-1, 10-2) for learning ratc. All the hyperparameters are tumod the evaluation set.
Figure 5: Instruction following navigation in maze. An agent is presented with a sequence of (Left, Right, Up, Down) instructions. Given the input text, the agent the blue dot need to perform sequence of actions, and only receives reward of G QUALITATIVE RESULTS 1 if it reaches the goal at the orange star.
In order to evaluate the qualitative quality of the proposed method, we compare GACA with the recent slate-of-the-art MAPO on WIKITABLE- QUESTIONS. Figure B shows examples of generated programs from natural language queries using model trained with GACA or MAPO, the difference between generated programs show that sometimes GACA is capable of generating correct programs that capture the meaning of the natural language queries while MAPO generates either wrong answer programs or spurious programs.
textworld
17

---

Under review conference paper at ICLR 2020
Query Query/Generatee Generated Programs
Comment
Query nu-1147: Which opponent of the kansas city chiefs in 1987 saw total of more than 70,000 in attendance?
The program generated by MAPO leads to wrong answer, because it wrongly assume that the with largest number of atten- dance number is opponent of kansas city. Instead GACA captures the semantic meaning of the query and generates correct program.
MAPO: ro (argmax all rows caltendaace--umbert tive (hop ro r.pponent-string;
GACA: To = (filter> all rows [70,000] r.attendance- number); 7zes (hop r.opponent-string)
Query mu-1167: Who was the first oldest living presi- dent?
MAPO gets correct answer by chance because is spurious program, MAPO wrongly assumes the data is ordered, in contrast, GACA generates programs that capture underlying semantic information.
MAPO: ru (first all aal_aroooa___ rows]; Fass (hop ro r.president)
GACA: na (filter str contain any all rows joldest living president' r. r.became oldest llvvii__vveiiiiiie president-string ); fres hop ..president-stringg]
Query mu-3733: At least how many more people at- tended gamestorm 15 than gamestrom 13?
MAPO gets correct answer chance because spurious program, MAPO wrongly assumes the data ordered, contrast, GACA generates programs that capture underlying semantic information.
MAPO: ro (filter str contain any all rows [13] r.dates-
string); Fres hop To rrattendance-number
GACA: = (filter str contain any all rows [13] r.dates-
string): F1 (filter str contain any all rows [13] r.dates-
string); (diff ro rattendance-mumber))
Table Example of generated programs from models trained using MAPO and GACA on WIK- "TAALEQURSTIONS.
18


Reviews:
[{"review_id": "rkeNx7jTFB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes guided adaptive credit assignment (GACA) for policy gradient methods with sparse reward.\n\nGACA attacks the credit assignment problem by\n1) using entropy regularized RL objective (KL divergence), iteratively update prior \\bar{\\pi} and \\pi_\\theta;\n2) generalizing KL to f-divergence to avoid mode seeking behaviour of KL;\n3) 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).\n\nExperiments of program synthesis and instruction following are conducted, to show the proposed GACA outperform competitive baselines.\n\nAlthough the experimental results look promising, I have many concerns with respect to this paper as follows.\n\n1. The organization is bad. The main algorithm has been put into the appendix. It should appear in the paper.\n\n2. There are too many typos and errors in the paper and derivations, which quite affected reading and understanding.\nFor example:\nin Eq. (6), what is z \\sim Z? Should be z \\in Z? It also appears in many other places.\nin Eq. (7), there should not be \\sum_{z \\in Z} here.\nProof 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.)\nin 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.\nTypos, 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.\n\n3. 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.\n\n4. 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.\n\n5. 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.\nHowever, 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}\".\n\n6. 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.\n\nOverall, 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.\n\n=====Update=====\nThanks 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.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HJxsdYBcYS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis work proposed an off-policy framework for policy gradient approach called\nguided adaptive credit assignment (GACA) in a simplified setting of goal-oriented\nentropy regularized RL.\nGACA optimizes the policy via fitting a learnable prior distribution that using\nboth high reward trajectory and zero reward trajectory to improve the sample efficiency.  \nThe experiments on sparse reward tasks such as WikiTableQuestions and WikiSQL\ndemonstrate the effectiveness of the GACA, comparing with a set of advanced baselines.\n\n\nDetailed comments:\n\nOff-policy learning:\nThe Environment dynamic is not considered. The trajectory\nreward is determined by the initial state, goal, and the sequence of actions taken thereafter. The off-policy learning can be applied since the distribution of\ninitial state, and goal is not affected by the policy. This reduces to a\nweighted maximum likelihood problem. \n\nResolving the sparse reward issue:\nIn sparse reward tasks, many of trajectories have zero rewards, in order to utilize\nthe zero reward trajectory (since in the weighted problem those samples have no\ncontribution to the gradient). This work proposed to store the trajectories\ninto two replay buffers and samples from both of them separately. \nIntuitively, it is not clear to me why minimizing mutual information between z and\nreward would help the learning. I am suspecting the reason is that mutual information brings non-zero gradient for zero reward trajectories (given zero-reward trajectories indeed helps the learning). \nThe authors also claimed that KL divergence performs worse than f-divergence due to the mode seeking issue. Do the experiments in GACA w/o AG support this claim?\n\nAblation study:\nThe authors claimed that using zero reward trajectory can help with sample efficiency.\nI wonder what the performance would be if we drop the zero reward trajectory buffer if we have a reasonable high frequency to reach the high trajectory reward sequence. \nIs it necessary to incorporate the zero reward trajectory? \n\nWhat is the exact formula of GACA w/o GP and GACA w/o AG? \n\nThe proposed method consists of three parts (GP, AG, and separate buffer. ) \nTwo variants (w/o GP, w/o AG) of GACA is conducted in the ablation study. \nHow does the GACA perform if we drop the separate buffer? What if we incorporate separate buffer for baselines. Does GP/AG play an essential role in performance improvement,\ncomparing to a separate buffer? \n\n\nOther questions:\nSince the sequence of actions is considered as a group, the performance\nmay highly depend on the size of action space and horizon. \nWhat is the size of the horizon of the tested problems? \nWhat is the value of WB and WC in each experiment?\n\n\nMinor:\nThere are many typos or grammar issues in this version. e.g.,\nL 3, Page 4, learn-able prior\nLast paragraph, page 3, \" as as a combination of expectations\", \nPage, 15 \"is actually equals mutual\"\nEq 23 -> 24", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "HJgXnWk0Yr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors formulate the credit assignment method as minimizing the divergence between policy function and a learned prior distribution. Then they apply f-divergence optimization to avoid the model collapse in this framework. Empirical experiments are conducted on the program synthesis benchmark with sparse rewards. \n\nThe main contribution of this paper is applying f-divergence optimization on the program synthesis task for credit assignment. \n\n+ One of my concerns is that the experiment section is in a limited domain to argue it is a broad algorithm for credit assignment. The paper will be stronger if the comparison is applied in a distant domain like goal-based robot learning etc. With some experiments on a different domain, the paper will be more convincing. \n\n+ The improvement/margin in program synthesis task needed to be explained well, is the margin significant enough?  \n\n+ The paper could discuss more on related papers on program synthesis in the related work section as the main experiment is in this work.\n\n+ The authors claim that the two-buffer estimation is better and lead to better gradient estimation, but it is not demonstrated empirically or theoretically. It could be better if the ablation study is conducted in the experiment. Or the author could provide a theoretical analysis of why equation (13) is better. Moreover, the investigation of different choices of $w_b$ and $w_c$ is necessary.  \n\n+ Another study needed is the investigation of different divergences; the work will be stronger if a KL divergence version is compared. Otherwise, it is not clear how much the f-divergence will contribute to the performance. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a policy gradient algorithm related to entropy-regularized RL, that instead of the KL uses f-divergence to avoid mode collapse.

The reviewers found many technical issues with the presentation of the method, and the evaluation. In particular, the experiments are conducted on particular program synthesis tasks and show small margin improvements, while the algorithm is motivated by general sparse reward RL.

I recommend rejection at this time, but encourage the authors to take the feedback into account and resubmit an improved version elsewhere.
Decision: Reject