In machine learning, training generative models often relies on the smooth flow of gradients. For continuous data like images, a Generative Adversarial Network (GAN) can easily propagate feedback from a discriminator back to a generator: if an image looks slightly unrealistic, the discriminator provides a gradient indicating exactly how to adjust each pixel's continuous value.
However, when we try to apply this adversarial framework to discrete sequences—such as text, music, or source code—we hit a mathematical wall. Selecting a word from a vocabulary is a discrete choice (a categorical sampling operation or an argmax). You cannot make the word "cat" 1% more like the word "dog" by slightly shifting a continuous parameter. Because this selection step is non-differentiable, standard backpropagation breaks down.
To bypass this bottleneck, researchers look to reinforcement learning (RL). By framing sequence generation as a sequential decision-making problem, policy gradient methods allow us to optimize generative models on discrete data using scalar rewards rather than direct gradient backpropagation.
Sequence Generation as a Markov Decision Process
To apply reinforcement learning to sequence generation, we must map the components of text generation to a Markov Decision Process (MDP):
- Agent: The generative model (e.g., a recurrent neural network or a Transformer).
- State ($s_t$): The tokens generated so far (the prefix $x_1, x_2, \dots, x_{t-1}$).
- Action ($a_t$): The next token $x_t$ selected from the vocabulary.
- Policy ($\pi_\theta$): The probability distribution over the vocabulary given the current state, parameterized by the model's weights $\theta$.
- Reward ($R$): A scalar evaluation of the completed sequence, provided by an external environment (such as a GAN discriminator, a black-box ranking model, or a human preference metric).
In this framework, the model no longer needs to receive a gradient through the token selection step. Instead, it acts as a stochastic policy that samples discrete tokens, observes a final reward, and adjusts its internal probabilities to favor actions that led to high rewards.
The Policy Gradient Mechanism
The mathematical foundation for this approach rests on the policy gradient theorem, typically implemented via the REINFORCE algorithm or more advanced variants like Proximal Policy Optimization (PPO).
Instead of differentiating the discrete tokens themselves, we differentiate the expected reward of the policy. The objective function $J(\theta)$ aims to maximize the expected reward of generated sequences:
$$J(\theta) = \mathbb{E}_{X \sim \pi_\theta}[R(X)]$$
Using the log-derivative trick, the gradient of this objective with respect to the model parameters $\theta$ can be estimated without requiring differentiability from the reward function or the token selection process:
$$\nabla_\theta J(\theta) \approx \sum_{t=1}^T \nabla_\theta \log \pi_\theta(x_t \mid s_t) \cdot R(X)$$
Intuitively, this equation acts as a scale: if a generated sequence $X$ receives a high positive reward, the gradient step increases the log-probability of every token choice made along that path. If the reward is low or negative, the probability of those choices is suppressed.
This mechanism enables a wide variety of non-differentiable optimization tasks. For example, Lantao Yu et al. pioneered this in SeqGAN: Sequence Generative Adversarial Nets with Policy Gradient, using a GAN discriminator to provide the scalar reward $R(X)$ to train a text generator. Similarly, Shuo Yang et al. utilized PPO in P-TA: Using Proximal Policy Optimization to Enhance Tabular Data Augmentation via Large Language Models to align synthetic tabular text generation with real-world data distributions.
[ State: x₁ x₂ ] ---> [ Generator / Policy (π_θ) ] ---> Samples Action: x₃
|
v
[ Complete Text: X ] ---> [ Evaluator / Discriminator ] ---> Reward: R(X)
|
+------------------ (Policy Gradient Update) -----------------+
Mitigating Variance and the Credit Assignment Problem
While policy gradients elegantly solve the non-differentiability problem, they introduce a severe practical challenge: high gradient variance.
If a model generates a 20-word sentence and receives a poor reward at the very end, the basic REINFORCE algorithm penalizes every single token equally. However, the sentence might have been grammatically perfect and contextually brilliant until a single catastrophic word choice at token 19. This is known as the credit assignment problem. Because rewards are typically sparse and delayed, the model struggles to identify which specific actions were responsible for the final outcome.
Researchers have developed two primary strategies to stabilize training and assign credit more accurately:
1. Monte Carlo Rollouts
To evaluate the quality of a partial sequence before it is fully finished, models can use Monte Carlo (MC) search. From an intermediate state $s_t$, the model completes the remaining sequence multiple times using its current policy.
Yu et al. used this technique to provide step-by-step feedback. By averaging the discriminator rewards of these simulated completions, the generator obtains an estimated action-value ($Q$-value) for a specific token choice at time step $t$, isolating its impact from subsequent tokens.
2. Baseline Subtraction and Self-Critical Training
Another way to reduce variance is to compare the reward of a sampled sequence against a baseline reward. If a sample performs better than expected, its token probabilities are boosted; if it performs worse, they are decreased.
In Adversarial Semantic Alignment for Improved Image Captions, Pierre Dognin et al. leveraged Self-Critical Sequence Training (SCST). Under SCST, the baseline is the reward obtained by the model's own greedy decoding output (the most likely token at each step). By comparing a stochastically sampled sequence against this greedy baseline, the model directly optimizes to outperform its own current average behavior, significantly lowering gradient variance and preventing training collapse.
Furthermore, Yau-Shian Wang et al. demonstrated in Learning to Encode Text as Human-Readable Summaries using Generative Adversarial Networks that providing word-step rewards using the previous word's score as a baseline pinpoints exactly which word choices contribute to or detract from overall coherence.
Expanding Beyond Adversarial Training
While initially popularized for text-based GANs, policy gradient sequence optimization has expanded into a versatile tool for steering language models using non-differentiable objectives, black-box systems, or human preferences.
Discrete Prompt Optimization
Instead of tuning the internal weights of a massive, frozen language model, policy gradients can be used to search the discrete token space for optimal prompts. Yihan Wang developed RLPrompt: Optimizing Discrete Text Prompts with Reinforcement Learning, which trains a compact policy network to generate discrete prompt tokens. The reward is derived directly from the target model's performance on a downstream task, bypassing the need to compute gradients through the target model itself.
Unsupervised Style Transfer and Rewriting
When parallel training corpora are unavailable, policy gradients allow models to optimize for abstract linguistic properties. For instance, Hongyu Gong et al. designed a generator-evaluator framework in Reinforcement Learning Based Text Style Transfer without Parallel Training Corpus that optimizes text generation against non-differentiable quality metrics like semantic similarity and perplexity. Similarly, Ting Liu demonstrated in Generating Reasonable and Diversified Story Ending Using Sequence to Sequence Model with Adversarial Training how scalar rewards from a discriminator push sequence models to generate story endings that favor global narrative diversity over local token-matching likelihoods.
Black-Box Adversarial Attacks
Policy gradients also enable adversarial manipulation of text systems. In Adversarial Attack and Defense of Structured Prediction Models, Wenjuan Han et al. trained a sequence-to-sequence model via RL to rewrite text in a way that tricks structured prediction models while preserving human readability. Because the victim model is a discrete, non-differentiable system, policy gradients serve as the primary bridge to discover successful textual perturbations.
Key Foundational Work
SeqGAN: Sequence Generative Adversarial Nets with Policy Gradient (2017) — contributed 3 concept elements to this direction.
SeqGAN: Sequence Generative Adversarial Nets with Policy Gradient (2016) — contributed 3 concept elements to this direction.
Generative Adversarial Network for Abstractive Text Summarization (2017) — contributed 1 concept elements to this direction.