Learning to Rank Generation with Pairwise Partial Rewards (2023)

Abstract: This paper studies the use of reinforcement learning for conditional text generation, which overcomes the limitation of the prevalent supervised maximum likelihood estimation approach. However, it still suffers from challenges including the large action space and the delayed reward, as the reward can be computed only after an entire sequence is generated. To address these challenges, we propose a method that provides partial rewards for intermediate actions taken on partial sequences. This enables the model to promptly prioritize actions that lead to the generation of more desirable sequences. Our method’s key contribution lies in its focus on distinguishing relatively more desirable actions rather than striving to precisely estimate pointwise values for arbitrary partial sequences. Instead, our model learns to discern the relative desirability between pairs of actions, or rank actions in a pairwise manner, only when necessary and feasible. This is materialized in an efficient way by leveraging the prefix tree constructed from the sampled sequences. Experimental results on paraphrase generation and constrained machine translation tasks showcase the effectiveness of our method.

## introduction conditional text generation encompasses various tasks, with the objective of generating a sequence y based on a given source sequence x, in a way that maximizes the utility u. for example, in paraphrase generation, which we use as our running example, u is high when (1) y matches the meaning of the source sequence x, (2) y is fluent in terms of language modeling, and (3) it has high lexical dissimilarity from x @xcite figure 1 : reinforcement learning boils down to either implicitly or explicitly maintain pointwise estimates of values at each state, corresponding to utility of partially generated sequences. @xcite . supervised learning, particularly maximum likelihood estimation (mle) training, has typically been the standard approach for conditional text generation. in this approach, the model is trained to maximize the likelihood of the reference given the source. during inference, it generates output sequences for which it assigns high probability. this approach is known to suffer from two significant challenges: exposure bias and train-test objective discrepancy @xcite . to address both challenges, reinforcement learning (rl) has gained attention as an alternative @xcite . rl formulates autoregressive text generation as a markov decision process where a state corresponds to a generated prefix under construction, foot_0 an action represents the selection of the next token, guided by the policy network, which is essentially the language model. the agent's goal is to maximize the reward it receives, which is determined by the utility u of the output sequence. however, this utility can be computed only after the generation is finished. this sparse and delayed reward problem introduces challenges in learning the impact of each action taken by the model, known as the credit assignment problem in rl, as depicted in figure 1 @xcite et al. @xcite . when a pointwise estimation of each partial candidate is unreliable, generation leads to undesirable sequences such as blank or repeated n-grams @xcite . we hypothesize that such pointwise estimation of state values, or equivalently expecting models to predict a total order over all partially generated sequences, is an overly ambitious objective. in this sense, while text degeneration is often attributed to the failure of decoding, we show that the policy, the model itself, is more responsible to the failure. to support our claim that language models indeed struggle with the pointwise estimation of the final outcome from partially generated sequences, we suggest comparing their performance with beam search using different beam sizes, as illustrated in figure 2 . beam search can be seen as providing some tolerance for the model's mistakes by holding on to candidate sequences even when its prefix values are underestimated @xcite . ideally, if the model's belief about the sequence's utility aligns positively with the actual utility of the fully generated sequence, increasing the beam size should only increase such a tolerance. we refer to this property as beam monotonicity, which is violated in a baseline model shown in figure 2a . similarly, reducing the beam size should not significantly hurt the performance if the model accurately estimates values of prefixes in earlier stages, as higher-ranked candidates would still survive with a smaller beam size. we call this property beam resilience, which is violated in figure 2b . a reliable policy should satisfy both properties, as shown in figure 2c . ## background as a background, we formulate the description of how autoregressive conditional text generation is formulated as a markov decision process and the agent-environment interaction is defined to transform the task into an rl problem. as mentioned before, state s t at time step t corresponds to (x, @xmath0, and the possible action a t at this moment is the act of choosing the next token, y t+1 to reach the next state s t+1 . here the environment is fully observable and the state transition given the action is deterministic, that is, selecting an action (the next token) is equivalent to selecting the next state (prefix with length increased by 1). a conditional language model then can be regarded as directly parameterizing the policy, ## analysis we provide in-depth analysis of the behavior of our model and baselines. ## related work this section describes previous work addressing the misbehavior often observed from conditional text generation. null sequences, repeated n-grams and gibberish can be generated as the model assigns high probability to them under certain circumstances @xcite . we categorize efforts based on whether they attribute these to the decoding method (subsection 6.1) or to the model's policy (subsection 6.2). ## conclusion we proposed ppr (pairwise partial reward), a novel approach to reward shaping through providing partial rewards in reinforcement learning for conditional text generation. our method utilizes prefix tree constructed from the set of sample sequences to learn to rank between action pairs, supporting any sequence-level utility metrics u for optimization. by considering samples collectively, our approach enables the model to reflect on its past decisions and immediately determine which actions led to favorable outcomes. this allows ppr to effectively guide the model in estimating values and selecting desirable actions during generation. experimental results demonstrate that our model outperforms baselines, especially with smaller beam sizes or unbiased sampling, indicating a significant improvements in assessing the values of partial sequences and enhancing language models as stochastic policies.