summaries: This paper introduces a new optimization method for text generation that improves upon directly optimizing MLE. It frames text generation learning as an off-policy reinforcement learning (RL) problem using demonstrations (the training examples). The authors also discuss why off-policy learning is more suitable for text generation than on-policy learning. After simplifications and approximations, the proposed optimization objective comes down to a form that is similar to MLE, but upweighs training examples that are more likely under the learned policy $\pi_\theta$ ("easy" examples) and having higher estimated rewards (considering the future). This paper proposes a method to train generative models of text using reinforcement learning from off-policy demonstrations. This helps solve the problems of exposure bias and mismatched objectives in standard learning schemes such as maximum likelihood estimation and policy gradient optimization on metrics like BLEU. In the proposed method (GOLD), the authors use policy gradient combined with importance weighting to train the model using just the off-policy demonstrations, i.e. human-written text. They experiment with three different reward formulations, and demonstrate improvements over MLE baselines on tasks like summarization and machine translation.  This paper formalizes training of conditional text generation models as an off-policy RL objective, specifically, in the limit case where samples are only obtained from the training data. The motivation behind this is that MLE objective optimizes recall -i.e. increasing the prob of all correct sequences that could be generated by humans as an output to a certain input context. While for certain tasks such as MT or summarization it is often sufficient to focus training to generate 1 single correct Translation or summary (see cons: for comments on the effect of this on sample diversity).  Therefore explorations in traditional PG by generating examples from an auto-reg model is unnecessary in this context. Therefore, using importance sampling, PG objective \E_{x \sim \pi_\theta} is modified to \E_{x \sim \pi_{data}} with the incorporation of the importance ratio and given a uniform sample probability of the training examples. As shown in eq(4), The gradient updates from this loss are identical to the standard MLE loss reweighted by the global reward and the current model probability of the training example, enforcing the model's current belief of the training data. This aligns with the previous intuition of enhancing precision on the expense of recall. Given this formulization this work experiments with three types of rewards: a constant reward and 2 MLE based rewards.    
abstractText: Current approaches to text generation largely rely on autoregressive models and maximum likelihood estimation. This paradigm leads to (i) diverse but low-quality samples due to mismatched learning objective and evaluation metric (likelihood vs. quality) and (ii) exposure bias due to mismatched history distributions (gold vs. model-generated). To alleviate these problems, we frame text generation as an offline reinforcement learning (RL) problem with expert demonstrations (i.e., the reference), where the goal is to maximize quality given model-generated histories. We propose GOLD (generation by off-policy learning from demonstrations): an easy-to-optimize algorithm that learns from the demonstrations by importance weighting. Intuitively, GOLD upweights confident tokens and downweights unconfident ones in the reference during training, avoiding optimization issues faced by prior RL approaches that rely on online data collection. According to both automatic and human evaluation, models trained by GOLD outperform those trained by MLE and policy gradient on summarization, question generation, and machine translation. Further, our models are less sensitive to decoding algorithms and alleviate exposure bias.
authors.name: Richard Yuanzhe Pang
authors.name: He He
references.authors: Roee Aharoni Yoav Goldberg
references.title: Split and rephrase: Better evaluation and stronger baselines. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)
references.authors: Daniel Andor Chris Alberti David Weiss Aliaksei Severyn Alessandro Presta Kuzman Ganchev Slav Petrov Michael Collins
references.title: Globally normalized transition-based neural networks. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)
references.authors: David Belanger Andrew McCallum
references.title: Structured prediction energy networks
references.venue: Proceedings of The 33rd International Conference on Machine Learning,
references.authors: Samy Bengio Oriol Vinyals Navdeep Jaitly Noam Shazeer
references.title: Scheduled sampling for sequence prediction with recurrent neural networks
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Massimo Caccia Lucas Caccia William Fedus Hugo Larochelle Joelle Pineau Laurent Charlin
references.title: Language gans falling short
references.venue: In International Conference on Learning Representations,
references.authors: Mauro Cettolo Jan Niehues Sebastian Stüker Luisa Bentivogli Marcello Federico
references.title: Report on the 11th IWSLT evaluation campaign
references.venue: In Proceedings of the International Workshop on Spoken Language Translation,
references.authors: Jaemin Cho Minjoon Seo Hannaneh Hajishirzi
references.title: Mixture content selection for diverse sequence generation
references.venue: In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLPIJCNLP),
references.authors: Kyunghyun Cho Bart van Merriënboer Caglar Gulcehre Dzmitry Bahdanau Fethi Bougares Holger Schwenk Yoshua Bengio
references.title: Learning phrase representations using RNN encoder–decoder for statistical machine translation
references.venue: In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP),
references.authors: Leshem Choshen Lior Fox Zohar Aizenbud Omri Abend
references.title: On the weaknesses of reinforcement learning for neural machine translation
references.venue: In International Conference on Learning Representations,
references.authors: Elizabeth Clark Asli Celikyilmaz Noah A. Smith
references.title: Sentence mover’s similarity: Automatic evaluation for multi-sentence texts
references.venue: In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics,
references.authors: Eldan Cohen Christopher Beck
references.title: Empirical analysis of beam search performance degradation in neural sequence models
references.venue: Proceedings of Machine Learning Research,
references.authors: Hal Daumé John Langford Daniel Marcu
references.title: Search-based structured prediction
references.venue: Machine learning,
references.authors: Kartik Goyal Graham Neubig Chris Dyer Taylor Berg-Kirkpatrick
references.title: A continuous relaxation of beam search for end-to-end training of neural sequence models
references.venue: In Thirty-Second AAAI Conference on Artificial Intelligence,
references.authors: Hirotaka Hachiya Takayuki Akiyama Masashi Sugiayma Jan Peters
references.title: Adaptive importance sampling for value function approximation in off-policy reinforcement learning
references.venue: Neural Networks,
references.authors: Tatsunori Hashimoto Hugh Zhang Percy Liang
references.title: Unifying human and statistical evaluation for natural language generation
references.venue: In Proceedings of the 2019 Conference of the North American Chapter of the Association
references.authors: W.K. Hastings
references.title: Monte carlo sampling methods using markov chains and their applications
references.venue: Biometrika, 57(1):97–109,
references.authors: Karl Moritz Hermann Tomas Kocisky Edward Grefenstette Lasse Espeholt Will Kay Mustafa Suleyman Phil Blunsom
references.title: Teaching machines to read and comprehend
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Sepp Hochreiter Jürgen Schmidhuber
references.title: Long short-term memory
references.venue: Neural Comput.,
references.authors: Ari Holtzman Jan Buys Li Du Maxwell Forbes Yejin Choi
references.title: The curious case of neural text degeneration
references.venue: In International Conference on Learning Representations,
references.authors: Ferenc Huszár
references.title: How (not) to train your generative model: Scheduled sampling, likelihood, adversary
references.venue: arXiv preprint arXiv:1511.05101,
references.authors: Natasha Jaques Asma Ghandeharioun Judy Hanwen Shen Craig Ferguson Agata Lapedriza Noah Jones Shixiang Gu Rosalind Picard
references.title: Way off-policy batch deep reinforcement learning of implicit human preferences in dialog
references.venue: arXiv preprint arXiv:1907.00456,
references.authors: Daniel Kang Tatsunori Hashimoto
references.title: Improved natural language generation via loss truncation
references.venue: In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 718–731,
references.authors: Chris Kedzie Kathleen McKeown
references.title: A good sample is hard to find: Noise injection sampling and self-training for neural language generation models
references.venue: In Proceedings of the 12th International Conference on Natural Language Generation,
references.authors: Yaser Keneshloo Tian Shi Naren Ramakrishnan Chandan K Reddy
references.title: Deep reinforcement learning for sequence-to-sequence models
references.venue: IEEE Transactions on Neural Networks and Learning Systems,
references.authors: Rémi Leblond Jean-Baptiste Alayrac Anton Osokin Simon Lacoste-Julien
references.title: SEARNN: Training RNNs with global-local losses
references.venue: In International Conference on Learning Representations,
references.authors: Sergey Levine Aviral Kumar George Tucker Justin Fu
references.title: Offline reinforcement learning: Tutorial, review, and perspectives on open problems
references.venue: arXiv preprint arXiv:2005.01643,
references.authors: Mike Lewis Yinhan Liu Naman Goyal Marjan Ghazvininejad Abdelrahman Mohamed Omer Levy Veselin Stoyanov Luke Zettlemoyer
references.title: BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension
references.venue: In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics,
references.authors: Jiwei Li Will Monroe Tianlin Shi Sébastien Jean Alan Ritter Dan Jurafsky
references.title: Adversarial learning for neural dialogue generation
references.venue: In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing,
references.authors: Zichao Li Xin Jiang Lifeng Shang Hang Li
references.title: Paraphrase generation with deep reinforcement learning
references.venue: In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing,
references.authors: Chin-Yew Lin
references.title: ROUGE: A package for automatic evaluation of summaries
references.venue: In Text Summarization Branches Out,
references.authors: Sidi Lu Lantao Yu Siyuan Feng Yaoming Zhu Weinan Zhang
references.title: CoT: Cooperative training for generative modeling of discrete data
references.venue: Proceedings of the 36th International Conference on Machine Learning,
references.authors: Kenton Murray David Chiang
references.title: Correcting length bias in neural machine translation
references.venue: In Proceedings of the Third Conference on Machine Translation: Research Papers,
references.authors: Shashi Narayan Shay B. Cohen Mirella Lapata
references.title: Don’t give me the details, just the summary! topic-aware convolutional neural networks for extreme summarization
references.venue: In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing,
references.authors: Mohammad Norouzi Samy Bengio zhifeng Chen Navdeep Jaitly Mike Schuster Yonghui Wu Dale Schuurmans
references.title: Reward augmented maximum likelihood for neural structured prediction
references.venue: Advances in Neural Information Processing Systems,
references.authors: Jekaterina Novikova Ondřej Dušek Amanda Cercas Curry Verena Rieser
references.title: Why we need new evaluation metrics for NLG
references.venue: In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing,
references.authors: Kishore Papineni Salim Roukos Todd Ward Wei-Jing Zhu
references.title: Bleu: a method for automatic evaluation of machine translation
references.venue: In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics,
references.authors: Tetiana Parshakova Jean-Marc Andreoli Marc Dymetman
references.title: Distributional reinforcement learning for energy-based sequential models
references.venue: arXiv preprint arXiv:1912.08517,
references.authors: Ramakanth Pasunuru Mohit Bansal
references.title: Multi-reward reinforced summarization with saliency and entailment
references.authors: Doina Precup Richard S. Sutton Satinder Singh
references.title: Eligibility traces for off-policy policy evaluation
references.authors: Weizhen Qi Yu Yan Yeyun Gong Dayiheng Liu Nan Duan Jiusheng Chen Ruofei Zhang Ming Zhou
references.title: ProphetNet: Predicting future n-gram for sequence-to-SequencePre-training
references.venue: In Findings of the Association for Computational Linguistics: EMNLP
references.authors: Colin Raffel Noam Shazeer Adam Roberts Katherine Lee Sharan Narang Michael Matena Yanqi Zhou Wei Li Peter J Liu
references.title: Exploring the limits of transfer learning with a unified text-to-text transformer
references.venue: Journal of Machine Learning Research,
references.authors: Pranav Rajpurkar Jian Zhang Konstantin Lopyrev Percy Liang
references.title: SQuAD: 100,000+ questions for machine comprehension of text
references.venue: In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing,
references.authors: Marc’Aurelio Ranzato Sumit Chopra Michael Auli Wojciech Zaremba
references.title: Sequence level training with recurrent neural networks
references.venue: In International Conference on Learning Representations,
references.authors: Stéphane Ross Geoffrey Gordon Drew Bagnell
references.title: A reduction of imitation learning and structured prediction to no-regret online learning
references.venue: In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics,
references.authors: Thomas Scialom Sylvain Lamprier Benjamin Piwowarski Jacopo Staiano
references.title: Answers unite! unsupervised metrics for reinforced summarization models
references.venue: In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP),
references.authors: Abigail See Peter J. Liu Christopher D. Manning
references.title: Get to the point: Summarization with pointer-generator networks. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)
references.authors: Iulian V Serban Chinnadhurai Sankar Mathieu Germain Saizheng Zhang Zhouhan Lin Sandeep Subramanian Taesup Kim Michael Pieper Sarath Chandar Nan Rosemary Ke
references.title: A deep reinforcement learning chatbot
references.venue: arXiv preprint arXiv:1709.02349,
references.authors: Shiqi Shen Yong Cheng Zhongjun He Wei He Hua Wu Maosong Sun Yang Liu
references.title: Minimum risk training for neural machine translation. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)
references.authors: Loic Simon Ryan Webster Julien Rabin
references.title: Revisiting precision recall definition for generative modeling
references.venue: In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning,
references.authors: Felix Stahlberg Bill Byrne
references.title: On NMT search errors and model errors: Cat got your tongue
references.venue: In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP),
references.authors: Richard S Sutton David A McAllester Satinder P Singh Yishay Mansour
references.title: Policy gradient methods for reinforcement learning with function approximation
references.venue: In Advances in neural information processing systems,
references.authors: Guy Tevet Gavriel Habib Vered Shwartz Jonathan Berant
references.title: Evaluating text GANs as language models
references.venue: In Proceedings of the
references.authors: Ran Tian Shashi Narayan Thibault Sellam Ankur P. Parikh
references.title: Sticking to the facts: Confident decoding for faithful data-to-text generation, 2020
references.venue: URL https://openreview.net/forum? id=HkxU2pNYPH
references.authors: Lifu Tu Richard Yuanzhe Pang Kevin Gimpel
references.title: Improving joint training of inference networks and structured prediction energy networks
references.venue: In Proceedings of the Fourth Workshop on Structured Prediction for NLP, pp. 62–73,
references.authors: Ashish Vaswani Noam Shazeer Niki Parmar Jakob Uszkoreit Llion Jones Aidan N Gomez Łukasz Kaiser Illia Polosukhin
references.title: Attention is all you need
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Chaojun Wang Rico Sennrich
references.title: On exposure bias, hallucination and domain shift in neural machine translation
references.venue: In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics,
references.authors: Sean Welleck Ilia Kulikov Jaedeok Kim Richard Yuanzhe Pang Kyunghyun Cho
references.title: Consistency of a recurrent language model with respect to incomplete decoding
references.venue: In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP),
references.authors: Sean Welleck Ilia Kulikov Stephen Roller Emily Dinan Kyunghyun Cho Jason Weston
references.title: Neural text generation with unlikelihood training
references.venue: In International Conference on Learning Representations,
references.authors: Ronald J Williams
references.title: Simple statistical gradient-following algorithms for connectionist reinforcement learning
references.venue: Machine learning,
references.authors: Sam Wiseman Alexander M. Rush
references.title: Sequence-to-sequence learning as beam-search optimization
references.venue: In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing,
references.authors: Lijun Wu Fei Tian Tao Qin Jianhuang Lai Tie-Yan Liu
references.title: A study of reinforcement learning for neural machine translation
references.venue: In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing,
references.authors: Lantao Yu Weinan Zhang Jun Wang Yong Yu
references.title: Seqgan: Sequence generative adversarial nets with policy gradient
references.venue: In Thirty-First AAAI Conference on Artificial Intelligence,
references.authors: Jingqing Zhang Yao Zhao Mohammad Saleh Peter J. Liu
references.title: Pegasus: Pre-training with extracted gap-sentences for abstractive summarization
references.venue: In Proceedings of the 37th International Conference on Machine Learning, Proceedings of Machine Learning Research. PMLR,
references.authors: Qingyu Zhou Nan Yang Furu Wei Chuanqi Tan Hangbo Bao Ming Zhou
references.title: Neural question generation from text: A preliminary study
references.venue: In National CCF Conference on Natural Language Processing and Chinese Computing,
references.authors: Daniel M Ziegler Nisan Stiennon Jeffrey Wu Tom B Brown Alec Radford Dario Amodei Paul Christiano Geoffrey Irving
references.title: Fine-tuning language models from human
sections.heading: 1 INTRODUCTION
sections.text: A dominant approach to text generation is to use autoregressive models learned by maximum likelihood estimation (MLE) on supervised data. However, this approach introduces two well-known discrepancies between training and evaluation objectives that lead to undesired generations. First, the training loss is negative log-likelihood, whereas the evaluation is based on human judgment of the output quality. Under model misspecification, MLE tends to over-generalize, assigning large probability mass to both high-quality and low-quality sequences (Huszár, 2015; Simon et al., 2019). Therefore, in practice, we must carefully select the decoding algorithms to produce high-quality outputs.
  Second, during training, the autoregressive model conditions on the gold history/prefix; however, at inference time it conditions on model-generated history. This is known as the exposure bias problem (Ranzato et al., 2016; Bengio et al., 2015). In the worst case, one incorrect prediction can produce a low-probability prefix under the gold data distribution, and errors compound in each of the following steps (Ross et al., 2011). In practice, prior work has observed problems such as repetition and hallucination partly due to exposure bias (Holtzman et al., 2020; Wang & Sennrich, 2020).
  We aim to bridge the gap between training and evaluation in this paper. To match training and evaluation objectives, ideally we should maximize output quality given model-generated histories. This corresponds to the reinforcement learning (RL) objective: maximizing the expected reward (quality) over trajectories (sequences) induced by the policy (model). However, optimizing this objective is notoriously difficult. Prior RL approaches mainly focus on fine-tuning a learned model to optimize sequence-level metrics such as BLEU (Papineni et al., 2002), but empirically it remains unclear if RL is beneficial to text generation (Wu et al., 2018; Choshen et al., 2020). Note that many challenges in RL arise from exploring an exponentially large space of sequences, with sparse rewards only on those close to the reference. We thus propose to learn from only the reference sequences without interaction (i.e., the offline setting). Specifically, we use off-policy policy gradient
  with importance weighting (Hastings, 1970; Hachiya et al., 2009; Parshakova et al., 2019), where training examples with higher probability under the model are weighted higher. Further, our reward functions approximate human judgment of the output quality by estimating how likely a human would have generated a sequence. We call our algorithm GOLD (Generation by Off-policy Learning from Demonstrations).
  Results on news summarization, question generation, and machine translation show that GOLD leads to better model performance than MLE and RL fine-tuning by both task metrics and human-rated quality. Further, our analysis shows that GOLD learns high-precision models that are less sensitive to decoding algorithms. In addition, it alleviates exposure bias: the output quality does not degrade much as generation length increases.
sections.heading: 2 FROM MLE TO RL FRAMEWORK
sections.text: MLE training. Given a context x such as a document, we want to generate a sequence of tokens y = (y0, . . . , yT ), where yi comes from a vocabulary V . The generator is modeled by a conditional probability distribution parametrized by θ: pθ(y | x) = ∏T t=0 pθ(yt | y0:t−1,x), where y0:t−1 denotes the prefix y0, . . . , yt−1. Let phuman(y | x) denote the data-generating distribution. Using MLE, the loss function is
  L(θ) = −Ey∼phuman [ T∑ t=0 log pθ(yt | y0:t−1,x) ] . (1)
  At inference time, we generate tokens sequentially according to pθ.
  Evaluation. In practice, the quality of an output often relies on task-specific metrics such as fluency, correctness, and interestingness. Here for generality we consider perceptual quality (Huszár, 2015; Hashimoto et al., 2019) which measures how likely a human would have generated the output given the context, i.e., phuman(y | x). Thus the evaluation metric is
  Ey∼pθ [ T∑ t=0 log phuman(yt | y0:t−1,x) ] . (2)
  Comparing (1) and (2), we see that the training objective encourages high recall: the model must put probability mass on all human-generated sequences. In contrast, the evaluation metric encourages high precision: all outputs from the model must be of high quality. Unfortunately, directly optimizing the evaluation metric is impossible because phuman is unknown and the expectation is difficult to estimate. We therefore develop a training objective that closely approximates (2) in the RL framework.
  RL formulation. Let’s consider generation as a sequential decision-making process. At each time step t, the policy πθ takes an action at ∈ V , transits to the next state st+1 = (y0:t,x), and receives a reward rt. The policy corresponds to the generation model: πθ(at | st) = pθ(at | y0:t−1,x). We can thus represent a sequence as a trajectory τ = (s0, a0, r0, . . . , sT , aT , rT ). The set of trajectories derived from the training data is called demonstrations which show the desired behavior of a policy. The RL objective is to maximize J(θ) = Eτ∼πθ [∑T t=0 γ trt ] , where γ ∈ (0, 1] is the discount factor, and πθ(τ) denotes the distribution of τ induced by πθ. If we knew oracle rewards rt = phuman(at | st), then this objective would be exactly the evaluation metric we want to optimize. Next, we describe how to optimize J(θ) with reward functions that approximate phuman.
sections.heading: 3 APPROACH
sections.heading: 3.1 OFF-POLICY POLICY GRADIENT
sections.text: Policy gradient. A straightforward way to optimize J(θ) is policy gradient (PG) (Williams, 1992; Sutton et al., 2000). The gradient is given by
  ∇θJ(θ) = Eτ∼πθ [∑ t ∇θ log πθ(at | st)Q̂(st, at) ] , (3)
  where Q̂(st, at) = ∑T t′=t γ
  t′−trt′ is the estimated return from state st. The expectation is estimated by Monte Carlo samples from πθ. In text generation, the return Q̂(st, at) is often a sequence-level reward such as BLEU. In practice, the policy is likely to get stuck in a region of zero reward during training, generating gibberish without receiving any learning signal (Li et al., 2018; Keneshloo et al., 2019). A common remedy is to initialize the policy with the MLE solution and/or interleave with MLE gradient update during PG. However, this would bias the parameters towards the MLE solution, thus often leads to marginal gains in practice (Wu et al., 2018; Choshen et al., 2020).
  Offline learning. To avoid zero-reward regions, we would like to reduce interaction with the environment and stay close to the demonstrated trajectories. In the extreme case, the policy is learned solely from the static demonstrations without additional interaction with the environment, which is referred to as the offline setting. While it is in general a more challenging problem, we argue that the offline setting is appropriate for text generation (Serban et al., 2017; Jaques et al., 2019). First, the environment dynamics is known: once a token is generated, we deterministically transition to the next state with the additional token appended to the prefix; no interaction is needed to learn the environment. Second, while exploration may lead to high-quality sequences different from the reference, we lack a good reward function to identify them (Novikova et al., 2017; Aharoni & Goldberg, 2018; Clark et al., 2019). Therefore, the benefit of exploration in text generation is limited.
  In the offline setting, we cannot estimate the expected return of πθ by sampling trajectories from it, and must use trajectories from a different behavioral policy πb, known as off-policy learning in RL. A common technique to estimate expectations under one distribution πθ given samples from a different distribution πb is importance sampling, which leads to the following unbiased estimator of the gradient (Precup et al., 2000):
  Eτ∼πb [∑ t wt∇θ log πθ(at | st)Q̂(st, at) ] ,
  with importance weights wt = ∏t t′=0 πθ(at′ |st′ ) πb(at′ |st′ ) .
  Approximations. Computing the importance weights above requires multiplying per-action importance weight over multiple time steps. In practice, we have found that it is sensitive to optimization hyperparameters and takes longer to converge. Therefore, we use the per-action approximation: wt ≈ πθ(at|st)πb(at|st) . This corresponds to optimizing the expected return under the off-policy state distribution induced by πb and the on-policy action distribution of πθ. Although this estimator is biased, empirically it has been shown to reduce variance and work reasonably well if πb and πθ are close (Serban et al., 2017; Levine et al., 2020). Another obstacle is that we do not know πb which produced the demonstrationsD = {(x(i),y(i))}Ni=1. One option is to estimate πb onD. Here we take a simpler approach that uses the empirical distribution: πb(τ) ≈ 1/N for τ ∈ D and 0 otherwise. As a result, the denominator in wt is a constant and can be ignored in optimization. Our final approximated gradient has the form:
  ∇θJ(θ) ≈ N∑ i=1 T∑ t=0 πθ(a i t | sit)∇θ log πθ(ait | sit)Q̂(sit, ait), (4)
  where the superscript i represents the ith trajectory. Compared with the MLE gradient:∑N i=1 ∑T t=0∇θ log πθ(ait | sit), our gradient (4) upweights actions with high return and actions preferred by the current policy πθ. Intuitively, it encourages the learning algorithm to focus on “easy” examples (high likelihood under the model) which improves precision.
sections.heading: 3.2 REWARD
sections.text: Let R be the reward function such that rt = R(st, at). To optimize the perceptual quality of a sequence (see (2)), we want R(s, a) to approximate phuman(a | s), i.e., how likely humans would have generated a given s. In general, it is hard to develop a reliable reward function for text generation tasks because it must work well for a large set of possible generations. In the offline setting, however, we can restrict the domain of R to state-action pairs on the demonstrations. Next, we propose three reward functions.
  δ-reward. An obvious choice is a sequence-level reward, which considers all demonstrations to be equally good and assigns zero reward to any other outputs. Formally,
  Rδ(st, at) def = { 1, if t = T and (s0:T , a0:T ) ∈ D 0, otherwise
  (5)
  where a reward of one is received in the terminal state for any trajectory in the demonstrations.
  Estimated phuman. In text generation tasks, an input often has many correct outputs and the reference may be an uncommon output that contains rare words or has complex syntax. To account for different likelihood of the references, we estimate the probability of each reference by minimizing KL (phuman‖q), where q(a | s) approximates phuman(a | s). This is equivalent to finding the MLE solution (denoted by pMLE).1 Importantly, pMLE is a reasonable approximation to phuman when restricted to the demonstrations. It is not a good reward function in general, however; it can assign large probability mass to low-quality outputs. Given the estimated perceptual quality pMLE(a | s), we define two reward functions. Our first reward function corresponds to a product of probabilities when summed over the trajectory:
  Rp(s, a) def = log pMLE(a | s). (6) Assuming γ = 1, the return at time step t is Q̂t(st, at) = ∑T t′=t log pMLE(at | st). Thus a sequence has high reward only if every word has high likelihood under pMLE. To allow for partial credits even if bad actions are taken at certain steps, we define another reward function corresponding to the sum of probabilities:
  Rs(s, a) def = pMLE(a | s). (7) The return Q̂(st, at) = ∑T t′=t pMLE(at | st), thus the policy can recover from bad decisions if the subsequent actions receive high reward.
  3.3 THE GOLD ALGORITHM
  Algorithm 1: GOLD 1 πθ ← pMLE, π̃θ ← pMLE 2 for step = 1, 2, . . . ,M do 3 Sample a minibatch B = {(xi,yi)}|B|i=1 4 foreach (sit, ait) do 5 Compute importance weights
  max(u, π̃θ), and compute returns Q̂(sit, a i t)− b
  6 Update θ by (4) using gradient descent 7 if step % k = 0 then π̃θ ← πθ 8 Return: πθ
  Our full algorithm based on off-policy PG is shown in Algorithm 1. For importance weights πθ(a | s), to avoid drastic changes, we initialize πθ with the MLE solution. In addition, we compute the importance weights by a weighting policy π̃θ that synchronizes with πθ periodically so that the weights do not change frequently between updates. We also lower-bound the importance weight by a small number u.
  Another source of variance comes from policy gradients. Since our return is computed from a sum or product of probabilities ((6) and (7)), we truncate the future trajectory after five steps. We follow the common practice to subtract a baseline b from the return to reduce variance; moreover, to avoid negative reward on the demonstrations (after subtracting baseline), we lower-bound pMLE in (6) and (7) by a small number c. In practice, GOLD is easy to implement; further, given an existing pMLE, the GOLD-training stage usually takes less time than MLE. The code is available.2.
sections.heading: 4 EXPERIMENTS
sections.heading: 4.1 SETUP
sections.text: We chose four text generation tasks: (1) question generation (NQG; Zhou et al., 2017): given a passage and a short span of the passage, the goal is to generate a question that can be answered by the
  1Note that KL (phuman‖q) = Ephuman log phuman − Ephuman log q, thus minimizing the KL divergence with respect to q is equivalent to the MLE objective.
  2Code: https://github.com/yzpang/gold-off-policy-text-gen-iclr21
  span; (2) summarization (CNN/DM; Hermann et al., 2015); (3) extreme summarization (XSum; Narayan et al., 2018): the references are more abstractive than CNN/DM summaries; (4) machine translation (IWSLT14 De-En; Cettolo et al., 2014). See Appendix A.1 for the size and the source of the datasets. We evaluate NQG and summarization by both automatic metrics, i.e., corpus-level BLEU-4 (Papineni et al., 2002) and ROUGE-1/2/L (Lin, 2004) respectively, as well as human ratings.
  We experiment with three variants of GOLD: GOLD-δ, GOLD-p, GOLD-s, which uses the δ-reward and the two estimated rewards (Rp and Rs), respectively. Our baseline learning algorithm is standard MLE, and we compare with on-policy RL training using policy gradient in Section 4.3. We describe models for each task at the beginning of Section 4.2.
  For GOLD training, we use the baseline b = −60 for GOLD-p and b = 0 for GOLD-s. To lower bound the return such that it is non-negative on demonstrated trajectories, we tune the lower bound c of pMLE in {0, 0.01, 0.05, 0.1} in (6) and (7). Furthermore, to reduce variance for importance weights, we lower bound them by u ∈ {0, 0.1, 0.15, 0.2}. All hyperparameters are tuned on the dev set. See Appendix A.3 for more reproduciblility details.
sections.heading: 4.2 RESULTS AND ANALYSIS
sections.text: GOLD improves both standard and transformer models. Recall that one of our main motivations is that MLE tends to over-generalize under model misspecification, i.e., high recall but low precision. One may wonder whether this problem can be fixed by better modeling. Therefore, we evaluated GOLD with both standard high-performing models and state-of-the-art pretrained model. For standard models, we chose two representative seq2seq-based models, NQG++ (Zhou et al., 2017) and the pointer-generator model (See et al., 2017) for NQG and CNN/DM respectively.3 Table 1 shows that GOLD is better than MLE in terms of BLEU and ROUGE. In particular, we find that using estimated rewards is superior to the δ-reward, showing the benefits of accounting for varying quality of the references. We thus consider only GOLD-p and GOLD-s in the rest of the experiments. For transformer models (Vaswani et al., 2017), we used the pretrained BART (Lewis et al., 2020) for NQG, CNN/DM, and XSum; we used standard transformer for IWSLT14 De-En. Table 3 shows that GOLD achieves better scores than MLE across all tasks, including near-SOTA on CNN/DM (R-2 95% confidence interval: 21.84-22.33) and good performance on XSum (R-2 95% CI: 22.25-22.92).
  We further crowdsourced human evaluation by pairwise comparison4 between MLE-trained and GOLD-s-trained model outputs. Each pair of comparison is repeated three times (by three different workers) and we take the majority answer. For each dataset, the evaluations are done by at least 15 different workers. For NQG, we showed workers the entire input and the questions generated by two models, and we ask workers to select the better one (with a third “tie” option). For summarization,
  3We didn’t use standard seq2seq-based models for IWSLT14 and XSum as they are not competitive. 4We used Amazon Mechanical Turk on 200 pairs of examples for each of the three tasks. We added qualification tasks with obvious answers and we didn’t use any results by workers who failed the qualifications.
  (a) NQG; x-axis is cropped
  (b) NQG; y-axis is cropped
  (c) CNN/DM; xaxis is cropped
  (d) CNN/DM; y-axis is cropped
  Figure 1: Histograms of token-level NLL loss using standard models on NQG and CNN/DM dev sets. MLE learns high-recall models whose loss distribution is spread out; GOLD learns high-precision models whose loss distribution is concentrated on near-zero losses.
  we ask workers to select the generation closer in meaning to the reference without showing the article. More details are in Appendix C. Table 5 shows that workers prefer outputs from models trained by GOLD more often than those trained by MLE.
  GOLD encourages high-precision models. One interesting observation from Table 1 and Table 3 is that compared to MLE, GOLD leads to much higher held-out perplexities, while achieving better metric scores. Since both are evaluated against the reference, one would expect high perplexity to correlate with low metric scores. To better understand the behavior of GOLD, we examine the distributions of token-level negative log-likelihood (NLL) loss (a monotonic transformation of perplexity) in Figure 1. We see that the loss distribution of GOLD (compared to MLE) concentrates on near-zero losses (Figures 1a and 1c) with a long tail of large losses (Figures 1b and 1d), hence high perplexity. In contrast, MLE has much fewer near-zero losses and fewer large losses, suggesting it tries to generate all tokens; i.e., MLE encourages recall, as discussed in Section 2. We conclude
  5 10 15 20 sequence length
  1.0
  1.5
  2.0
  2.5
  3.0
  hu m
  an ra
  tin g
  MLE GOLD-s
  5 10 15 20 time-step
  2
  4
  6
  to ke
  nle
  ve l a
  vg N
  LL lo
  ss
  MLE GOLD-s
  Figure 2: Left: Avg human ratings vs. generation length, on 736 NQG samples. (Colored regions: 95% confidence interval.) Each data point has≥30 annotations. The quality of long generations from MLE-trained model drops heavily, but stays stable across lengths for GOLD-s generations. Right: Avg NLL loss of tth token given the gold prefix tokens vs. time-step t, on NQG dev set. Without exposure bias, NLL loss stays stable across lengths.
  that GOLD achieves better metric scores by focusing on easy-to-learn tokens at the expense of lower recall with respect to the reference.
  Another advantage of high-precision models is that they do not rely much on decoding algorithms to sample high-quality outputs from the learned distribution. From a RL perspective, the policy already considers future rewards when making local decisions, thus beam search is not necessary. As a result, we see in Table 2 that GOLD achieves similar performance with both argmax decoding and top-k sampling. In contrast, MLE suffers significantly from sampling, which suggests that it learns a high-recall but low-precision model.
  GOLD alleviates exposure bias. GOLD suffers less from exposure bias because it trains on the state/history distribution induced by the model instead of the reference data. Here, we empirically quantify the exposure bias problem in learned models. If there is exposure bias, then the output quality is expected to degrade as output length increases, as the history is more likely to deviate from the reference distribution with accumulated generation steps. To evaluate quality, we sampled 736 generations of different lengths from standard models trained by both MLE and GOLD on NQG. Given the paragraph, words to query on, and the generated questions, we then asked workers to rate the generations from 1 (worst) to 4 (best). Figure 2 (left) shows that the output quality of the MLE-trained model degrades when the sequence length is over 14 words, whereas the quality of the GOLD-s-trained model stays relatively stable across all lengths.5 Qualitatively, we observe frequent degenerations (Holtzman et al., 2020; Welleck et al., 2020a) including repetitions and hallucinations within a sentence generated by MLE-trained model, as shown in Table 6. In contrast, Figure 2 (right) shows the NLL loss conditioned on gold histories on NQG dev set.6 We can see that without exposure bias, NLL loss does not vary much as the length increases. Therefore, we conclude that the big performance drop for long generations using MLE is mainly due to exposure bias and GOLD does not suffer from the problem.
sections.heading: 4.3 COMPARISON WITH ON-POLICY TRAINING
sections.text: While offline RL is generally more challenging due to lack of interaction with the environment, we argue that the benefit from interaction is limited in text generation (Section 3.1) and overweighed by the optimization challenges. In this section, we investigate the effect of on-policy training using task metrics as rewards. Specifically, we pre-train the model using MLE and then fine-tune it using PG. To avoid degenerate solutions, we interleave MLE and PG updates evenly during fine-tuning. Similarly, we fine-tune GOLD-initialized models using PG. For on-policy fine-tuning, we use BLEU and ROUGE-2 as rewards for NQG and CNN/DM respectively.7 Table 4 shows that additional on-policy training improves both MLE and GOLD marginally. However, MLE with PG is still worse than GOLD. Further, one of the best-performing on-policy methods using a similarly competitive pretrained transformer model (Ziegler et al., 2019) also shows limited improvements over supervised baseline on CNN/DM, despite having better reward functions (domain-specific human preference annotations). Overall, the benefit from on-policy training is unclear in our experiments.8 Please refer to the appendix for more details.
sections.heading: 4.4 DISCUSSION ON GENERATION DIVERSITY
sections.text: The objective of GOLD is to produce high-precision text at the cost of recall: There are references that the model cannot generate with high probability, which is reflected by the high held-out perplexity in Table 1 and Table 3. One may wonder what the impact of GOLD on text “diversity” is. This issue warrants more discussion, but for text generation, “diversity” may stand for the following.
  (1) Diversity as in the ability to generate a number of different correct generations given one context. This is often discussed in the context of mode collapse, which is an important problem for image generation and unconditional text generation (e.g., continuation from a prompt). However, for many conditional NLG tasks, while there are multiple correct outputs, producing one good generation is often sufficient in practice, e.g., question generation, summarization, machine translation, image captioning, text style transfer, and even chit-chat dialogues (unless users expect the bots to say different things in the same context every time). One exception is creative writing tasks where we would like to have multiple novel generations given the same context, e.g., generating from a language model (Caccia et al., 2020). In these cases, GOLD may not be able to provide a variety of high-quality generations given one context, although it would still produce different outputs given different contexts. Another potential failure mode is that in open-ended dialogues, if one common response has large probability under true data distribution, then GOLD may lead to a distribution concentrated on this mode. In this case, additional inductive bias is needed to separate good modes from bad ones, e.g., additional reward on specificity of the response. On the other hand, while MLE-trained models have good recall and we can potentially sample many different outputs with a high temperature, or large k in top-k sampling, or large p in top-p sampling,9 there are only a few high-quality ones. Our conjecture is that there may not be enough data to cover all modes, and in fact high-likelihood outputs from MLE-trained models are often degenerate (Stahlberg & Byrne, 2019; Cohen & Beck, 2019; Holtzman et al., 2020).
  In sum, given the trade-off between diversity and quality, we argue that generating a single highquality output is a reasonable goal for most conditional text generation tasks, and we leave the question of generating both diverse and high-quality outputs to future work.
  (2) Diversity as in the linguistic complexity of the output, given the input. First, we compare GOLD and MLE by measuring the complexity of the output using the number of unique n-grams and did not find significant difference. For example, GOLD’s number of unique 1/2/3/4/5-grams for XSum (using BART) is 18846/18835/18103/17639/17258, MLE’s is 19071/19053/18349/17875/17531, and gold-standard target numbers are 23674/23661/22869/22280/21822. In addition, for question generation and summarization, we measure the complexity of the output by abstractivness, i.e., the proportion of n-gram overlaps between the input and the generation. For XSum (using BART),
  7While rewards in Section 3.2 are useful on demonstrations, they are not suitable for the on-policy setting as they cannot differentiate good vs. bad generations on the entire output space effectively; e.g., Murray & Chiang (2018); Stahlberg & Byrne (2019) showed that maximizing pMLE during decoding leads to empty generations.
  8On a related note, Choshen et al. (2020) also showed in machine translation that even properly tuned on-policy methods may not work well either.
  9Top-p sampling is another term for nucleus sampling by Holtzman et al. (2020).
  the proportion of 1/2/3/4/5-gram overlap for MLE is 0.75/0.27/0.10/0.053/0.031 and for GOLD: 0.73/0.24/0.087/0.039/0.021; the trend mostly holds for NQG and CNN/DM as well. In sum, we conclude that GOLD and MLE are comparable in producing complex or novel outputs.
  (3) Diversity as in the coverage of the true data distribution. This definition is related to (1). This diversity is the “recall” intuitively, and can be measured by NLL loss or perplexity, which will be sacrificed. In our case, the consequence is that the model tends to ignore difficult gold examples (Figure 1), which in text generation, may sometimes be noise or outliers. Empirically for a large number of text generation tasks, paying less attention to such examples did not cause mode collapse in our case.
sections.heading: 5 RELATED WORK
sections.text: Exposure bias. In structured prediction, there is a flurry of works addressing exposure bias since Bengio et al. (2015). Most works focus on learning global sequence scores instead of locally normalized scores using either variants of beam search (Wiseman & Rush, 2016; Andor et al., 2016; Goyal et al., 2018) or energy networks (Belanger & McCallum, 2016; Tu et al., 2020). These training algorithms are often complex and costly. Exposure bias is well studied in imitation learning (Daumé et al., 2009; Ross et al., 2011) and learning-to-search has been applied to RNNs to incorporate losses of sequences deviating from references (Leblond et al., 2018), but they require annotations or cost functions on non-reference sequences which may not be available for text generation.
  Objectives beyond MLE. Policy gradient-based algorithms and their variants have been used extensively in text generation to optimize sequence-level metrics (Ranzato et al., 2016; Shen et al., 2016; Norouzi et al., 2016; Pasunuru & Bansal, 2018). In addition, off-policy RL is commonly used in dialogue where online interaction with users is expensive (Serban et al., 2017; Jaques et al., 2019). The main difference is that we take advantage of the demonstrations and design generic reward functions for generation tasks. There is another line of work using policy gradient to optimize reward from a discriminator that differentiates good vs. bad generations (Yu et al., 2017; Li et al., 2017; Lu et al., 2019). However, these approaches often underperform MLE in practice (Tevet et al., 2019) due to optimization challenges. Recently, a concurrent work, Kang & Hashimoto (2020), proposed truncated log-loss which both optimizes distinguishability and enjoys efficient optimization.
  High-precision text generation. It is noticed early in neural text generation that MLE tends to produce high-recall models that over-generalize. Previously, high-quality outputs are selected mainly through decoding (e.g., beam search, low-temperature sampling, truncated sampling). Recently, there is an increasing amount of work on discouraging implausible samples during training, e.g., using negative sampling (Welleck et al., 2020b), self-training on high-quality samples (Kedzie & McKeown, 2019), and confidence-oriented decoding with calibration (Tian et al., 2020). In contrast, we tackle the fundamental problem of mismatched objectives and propose a general learning framework.
sections.heading: 6 CONCLUSION
sections.text: We provide an efficient algorithm that addresses the two train/test discrepancies in MLE training for text generation: likelihood as learning objective vs. quality as evaluation metric; gold history in training vs. model-generated history in inference. We have demonstrated that off-policy RL is a promising framework for text generation, with matched train/test objectives and optimization advantages like MLE. We believe more advanced off-policy learning techniques (e.g., proximity constraints) can be easily integrated into text generation and further improve performance.
sections.heading: ACKNOWLEDGEMENTS
sections.text: The authors thank Kyunghyun Cho, Tatsunori Hashimoto, Graham Neubig, Ethan Perez, Karl Stratos, Clara Vania, and Alex Warstadt (alphabetical order) for helpful discussions, and the anonymous reviewers for helpful feedback. This work was supported by Samsung Advanced Institute of Technology (Next Generation Deep Learning: From Pattern Recognition to AI) and Samsung Research (Improving Deep Learning Using Latent Structure).
sections.heading: A PRACTICAL SETUP AND IMPLEMENTATION
sections.heading: A.1 TASKS AND DATASETS
sections.text: (1) Natural question generation (NQG; Zhou et al., 2017) based on the SQuAD QA dataset (Rajpurkar et al., 2016): Given a text passage and a short span of the passage, the goal is to generate a question that can be answered by the span. (2) CNN/DailyMail summarization (CNN/DM): Given a piece of news, generate a few sentences of summary. We use the entity-non-anonymized version of CNN/DM dataset, following See et al. (2017). The target summaries tend to be extractive, meaning there tends to be heavy text-span overlaps between the source article and the target summary. (3) Extreme summarization (XSum; Narayan et al., 2018) is based on BBC news. The target summaries are highly abstractive. Past extractive strategies that work well for CNN/DM may not work well for XSum. (4) IWSLT14 German to English machine translation (IWSLT14 De-En; Cettolo et al., 2014) is a popular machine translation benchmark. Machine translation is different from the above three tasks, given that intuitively, the space of high-quality generation is smaller.
  More details on datasets. We first provide the number of examples in each dataset. The train/dev/test split for NQG is 86229/8913/8919; the split for CNN/DM is 287227/13368/11490; the split for XSum is 204045/11332/11334; the split for IWSLT14 De-En is 160239/7283/6750.
  To download and preprocess the NQG data, we follow the following instructions: https:// github.com/clovaai/FocusSeq2Seq; to download and preprocess the summarization data, we follow the following instructions: https://github.com/pytorch/fairseq/blob/ master/examples/bart/README.summarization.md; to download and preprocess the IWSLT14 De-En data, we follow the following instructions: https://github.com/pytorch/ fairseq/tree/master/examples/translation. More information can be found in our codebase.
sections.heading: A.2 MODEL ARCHITECTURES
sections.text: We use two sets of architectures for our experiments.
  Standard architectures. For NQG, we use the model NQG++ (Zhou et al., 2017), a seq2seqwith-attention model based on GRU (Cho et al., 2014), and for summarization we use pointer generator network (See et al., 2017), a seq2seq-with-attention model based on LSTM (Hochreiter & Schmidhuber, 1997). Specifically, we use 2 layers for both the encoder and the decoder, for both tasks. Other hyperparameters are based on the following implementation: https://github. com/clovaai/FocusSeq2Seq.
  Transformer architectures. For NQG, CNN/DM, and XSum, we also experiment with one of the top-performing models, BART (Lewis et al., 2020). Our experiments are based on the pretrained BART model provided by original authors10: it has 12 encoder layers and 12 decoder layers, and it is pretrained on around 3.3 billion words of Wikipedia articles and books. We use the model to investigate if our methods work with models with stronger capabilities. For IWSLT14 De-En, we use a moderate-size standard transformer architecture (encoder/decoder embedding dimension 512, 4 encoder attention heads, 6 encoder layers, 4 decoder attention heads, 6 decoder layers), a top-performing architecture in machine translation.
sections.heading: A.3 MORE ON REPRODUCIBILITY
sections.text: The codebase is released. The link to the code is posted on the following website: yzpang.me.
  Hyperparameters and training details on standard architectures. This paragraph corresponds to results in Table 1. We use a learning rate of 5e-4. For NQG, we use a batch size of 32; for CNN/DM we use a batch size of 16. We train using a single Nvidia GTX 1080 Ti (memory: 12 GB) GPU.
  10https://github.com/pytorch/fairseq/tree/master/examples; pretrained by corrupting the original document and optimized with respect to the reconstruction loss between the original document and the decoder output.
  As discussed in Section 3.3 and Section 4.1, we tune the lower bound of pMLE in {0, 0.01, 0.05, 0.1}. For NQG models, the lower bound of 0.1 produces best performance. For CNN/DM using GOLD-p, the lower bound is 0.01; for CNN/DM using GOLD-s, the lower bound is 0.
  Recall that as discussed in Section 3.3, the weighting policy π̃θ synchronizes with actual policy πθ once every k steps so as to stabilize training. We tune k ∈ {1500, 2691} (where 2691 steps corresponds to 1 epoch) for NQG and found that k = 1500 works better for all NQG models. We tune k ∈ {1500, 3000, 5000} for CNN/DM; we found that k = 1500 works best for GOLD-δ and GOLD-p, and k = 5000 works best for GOLD-s. Note that in practice, we do not observe big gaps when using other k’s in the set. For standard models, implementation is based on Cho et al. (2019). In all experiments, we evaluate once every epoch, and we do validation on the entire dev set, using task-specific metrics (BLEU/ROUGE-2), following Cho et al. (2019) and standard practice in machine translation.
  Hyperparameters and training details on transformer models. This paragraph corresponds to results in Table 3. For transformer models, we use Nvidia P40 GPUs (memory: 24 GB each). For NQG, CNN/DM, and XSum based on BART, we use 4 GPUs to train. For IWSLT14 De-En, we use 1 GPU. Note that fairseq defines batch size in terms of number of tokens instead of number of sequences. For NQG, we use 512 tokens as batch size (for each of the four GPUs); for CNN/DM and XSum, we use 1024 tokens as batch size (for each of the four GPUs); for IWSLT14 De-En, we use 4096 tokens as batch size.
  We use a learning rate of 2e-5 for NQG, CNN/DM, and XSum; 3e-4 for IWSLT14 De-En.
  Recall that as discussed in Section 3.3, the weighting policy π̃θ synchronizes with actual policy πθ once every k steps so as to stabilize training. Here, k = 1000 for NQG; k = 5000 for CNN/DM, XSum, IWSLT14 De-En. As discussed in Section 3.3 and Section 4.1, the lower bound of pMLE is set to be 0.01 for GOLD-p and 0.1 for GOLD-s. For all other parameters that are not specific to GOLD, we use the default fairseq summarization parameters (which can be found through footnote 10).
  For hyperparameter u as discussed in Section 4.1, for NQG and CNN/DM, u = 0.1; for XSum, u = 0.15; for IWSLT14 De-EN, u = 0.2.
  As indicated, the hyperparameters were only tuned in a small set of possible values. More careful tuning may result in slightly better performances.
  Number of parameters in each model. For standard models, we use NQG++ for NQG, and it has 10372565 parameters. We use pointer generator for CNN/DM, and it has 19965705 parameters. For transformer models, the BART model for NQG, CNN/DM, and XSum all have 406290432 parameters; the transformer model used for IWSLT14 De-En has 39469056 parameters.
  Average runtime. For standard models, based on the above models and the computing infrastructures, each epoch of NQG takes around 10 minutes to train and achieves best performance within 20 epochs. Each epoch of CNN/DM takes about 2 hours to train and achieves best performance within 15 epochs. For transformer models, each epoch of NQG takes around 5 minutes to train and achieves best dev performance within 5 epochs; each epoch of CNN/DM takes around 11 hours to train and achieves best dev performances within 5 epochs; each epoch of XSum takes around 8 hours to train; each epoch of IWSLT14 De-En takes around 3 minutes to train and achieves best performances within 100 epochs (as expected, given the large batch size11). Note that our transformer models are trained on P40s given hardware constraints; if the transformer models are trained on V100 GPUs, for example, the training time per epoch will likely be much shorter.
sections.heading: A.4 MORE DISCUSSION ON APPROXIMATIONS
sections.text: Recall that we truncated the future trajectory after five steps. In other words, the number of current+future steps is upper-bounded at six. Effectively, we are using a discount factor of 0.83.12
  11We use 4096 tokens (which corresponds to hundreds of sentences) as batch size for IWSLT14 De-En. 12Note that 1 + γ + . . .+ γT ≈ 1
  1−γ = 6 when γ = 5 6 .
  Given that theQ-value corresponds to future return, we attempted using different strategies. (1) Using the entire future trajectory, and (2) using a fixed number of future steps. We attempted (1) on NQG using the standard models (tuned discount factor in {1, 0.9, 0.8, 0.7, 0.5}) and found that {0.8, 0.7} usually performs best, resulting in similar performance but longer training time, compared to the current 5-future-step approach. We attempted (2) using the number of future steps in {1, 2, 3, 5, 7, 10} and found that using {5, 7, 10} leads to similar results, which are slightly better compared to {1, 2, 3}. One benefit is that given a fixed number of future steps, we found that using easy-to-tune constant baselines work well, and training time is also much shorter.
sections.heading: A.5 DETAILS ON ON-POLICY EXPERIMENTS
sections.text: For the MLE+PG baseline, we used the REINFORCE algorithm with sequence-level rewards (BLEU for NQG and ROUGE-2 for summarization). We attempted two versions of the baselines: (i) constant baselines searched in {0, 0.01, 0.05, 0.1, 0.15} for BLEU (NQG) and ROUGE-2 (CNN/DM), as well as (ii) baselines computed by the average BLEU/ROUGE-2 over the last 100 steps, minus {0, 0.05}. In terms of training warmup choices, We tried two versions of the training algorithm. (a) We initialized with MLE and trained with PG losses interpolated with MLE losses, given we found that the training process would become very unstable without interpolation. (b) We also attempted the following: we intialized the model at random and used MIXER (Ranzato et al., 2016). However, we failed to find improvements compared to (a), under our architecture. A relevant work Choshen et al. (2020) showed that properly tuned on-policy RL may not work for text generation in some cases.
  We also tried MIXER with the learned baseline for NQG, which is estimated by a simple linear regressor that takes RNN hidden states as inputs, according to Ranzato et al. (2016). After some tuning, we achieved only slight improvements in NQG (BLEU 14.71). One advantage of GOLD is that our algorithm does not rely on learning baselines which could have a big impact on performance of on-policy algorithms; in fact, all baselines are constants in this paper.
  Note that for GOLD+PG models, we only attempted constant baselines; better tuning of baselines could potentially lead to stronger performance.
sections.heading: B MORE ON RESULTS
sections.heading: B.1 LEAD-3 BASELINES FOR SUMMARIZATION
sections.text: The lead-3 baseline (using first 3 sentences as summaries) is a popular strong baseline in summarization literature. The ROUGE-1/2/L scores of the lead-3 baselines are as follows: 40.42/17.62/36.67 for CNN/DM; 16.30/1.60/11.95 for XSum. Our performance using transformer models beat these baselines by a large margin.
sections.heading: B.2 PERFORMANCE WITH TRANSFORMER ARCHITECTURES
sections.text: We experiment using transformer architectures, as shown in Table 3; we also experiment on two more tasks (compared to using standard architectures): XSum and IWSLT14 De-En. We achieve SOTA/near-SOTA result (according to automatic metrics which have inherent limitations) on CNN/DM: at the time of writing, our results (45.40/22.01/42.25 using GOLD-p or 44.82/22.09/41.81 using GOLD-s) are higher than 44.17/21.47/41.11 (PEGASUS; Zhang et al., 2020) and 44.20/21.17/41.30 (ProphetNet; Qi et al., 2020), both slightly higher than BART. Note the PEGASUS CNN/DM result is pretrained on 1.5B news articles (around 3.8 terabyte), whereas BART is pretrained on 3.3B words (around 0.16 tetrabyte). Our XSum results are also higher than PEGASUS (45.20/22.06/36.99) trained on Colossal Clean Crawled Corpus (C4; Raffel et al., 2020), but lower than the PEGASUS result using the publicly-unavailable 1.5B-article 3.8 terabyte HugeNews (Zhang et al., 2020) as pretrained corpus. We hypothesize that if our models are applied onto their architectures instead of pointer generator networks or BART, we would similarly get non-trivial improvements.
  We also achieve 0.81 point of BLEU improvement on IWSLT14 De-En; GOLD-s performs better than the existing approaches that do not use knowledge distillation or data augmentation, as far as the authors are aware.
sections.heading: B.3 MORE ON EXPOSURE BIAS
sections.text: With exposure bias. Recall that in Section 4.2, we used human evaluation (a score of 1 or 2 or 3 or 4) to approximate the output quality, and we found that the MLE-trained model degrades significantly when the generation length is long, whereas the quality of the GOLD-s-trained model stays relatively stable across lengths.
  Here, we use BLEU to approximate the quality of NQG generations, and we show that BLEU does not bias toward long sentences. Figure 3 shows the average sentence-level BLEU by sequence length.13
  Specifically, Figures 3a and 3c show the BLEU on randomly shuffled targets (from dev set), which show that longer sentences do not appear to punish BLEU scores. Figures 3b and 3d show the BLEU by sentence length, on model generations. We see that MLE’s BLEU decreases by length but GOLD-s’s BLEU appears to stay relatively stable. We thus see some evidence that MLE is generating worse sentences as sentence gets longer.
  If there is no exposure bias. In the main text, we used the NLL loss vs. length plot to demonstrate that without exposure bias, the loss does not vary much across length, so the MLE performance drop in Figure 2 (left) is mainly due to exposure bias. Here, we provide another way to analyze the case without exposure bias.
  Figure 4 shows the token prediction accuracy conditioned on gold histories on NQG dev set. Note that for each example, we let tx = Lx − 5, where Lx is the length of reference sentence x. We can see that without exposure bias, prediction accuracy does not vary much as the length increases. Therefore, we conclude that the big performance drop for long generations using MLE is mainly due to exposure bias and GOLD suffers less from the problem.
sections.heading: B.4 EXAMPLES
sections.text: Table 7 and Table 8 show the example generations based on the transformer models.
  13We use BLEU-2/3 given that without smoothing, sentence-level BLEU-4 results in large variance.
sections.heading: C HUMAN EVALUATIONS
sections.heading: C.1 PAIRWISE COMPARISON
sections.text: Our goal is to enable high-quality generations that do not necessarily result in gold references. Given that corpus-level BLEU/ROUGE score is only a popular approximation of generation quality, we first conduct human ratings to confirm the hypothesis that our approaches are generating better sequences. For NQG, for each unit of human evaluation, we present the source paragraph, the words to ask the question on, the question generated by MLE-trained model, as well as the question generated by GOLD-s-trained model. We ask the human evaluators the general question: which generated question is better? Figure 5 shows one example interface of pairwise comparisons.
  Using NQG dev set, on standard models, of the 183 pairs of comparison we conducted human evaluations on, 42 (23.0%) MLE-questions are better, 81 (44.3%) GOLD-s-questions are better, and 60 (32.8%) are tied. We also evaluate on models based on BART, shown in Table 5 in the main text.
  For summarization tasks, given that it is infeasible to get high-quality annotations if we let workers read the entire news article14, we only did the following: given the reference summary, a summary generated from MLE model, and a summary generated from our model, we asked workers to compare which generated summary is closer in meaning to the reference summary. Figure 6 shows one example interface of the mentioned pairwise comparison for summarization. See Table 5 for results.
sections.heading: C.2 NQG RATING
sections.text: NQG rating was conducted to examine if longer sentences (generated by MLE-trained model) will result in worse human ratings, and if GOLD alleviates the problem. In Figure 2 (left), to reduce variance, we group length by buckets of two (e.g., [7, 8], [9, 10], [11, 12], etc.). Furthermore, we
  14To obtain high-quality low-variance annotations, we may need to design QA tasks to make sure workers understood the news articles first, given the articles are usually very long.
  sampled 736 annotations such that each bucket would contain at least 30 sentences (for human evaluation) for each of MLE and GOLD-s. We also shown the 95% confidence interval using standard bootstrapping, in Figure 2 (left).
  Given the paragraph, words to query on, and the generations, we ask workers to rate the generations. Figure 7 shows an example interface of NQG human ratings. We ask workers to consider both the correctness of the generation (i.e., if the question is asking about the specified words using facts) and the quality of the generation (i.e., if the generation is fluent and coherent). We ask workers to rate from 1 to 4, where 1 means very bad, 2 means slightly below average, 3 means slightly above average, and 4 means very good.