Globally Optimal Policy Extraction with Gated Convex Programs

Deep reinforcement learning policies are hard to audit. The usual fix is to copy their behavior into a small decision tree whose rules a person or a formal verifier can check. Every current way of fitting that tree has one of two problems. It either picks splits greedily one node at a time, as VIPER's CART step does, or it trains split and leaf parameters jointly by gradient descent, as differentiable trees do, and gradient descent can stop in a poor solution. So when an extracted tree is huge or unfaithful, nobody can say whether small interpretable policies are inherently weak or whether the optimizer failed to find a good one.

We propose to remove that doubt. First, build a large dictionary of candidate splitting hyperplanes over the state space. Then fit the policy as a sum of "gated" linear controllers, where each controller is switched on only on one side of its hyperplane. With the hyperplanes fixed, this imitation problem is a convex Group Lasso. A convex problem has no spurious local minima, so a fast solver reaches its global optimum from any starting point. The sparsity penalty chooses a handful of hyperplanes and their controllers together. The selected hyperplanes then compile exactly into a piecewise-linear policy whose regions are intersections of half-spaces, and that form can be checked by linear programming or SMT solvers. The result is policy extraction whose fidelity-versus-size tradeoff is certified optimal over a stated candidate set, instead of being an artifact of initialization.

Core Claim

The claim is that the convex reformulation of two-layer ReLU networks can serve as the fitting step inside criticality-weighted policy extraction. That reformulation fixes neuron on/off patterns so the network turns into a Group Lasso problem (Pilanci et al.; Mishkin et al.). Used this way, it yields interpretable controllers that are globally optimal for the imitation objective at each extraction round. Because the problem is convex, its solutions along the regularization path trace the best achievable fidelity at each size for the given dictionary. That lets us measure, for the first time, how much of the gap between compact trees and deep teachers comes from optimization and how much from the policy class.

Concretely, let $s$ be a state and $g_1,\dots,g_M$ the fixed candidate hyperplanes. The student's continuous action is $\pi(s)=\sum_{i=1}^M \mathbf{1}[g_i^\top s\ge 0]\,U_i s$, where $U_i$ is a matrix mapping state to all action dimensions. Given teacher actions $a^*(s)$ on states $s$ collected by DAgger (an imitation loop that repeatedly rolls out the student and relabels the visited states with the teacher's action), and VIPER's criticality weight $w(s)=\max_a Q^*(s,a)-\min_{a'}Q^*(s,a')$, we solve

$$\min_{U_1,\dots,U_M}\ \sum_{s\in\mathcal{D}} w(s)\,\ell\big(\pi(s),a^*(s)\big)+\lambda\sum_{i=1}^M \lVert U_i\rVert_F ,$$

where $\ell$ is squared error for continuous actions or cross-entropy for discrete ones, $\mathcal{D}$ is the aggregated state set, and $\lambda$ controls how many hyperplanes survive. The objective is convex in the $U_i$. The penalty on each whole block $U_i$ removes a hyperplane for every actuator at once. This also sidesteps the per-output separation that Convex Distillation had to patch with a separate polishing step.

Relation to Prior Work

Three papers motivate the gap by showing where current extraction breaks. VIPER extracts trees from a deep oracle using Q-weighted DAgger and verifies them formally, but it fits each tree with greedy axis-aligned CART. It needs over 9,000 nodes on Half-Cheetah. ICCT trains crisp trees with sparse linear leaves end-to-end with Soft Actor-Critic and reaches strong results, but the paper reports sensitivity to depth and other hyperparameters. RADDT rewrites hard oblique routing with ReLU path violations and a softmin that is annealed toward a hard choice. It beats CART by 7.54% on tabular data, but its objective stays non-convex, and it never treats control. We keep VIPER's weighting and verification pipeline and ICCT's linear-leaf controllers. What we replace is the fitting step: a convex program instead of greedy splitting or gradient descent.

Two papers supply the method. Mishkin et al. introduce gated ReLU Group Lasso problems and R-FISTA, a restarted accelerated proximal-gradient solver that runs on GPUs. On synthetic landscapes where SGD missed the global optimum 40% of the time, their convex solver found it every time. Convex Distillation fixes gates from teacher activations to compress a network block convexly. That work stays in supervised vision and keeps a dense, uninterpretable student. Our contribution is to use the sparsity of the Group Lasso solution as the interpretability mechanism, to take gates from state-space geometry rather than only from teacher neurons, and to put the program inside a sequential imitation loop.

Two papers constrain the design. Pilanci et al. show that enumerating hyperplane arrangements exactly grows exponentially in data rank. We therefore claim optimality only over a sampled dictionary, never over all oblique trees. CoRR avoids local minima by fitting a convex envelope to black-box queries, but it depends on the right basis being chosen by hand. Our dictionary plays the same role, so choosing the dictionary is the main risk and gets its own ablation.

Research Program

The dictionary combines four sources: random hyperplanes through pairs of visited states, following the arrangement sampling of Pilanci et al.; the first-layer hyperplanes of the teacher network, following Convex Distillation; axis-aligned thresholds at data quantiles, so CART's candidate splits are included; and, as an extension, conjunction gates equal to leaf regions of a large overgrown oblique tree. Conjunction gates are still fixed indicators, so the problem stays convex, and the program then performs globally optimal sparse pruning of a tree.

Each DAgger round solves the weighted program with R-FISTA over a grid of $\lambda$ values, warm-starting each $\lambda$ from the previous solution. The selected hyperplanes are then compiled into a region table: each nonempty cell visited by data becomes a polyhedron with its own linear controller. That table is emitted as an oblique tree whose depth is at most the number of selected hyperplanes.

Our size metrics are three: selected hyperplanes, visited cells, and total nonzero parameters. We report all three because the penalty directly limits only hyperplanes. Verification reuses VIPER's toolchain: linear programming for local robustness, SMT for reachability on Toy Pong and Pong, and Sum-of-Squares for Cart-Pole stability.

One honest limit must be stated. Global optimality holds per round for the imitation objective. It does not hold for closed-loop return, because DAgger's shifting state distribution sits outside the convex program. Separately, we will test whether the solutions along the regularization path give a smoother and more reproducible return-versus-size curve than gradient-trained trees do.

Baselines

The naive reference point is VIPER with CART (VIPER), run with the same teacher, the same Q-weights, and the same number of DAgger rounds and environment samples. Its reported results set the bar. On symbolic Atari Pong it reached perfect play with 769 nodes, versus nearly 8,000 for plain DAgger. On Half-Cheetah it needed over 9,000 nodes. Beating it means matching its teacher-normalized return with at least an order of magnitude fewer cells on Half-Cheetah, and with fewer cells on Pong.

The strongest competitor for compact continuous control is ICCT (ICCT). It reports maximum Inverted Pendulum reward with 13 parameters and up to 33% improvement over deep MLPs on the Multi-Lane Ring task in the Flow traffic-simulation suite. For Lunar Lander we found no reported number on Lacuna, so we will run it ourselves. ICCT is the right comparison because it has the same leaf form and the same goal of small crisp policies. We run it at matched leaf counts, with its hyperparameters tuned over a grid whose total GPU-hours equal our full $\lambda$ path. We train it two ways: from reward, as published, and by imitation of the same teacher, so the comparison isolates the optimizer. Beating it means equal or higher return at equal parameter count, with lower spread across seeds.

The strongest gradient-based oblique tree is RADDT-Linear (RADDT), adapted to Q-weighted imitation. It gets the same leaf budget and a restart budget matched to our wall-clock time. The only numbers reported for it are tabular: +7.54% over CART, +2.01% over Random Forest, and +1.12% over XGBoost. For RADDT on control, we found no reported result on Lacuna.

Two ablations isolate the key ingredient. The first freezes RADDT's learned hyperplanes as the whole dictionary and re-solves our convex program. The resulting drop in imitation loss is a direct measure of how much RADDT lost to joint non-convex fitting. The second keeps our model but trains it with Adam from random initialization instead of R-FISTA, which separates the effect of the model class from the effect of convexity.

Why not just…?

Why not just run VIPER with CART and a depth limit? Greedy splits cannot revise early choices. The 9,000-node Half-Cheetah result shows that when depth is unrestricted, CART buys fidelity with size. Because our dictionary contains CART's axis-aligned candidates, any fidelity gain at a fixed number of cells must come from choosing splits jointly, not from a richer candidate set. The axis-aligned-only dictionary ablation tests exactly this.

Why not just train ICCT or RADDT with many random restarts? This is the real threat. On low-dimensional tasks like Cart-Pole, enough restarts may find solutions as good as ours. The matched-budget comparison decides it. If restarted gradient trees reach our imitation loss and return at equal size and equal compute, the contribution shrinks to reproducibility and a certificate that nothing better exists in the dictionary. We will report that outcome plainly. The frozen-hyperplane ablation measures the gap directly rather than inferring it from return.

Why not just alternate: fix the routing, refit leaves by least squares, then refit the splits? Refitting leaves with routing fixed is convex, but refitting the splits is not, so alternation still stalls at whatever routing it started with. Our program instead chooses which hyperplanes to use as part of one convex problem. We include alternating leaf refitting on top of a CART tree as an extra baseline at matched cell counts.

Why not just use the dense convex-distilled student from Convex Distillation? That student is the $\lambda\to 0$ end of our regularization path. It is globally optimal but uses thousands of gates and cannot be audited. Reporting fidelity along the whole path shows how much the teacher's behavior survives sparsification.

Proposed Experiments

We test on Cart-Pole, Toy Pong, and symbolic Atari Pong from VIPER; on Inverted Pendulum, Lunar Lander, and the Flow driving tasks (Lane-Keeping, Single-Lane Ring, Multi-Lane Ring, Figure-8) from ICCT; and on Half-Cheetah as the high-dimensional stress case. Teachers are fixed networks trained with Soft Actor-Critic or DQN and shared by all methods.

Metrics are teacher-normalized return, the number of cells, hyperplanes and parameters, imitation loss on held-out teacher states, standard deviation over ten seeds, solver time, and time to verify.

Four checks decide the proposal. First, on Half-Cheetah, does the convex path reach VIPER-level return with at least ten times fewer cells than VIPER's reported 9,000-plus nodes? Second, for fixed dictionaries, is the chosen policy identical across seeds while ICCT and RADDT vary, and does that stability carry over to return? Third, does re-solving convexly on RADDT's own hyperplanes lower its imitation loss? A lower loss would show that entrapment in poor solutions, not the tree class, limited it. Fourth, do the compiled policies pass the same LP, SMT and Sum-of-Squares checks VIPER ran, in comparable time?

The high-dimensional case is where we expect the approach to break. As the state dimension grows, the dictionary needed to contain good splits may itself grow exponentially, which is the same arrangement blow-up Pilanci et al. describe. We will report how Half-Cheetah fidelity scales with dictionary size, and that curve will show where this approach stops paying off.