1
00:00:01,000 --> 00:00:43,910
[Hal Turing] Alrighty! Thanks for tuning in! Hello AI world! I am your host, Hal Turing, and my co-host is Dr. Ada Shannon. Today we're digging into a paper called Programmatically Interpretable Reinforcement Learning, by Abhinav Verma as first author, with four co-authors — Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri. That's a Rice University, Google Brain, and DeepMind collaboration, presented at ICML 2018, with the arXiv posting dated back to April 2018. And Ada, the thing that jumped out at me immediately is the framing: they basically say, forget explaining a neural network after the fact — what if the policy itself was just... readable code?

2
00:00:43,910 --> 00:01:20,226
[Dr. Ada Shannon] Right, and that's a much harder ask than it sounds. Most of what people call 'interpretable deep RL' is really post-hoc — you train the black box, then you slap a saliency map or an attention visualization on top and squint at it. This paper refuses that compromise entirely. They want the policy to literally be a short program you could print out and read top to bottom, in a restricted language they design for the task. No decoder ring required. And the reason that matters isn't academic purity — it's that you can't formally verify a saliency map. You can verify a program.

3
00:01:20,226 --> 00:01:30,164
[Hal Turing] So walk me through why that verification piece is such a big deal. I get that 'humans can read it' is nice, but the paper seems to be making a stronger claim than just readability.

4
00:01:30,164 --> 00:02:08,756
[Dr. Ada Shannon] It is. Think about deploying a policy in a self-driving car or an industrial controller — somewhere a bad action isn't just a wrong label, it's a crash. With a deep network, millions of weights, you basically cannot prove 'this car never exceeds a given speed off-track' or 'the steering output is always bounded.' It's not that nobody's tried — it's that the property-checking tools choke on networks that size. A program in a small domain-specific language is a completely different animal for a theorem prover or a symbolic execution engine to chew on. That's the whole motivation for what they call PIRL — Programmatically Interpretable Reinforcement Learning.

5
00:02:08,756 --> 00:02:19,158
[Hal Turing] Okay, define that properly for people who haven't seen the term. PIRL isn't just 'use a decision tree instead of a network,' right? There's something more structured going on.

6
00:02:19,158 --> 00:02:56,914
[Dr. Ada Shannon] Right, PIRL is a framework, not a single algorithm. You still have your normal RL setup — states, actions, a reward signal — but instead of letting the policy be any differentiable function a network can represent, you constrain it to programs written in a high-level language you've designed for the domain. And crucially, you also supply what they call a policy sketch — think of it as a grammar, a template with holes in it, that says 'the policy looks like this shape, and here's what's still unknown.' It's a structural prior, and it's also a regularizer, because it rules out the vast majority of garbage programs before search even starts.

7
00:02:56,914 --> 00:03:03,880
[Hal Turing] Give me the concrete example, because I think that's where this clicks. I know they use a driving sketch — some kind of branching PID setup.

8
00:03:03,880 --> 00:03:46,233
[Dr. Ada Shannon] Yeah, this is the running example for the whole paper — Figure 2, if anyone's got the PDF open. The sketch says: the policy is a switch statement that branches on some unknown condition, and each branch is a classic Proportional-Integral-Derivative controller — a PID controller, decades-old control theory, the same math that's been running cruise control and thermostats since before either of us was born. The unknown piece is the branch condition itself, framed around a variable called TrackPos, how far the car is from the center of the track, plus the PID gains inside each branch. So the search isn't 'find any program' — it's 'fill in these specific numeric and logical blanks in a shape we already believe in.'

9
00:03:46,233 --> 00:03:58,447
[Hal Turing] Sure, but that space is still not something you can just backprop through — there's no gradient through 'pick a branch.' So how do they actually search it? This is where I assume the neural network sneaks back in.

10
00:03:58,447 --> 00:04:38,060
[Dr. Ada Shannon] Exactly, and this is the clever part — it's called Neurally Directed Program Search, NDPS. Step one: just train an ordinary deep RL policy network the normal way, DDPG or whatever, ignore interpretability entirely. That network becomes an oracle. Step two: do a local search over programs in your sketch — not to maximize reward directly, which is the nasty nonsmooth problem — but to minimize the distance between the program's outputs and the oracle's outputs on a set of sampled states. You've converted 'search a jagged discrete space for a reward peak' into a series of supervised regression problems chasing a smooth target. That reframing is the whole trick.

11
00:04:38,060 --> 00:04:44,980
[Hal Turing] Oh wait, that's basically imitation learning — the program is imitating the neural net instead of imitating a human demonstrator.

12
00:04:44,980 --> 00:05:31,094
[Dr. Ada Shannon] That's exactly right, and they say so explicitly — it's inspired by DAgger, the Dataset Aggregation algorithm from Ross, Gordon, and Bagnell, out of Carnegie Mellon, 2011. DAgger's insight was that naive behavioral cloning falls apart because your learner drifts off the expert's distribution and never learned how to recover — so instead you interactively query the expert on states the learner actually visits, and keep growing your training set. NDPS borrows that iterative 'expand the interesting inputs, retrain' loop. But it's not a clean transplant — DAgger's regret guarantees are about matching an expert's actions exactly, while NDPS is chasing reward through the proxy of imitation distance, which is a subtly different optimization target we'll want to come back to.

13
00:05:31,094 --> 00:05:38,711
[Hal Turing] So before we get anywhere near TORCS or lap times — that's a genuinely different way to think about getting a policy you can actually trust.

14
00:05:38,711 --> 00:06:17,256
[Dr. Ada Shannon] Right — and the key move is that once DDPG trains that oracle, per Lillicrap and colleagues' continuous-control paper out of DeepMind, 2015, the network is frozen. It never gets touched again. From there NDPS searches program templates: take the current-best program, replace its numeric constants with open parameters, elide a couple of subexpressions, then regenerate them from the sketch grammar, always favoring the shortest replacement. So you're never searching the full infinite program space — you're searching a tight neighborhood of 'things that look like this program but slightly different,' and scoring each candidate by how closely it imitates the oracle's outputs on a working set of histories.

15
00:06:17,256 --> 00:06:36,760
[Hal Turing] Okay, and that scoring step — finding the actual parameter values inside a template — is still a real-valued optimization problem over continuous numbers. How do they actually solve that, and does it connect back to the DAgger-style loop you mentioned earlier, where the set of histories itself keeps getting refreshed as the search progresses?

16
00:06:36,760 --> 00:07:21,528
[Dr. Ada Shannon] Two separate pieces, both worth naming. For parameters, their primary tool is Bayesian optimization, from Snoek, Larochelle, and Adams out of Harvard and the University of Toronto, 2012 — treat summed distance-to-oracle as a black-box function and let a Gaussian process guide the search. They also tried an SMT-based alternative, a MaxSAT formulation where each sampled history is a weighted constraint. That one collapses once actions are continuous vectors rather than a handful of discrete choices, so TORCS uses Bayesian optimization exclusively. And yes, the history set is exactly the DAgger-style piece — the current program drives, you sample where it disagrees with the oracle, and fold those states back in as input augmentation.

17
00:07:21,528 --> 00:07:52,504
[Hal Turing] Oh — hold on, before we get to any numbers, I want to plant a flag on the setup itself, because it matters for how we read everything downstream. This is DDPG with full-state access, no restrictions, running in TORCS's Practice Mode — no pit stops, no race-level strategy, just 29 sensors feeding acceleration and steering — on two tracks, CG-Speedway-1 and the noticeably harder Aalborg. That's the baseline everything gets measured against.

18
00:07:52,504 --> 00:08:53,619
[Dr. Ada Shannon] Correct on all counts, and it sets up the ablation results nicely. Naive — no oracle guidance at all — crawls to 2:07 on CG-Speedway-1 and times out completely on Aalborg. NoAug and NoSketch both time out on both tracks after the twelve-hour synthesis budget expires. NoSketch fails because the raw grammar from Figure 1 is unconstrained enough that random sampling almost never lands on a working controller. NoAug fails because without refreshing the history set, the synthesizer gets no oracle guidance once the program drifts off-distribution. But here's the part worth sitting with: NoIF — no branching, one fixed PID controller for the whole lap — scores 115.25 reward on CG-Speedway-1 and 52.81 on Aalborg. Full NDPS, with the TrackPos-switching sketch, scores 115.32 and 54.91. That's within rounding error on both tracks.

19
00:08:53,619 --> 00:09:37,087
[Hal Turing] Which is strange, because that TrackPos branch was the whole motivating example — the thing that made this feel like more than 'fit one controller and call it a day.' If a single fixed PID nearly matches the branching version on reward, what was the branching actually buying them here? And does the smoothness story hold up any better — DRL's steering standard deviation comes in at 0.60 on CG-Speedway-1 and 0.90 on Aalborg, versus 0.13 and 0.25 for NDPS. That's a four-to-five-times reduction. Is that programs being inherently smoother, or something about how DDPG itself was set up?

20
00:09:37,087 --> 00:10:48,186
[Dr. Ada Shannon] On smoothness, lean toward the setup explanation — nothing in their DDPG configuration includes a jerk penalty or reward shaping against rapid steering changes, so 'unregularized DDPG is jerky' is the more honest framing than 'programs are categorically smoother.' Where the paper is on firmer ground is robustness. Block the RPM and TrackPos sensors at 50 percent probability on CG-Speedway-1, and DDPG crashes after 21 meters while NDPS goes 1,976. At 90 percent it's 17 versus 200. Transfer to unseen tracks is even starker — DDPG crashes on every single transfer track, CG Track 2, E-Road, Alpine 2, Ruudskogen, while NDPS completes all of them at comparable lap times. And on verification: they prove a smoothness bound and universal action bounds via symbolic execution on the synthesized program, something Reluplex — Katz, Barrett, Dill, Julian, and Kochenderfer, Stanford, 2017 — can't touch, since it tops out around 300-node networks and their DDPG net has three 600-node layers.

21
00:10:48,186 --> 00:11:20,369
[Hal Turing] That setup gap compounds the branching problem too, Ada — NDPS ties NoIF, the no-branch single-PID version, on reward on both tracks. The paper's own headline illustration, that TrackPos switch in Figure 2, isn't earning its keep experimentally. The real contribution might just be sketch-plus-oracle-search as a synthesis method, independent of whether the program branches at all. So how much of the DAgger lineage you mentioned actually transfers here as a guarantee, versus just inspiration?

22
00:11:20,369 --> 00:11:56,731
[Dr. Ada Shannon] None of it, formally. NDPS borrows DAgger's aggregation mechanic — collect states, relabel with the oracle, retrain — but optimizes distance-to-oracle as a proxy for reward, not exact behavioral matching, so none of DAgger's regret proof carries over to 'minimizing that distance also maximizes reward.' It's a justified heuristic, not a derived guarantee. And the oracle itself, Lillicrap and colleagues' DDPG from DeepMind, 2015, is exactly the architecture whose training instability is doing unacknowledged work here, both as what NDPS imitates and what it's compared against.

23
00:11:56,731 --> 00:12:34,162
[Hal Turing] Oh — wait, hold on, that ties right into the sensor-dropout robustness numbers. They block RPM and TrackPos, and NDPS survives to 1976 meters where DRL crashes at 21. But the paper admits those are exactly the sensors 'the synthesized programs crucially depend on' — they picked the failure mode the program was structurally built to tolerate. Was DDPG ever exposed to blocked sensors in training? If not, this isn't programs beating neural nets, it's trained-for-the-fault beating never-trained-for-it.

24
00:12:34,162 --> 00:13:30,308
[Dr. Ada Shannon] It doesn't — same network, full observability during training, evaluated cold against a fault it never saw. A PID controller's boundedness gives it free robustness to a null reading defaulting a guard one way or the other; that's the control structure, not proof programs beat nets on a fair test. The transfer failure is the same shape — suspiciously total, which smells like no domain randomization and single-track overfitting, not a ceiling on neural transfer. Then the classic-control appendix undercuts the abstract's own language: NDPS-BOPT scores 143 on CartPole against a 195 solved threshold, and negative 127 on Acrobot against DRL's negative 63. Two of three land clearly below the bar the paper claims to clear. As for Reluplex's node limit, it's dated now — branch-and-bound verifiers handle that scale routinely today.

25
00:13:30,308 --> 00:14:25,664
[Hal Turing] There's a deeper soundness gap underneath all of it, too — that branching-PID template comes straight out of Solar-Lezama's sketching work, MIT, 2009, and it's entirely hand-designed. Nobody verifies the sketch itself is the right inductive bias for the safety property you'd actually care about; a human could write a plausible, reward-competitive sketch that structurally excludes the one branch needed for a rare unsafe corner case, and NDPS would fit it and call it verified. That's the scope-versus-claims problem in miniature: the abstract reads as a general pitch for verifiable RL, but what's tested is one hand-crafted sketch on TORCS Practice Mode plus three toy Gym games, fully symbolic, no pixels, no race strategy. The 'this generalizes' inference leans on a domain expert already knowing PID is the right shape before the algorithm ever runs.

26
00:14:25,664 --> 00:15:17,630
[Dr. Ada Shannon] That's the part I'd flag for practitioners too — the paper treats the neural oracle as disposable scaffolding, thrown away the moment it's distilled. Later neurosymbolic and mixture-of-experts control work treats that oracle as worth keeping — a fallback for out-of-sketch states, or a richer teacher for continual re-distillation as conditions drift. If you're building on this today, that's the obvious upgrade: don't throw away DDPG once you've got your program, keep it as a safety net. Practically, this is a method for teams that already have domain expertise about the right control structure and need verifiability more than raw performance — not a general recipe for interpretable RL from scratch. Future work the authors flag themselves — pixel inputs, stochastic policies, extending sketches beyond RL — all still stand as open problems today.

27
00:15:17,630 --> 00:15:57,011
[Hal Turing] So here's where I land: the durable results are transfer and sensor-dropout robustness — DRL crashing on every transfer track while NDPS finishes all of them is a hard number to argue with. The smoothness story and the branching-versus-single-PID story are both softer than the framing implies, and the classic-control results sit below the bars the abstract suggests they cleared. What NDPS actually proves is that oracle-guided local search over a good sketch is a workable way to synthesize interpretable, verifiable policies — the specific branch in Figure 2 was never really the point. Worth reading critically, not dismissing. Thanks for digging through it with me, Ada.

28
00:15:57,011 --> 00:16:04,303
[Dr. Ada Shannon] Always a good one when the ablation table argues with the abstract. Thanks for listening, everyone — that's it for this one, we'll see you next time.