Deep learning thrives on continuity. When every operation in a neural network is smooth and differentiable, optimization is straightforward: compute the gradient of a loss function with respect to the parameters via backpropagation, and take a step downhill.
However, many real-world problems require neural networks to make hard, discrete choices. A model might need to select a specific snippet of text as a rationale, pick a discrete negative sample from a massive product catalog, choose a precise keypoint on an image, or decide whether to skip a computationally expensive layer.
The moment a network makes a hard choice—such as using an $\text{argmax}$ operation or a binary threshold—the chain rule breaks. The derivative of a discrete selection with respect to the network's internal representations is zero almost everywhere, and undefined at the boundaries. Without gradients, standard backpropagation fails.
To bridge this gap, a powerful paradigm treats discrete selection mechanisms as stochastic policies and optimizes them using policy gradient methods from reinforcement learning. This approach allows networks to learn optimal discrete selection strategies using downstream task performance as a reward signal.
The Core Mechanism: From Hard Selection to Stochastic Policies
To understand why this works, consider a network that must select a single discrete item $a$ from a set of candidates $\mathcal{A}$ based on an input $x$.
Instead of making a deterministic choice directly, the network outputs a continuous vector of preferences, which is transformed via a softmax layer into a probability distribution $\pi_\theta(a|x)$, where $\theta$ represents the network's parameters. We then sample a discrete action $a$ from this distribution:
$$a \sim \pi_\theta(a|x)$$
Once the discrete selection $a$ is made, it is passed to the rest of the pipeline. The downstream system evaluates the quality of this choice and returns a scalar reward $R(a)$. Crucially, the downstream system does not need to be differentiable; it only needs to provide a score indicating how well the selection performed.
Because $a$ is sampled stochastically, we cannot optimize the reward for a single specific choice. Instead, we maximize the expected reward over the distribution of choices:
$$J(\theta) = \mathbb{E}_{a \sim \pi_\theta(a|x)} [R(a)]$$
To find the gradient of this expectation with respect to our model parameters $\theta$, we apply the log-derivative trick (also known as the REINFORCE algorithm):
$$\nabla_\theta J(\theta) = \mathbb{E}_{a \sim \pi_\theta(a|x)} [R(a) \nabla_\theta \log \pi_\theta(a|x)]$$
This equation reveals the core intuition of why the idea works: we do not need to differentiate the reward function $R(a)$ with respect to $a$. Instead, we only differentiate the log-probability of the action we chose, and scale that gradient by the scalar reward.
- If a chosen item leads to a high reward (e.g., better accuracy or lower compute), the gradient increases its probability of being chosen in the future.
- If the choice leads to a low reward, its probability is suppressed.
Paradigm 1: Hard Masking and Feature Selection
One major application of this technique is forcing networks to select a sparse subset of inputs or features, making the model's decisions more interpretable or efficient.
In Rationalizing Neural Predictions, Tao Lei et al. address the opacity of deep NLP models by forcing a generator to select short, coherent snippets of text ("rationales") that are sufficient to justify a prediction. Because the selection is a hard binary mask over words, the authors use policy gradients where the reward balances downstream prediction accuracy with a penalty for choosing too many words.
Input Text ───> [ Generator Policy π_θ ] ───> Discrete Binary Mask (Non-Differentiable)
│
▼
Downstream Predictor <─── Selected Rationale Snippets ┘
│
▼
Scalar Reward R(a) ───> Policy Gradient Update ───> Updates π_θ
This instance-specific selection logic is extended to tabular data by Jinsung Yoon et al. in INVASE: Instance-wise Variable Selection using Neural Networks. The authors employ an actor-critic framework to discover which specific features are necessary for each individual data point, bypassing the need for continuous, differentiable approximations of sparsity.
Paradigm 2: Intelligent Negative Sampling in Adversarial Games
In information retrieval, recommendation systems, and knowledge graph embeddings, models are often trained by contrasting a true item against a set of "negative" items. Selecting random negatives is easy but inefficient, as the model quickly learns to distinguish obvious mismatches. Finding "hard" negatives is better, but searching a discrete catalog for the most challenging items is non-differentiable.
To solve this, Jun Wang et al. introduce IRGAN: A Minimax Game for Unifying Generative and Discriminative Information Retrieval Models. They frame negative sampling as a minimax game between a generator and a discriminator:
- The generator acts as a policy, sampling discrete items from a document collection to fool the discriminator.
- The discriminator evaluates the selected items and provides a scalar confidence score.
- This score acts as a reward, updating the generator via policy gradients to sample increasingly difficult, high-quality negatives.
This framework has proven highly adaptable. Liwei Cai et al. apply a similar strategy in KBGAN: Adversarial Learning for Knowledge Graph Embeddings to sample negative triples, while Jingtao Ding et al. utilize policy gradients in Reinforced Negative Sampling for Recommendation with Exposure Data to intelligently select items that users were exposed to but chose to ignore.
Paradigm 3: Dynamic Resource Allocation and Conditional Execution
As deep learning models grow, running every layer for every input becomes computationally prohibitive. Policy gradients allow networks to make discrete, input-dependent decisions about their own execution paths.
In 2D or not 2D? Adaptive 3D Convolution Selection for Efficient Video Recognition, Hengduo Li et al. design a network that decides on the fly whether a video frame requires heavy 3D convolutions or cheaper 2D variants. Because choosing a network architecture path is a discrete operation, they use reinforcement learning to optimize the selection policy. The reward function explicitly penalizes computational cost alongside accuracy, forcing the model to learn an optimal efficiency-accuracy trade-off.
A similar logic is applied to generative models by Hui Zhang et al. in AdaDiff: Adaptive Step Selection for Fast Diffusion Models, where a policy gradient framework dynamically selects the number of discrete denoising steps based on the complexity of the input prompt, cutting inference time without sacrificing image quality.
Bridging Continuous and Discrete Worlds
Beyond masking, sampling, and skipping, policy gradients serve as a general-purpose bridge when continuous neural networks must interact with discrete geometric or structural operations.
For instance, in computer vision, Michal J. Tyszkiewicz et al. demonstrate in DISK: Learning local features with policy gradient that selecting discrete pixel keypoints for image matching can be trained end-to-end by treating pixel selection as a probabilistic policy. In clustering, Changhee Lee demonstrates in Temporal Phenotyping using Deep Predictive Clustering of Disease Progression that assigning patients to discrete clinical clusters can be optimized via an actor-critic framework to maximize future predictive accuracy.
By transforming a structural optimization problem (searching a combinatorial space of discrete choices) into a smooth parameter optimization problem (shifting probability distributions), policy gradients allow researchers to build hybrid architectures that combine the expressive power of deep learning with the precision of discrete decision-making.
Key Foundational Work
Unsupervised Generative Adversarial Cross-modal Hashing (2017) — contributed 1 concept elements to this direction.
IRGAN: A Minimax Game for Unifying Generative and Discriminative Information Retrieval Models (2017) — contributed 1 concept elements to this direction.
Rationalizing Neural Predictions (2016) — contributed 1 concept elements to this direction.