Deep reinforcement learning owes much of its success to the mathematical smoothness of neural network parameter spaces. In a standard neural network, a tiny tweak to a weight causes a tiny, predictable change in the output. This continuity creates a smooth landscape where gradients point the way forward, allowing gradient descent to incrementally guide an agent toward optimal behavior.
However, many real-world decision-making problems inherently demand discrete, symbolic, or rule-based structures. For instance, safety-critical systems often require human-readable code or flowchart-like logic to allow formal verification and safety guarantees. In these domains, the smooth landscape vanishes. Instead, we are left with a jagged, non-differentiable terrain where standard gradient-based optimization completely breaks down.
The Anatomy of Non-Smooth Landscapes
Why exactly does optimization fail when we move away from continuous neural networks? The literature highlights three distinct structural barriers:
- The Discontinuity of Code: When representing policies as explicit computer programs or domain-specific languages, the search space becomes inherently non-smooth. As noted by Abhinav Verma et al. in Programmatically Interpretable Reinforcement Learning, a single character change in a program's source code can cause a massive, discontinuous jump in behavior or even cause the program to crash entirely. This extreme sensitivity prevents incremental improvement via local mutations, a challenge thoroughly documented across programmatic policy synthesis (Jeevana Priya Inala et al., Synthesizing Programmatic Policies that Inductively Generalize; Tales Henrique Carvalho et al., Reclaiming the Source of Programmatic Policies: Programmatic versus Latent Spaces).
- Value Function Flatness: In configurable environments or bilevel optimization problems, the goal is to optimize environmental parameters alongside the agent's policy. Rui Silva et al. in A Theoretical and Algorithmic Analysis of Configurable MDPs demonstrate that these landscapes feature vast "flat regions." Tweaking an environmental parameter might not immediately alter the agent's optimal action, yielding a gradient of zero. However, when a parameter crosses a critical threshold, the optimal policy shifts abruptly, creating a sharp, non-differentiable boundary.
- Discrete Indicator Functions: In fields like precision medicine, individualized decision rules are often defined by discrete indicator functions (e.g., "if biomarker $> X$, administer treatment"). As explained by Lan Wang et al. in Transformation-Invariant Learning of Optimal Individualized Decision Rules with Time-to-Event Outcomes, these step functions produce non-smooth objective functions where directional signals are completely absent.
Bridging the Gap: How We Optimize Non-Differentiable Policies
To navigate these challenging terrains, researchers have developed several core strategies that either smooth out the landscape or use continuous models to guide the discrete search.
Neural Guidance and Space Projection
One powerful intuition is to use a continuous "oracle" to guide the discrete search. In Programmatically Interpretable Reinforcement Learning, Abhinav Verma et al. introduce Neurally Directed Program Search (NDPS). Instead of searching the discrete program space blindly, they first train a high-performing neural network policy. This continuous network acts as a teacher, providing a smooth directional signal that guides the program synthesis engine toward high-reward regions of the code space.
Building on this, the authors extended the idea in Imitation-Projected Programmatic Reinforcement Learning via a meta-algorithm called PROPEL. PROPEL frames the problem as constrained mirror descent. It "lifts" a programmatic policy into a continuous, flexible neural-programmatic space where gradient updates are possible, and then "projects" it back into a pure, verifiable program using imitation learning. This allows optimization to exploit continuous gradients without sacrificing the final model's interpretability. While early methods relied heavily on these pre-trained neural teachers, subsequent work by Wenjie Qiu et al. in Programmatic Reinforcement Learning without Oracles demonstrated that differentiable architecture search can also synthesize programs directly from reward signals, bypassing the need for an oracle entirely.
Landscape Smoothing via Regularization
Instead of using a neural guide, can we make the landscape itself smooth? In Adaptive Model Design for Markov Decision Process, Siyu Chen et al. tackle the abrupt policy shifts that plague bilevel Markov Decision Process (MDP) optimization. They introduce entropy regularization into the agent's policy. By forcing the agent to maintain a softer, probabilistic strategy rather than a hard deterministic choice, the sharp, non-differentiable boundaries are smoothed out. This transformation allows a two-timescale gradient algorithm to successfully optimize environmental parameters.
Generative and Language Model-Assisted Search
With the advent of Large Language Models (LLMs), researchers have found a new way to navigate the sparse, discrete search space of executable code. Rather than relying on rigid syntax mutations, Zhiyi Kuang 0003 et al. in Learning Game-Playing Agents with Generative Code Optimization use LLMs to iteratively write, test, and refine Python code policies based on environment feedback.
Similarly, Quazi Asif Sadmine et al. developed LS-LLM in Language Models Speed Up Local Search for Finding Programmatic Policies, utilizing LLMs to provide intelligent "warm starts" for local search algorithms. The LLM acts as a proposal distribution that understands code semantics, bypassing the random, destructive mutations that typically cause programmatic optimization to stall.
[Continuous Space] ──(Smooth Gradients)──> Easy Optimization (Neural Networks)
│
[Bridging Mechanisms]
│
▼
• Neural Guidance & Projection (PROPEL)
• Entropy Regularization (Smoothing)
• LLM Code Mutation (Semantic Search)
│
▼
[Discrete Space] ──(Jagged/Flat)───────> Hard Optimization (Code, Rules, Logic)
Global and Derivative-Free Optimization
When gradients are completely unavailable and cannot be approximated, global derivative-free optimization becomes necessary. David Wingate et al. in Bayesian Policy Search with Policy Priors reframe discrete policy search as a probabilistic inference task, using structured policy priors to constrain the search space when a clear gradient is absent. In precision medicine, Lan Wang et al. employ genetic algorithms to directly navigate the discontinuous thresholds of indicator-based decision rules without requiring a pre-specified regression model.
Why This Matters: Transparency and Control
The push to optimize non-differentiable policies is driven by necessity. While end-to-end neural networks are easy to train, they fail in environments requiring hard safety constraints, formal verification, or extreme generalization.
For example, Bo Zhou et al. show in Action Set Based Policy Optimization for Safe Power Grid Management that standard RL agents gamble with critical physical constraints, requiring discrete search steps or external simulators that break backpropagation. Furthermore, as Yasasa Abeysirigoonawardena et al. highlight in Generating Transferable Adversarial Simulation Scenarios for Self-Driving via Neural Rendering, modular control stacks with non-differentiable logic are naturally resilient to standard gradient-based adversarial attacks, but conversely harder to stress-test without specialized differentiable sandboxes.
By developing algorithms that can directly optimize across code, rules, and discrete transitions, this research direction ensures we do not have to choose between the high performance of modern machine learning and the safety, interpretability, and robustness of symbolic logic.
Key Foundational Work
Programmatically Interpretable Reinforcement Learning (2018) — contributed 1 concept elements to this direction.
Bayesian Policy Search with Policy Priors (2011) — contributed 1 concept elements to this direction.