REVIEW 5 major objections 5 minor 34 references
Common Benchmarks Undervalue the Generalization Power of Programmatic Policies
T0 review · 5 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read Neural policies can match programmatic policies on out-of-distribution problems when given the same sparse observations and a reward function that encourages caution.
desk verdict Useful empirical critique of programmatic-policy generalization claims, but the central claim outruns the evidence because baselines are imported and TORCS success rates use a selected denominator. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The argument runs on two simple interventions plus one new benchmark. The first intervention is observation matching: the neural policy receives only the sparse percepts the programmatic language exposes (in KAREL, the local perception functions frontIsClear, leftIsClear, rightIsClear, markersPresent) augmented with its previous action, which removes the spurious correlations that a fully observable convolutional network can latch onto. The second is reward caution: lowering the coefficient β in the TORCS reward from 1.0 to 0.5 makes the learned driving policy slower and therefore safer on unseen sharp turns. The new benchmark, SparseMaze, is the load-bearing object for the paper's positive proposal: a sparse maze wide enough that a 'follow the right wall' strategy fails, so solving it requires remembering visited cells and using a queue or stack, which is exactly the algorithmic structure that programmatic policies can express and that the tested neural policies could not learn.
What would settle it
Retrain the programmatic methods under exactly the same sparse observations and cautious reward used for the neural baselines, with the same number of seeds and the same evaluation protocol. If the programmatic policies still generalize while the neural policies fail, the paper's artifact explanation collapses; if the programmatic policies also lose the advantage, the paper's account is supported.
Extended reading notes
Core claim
On its own terms, the paper's central claim is that the OOD generalization advantage previously attributed to programmatic policies on TORCS and KAREL is not a property of the representation. With a fully connected network given the agent's last action as part of a sparse observation, PPO reaches near-perfect returns on 100x100 versions of four KAREL tasks (STAIRCLIMBER, MAZE, TOPOFF, FOURCORNER); with a cautious reward coefficient (β=0.5), DDPG generalizes to unseen TORCS tracks in the majority of trained seeds. In PARKING, neither representation generalizes reliably, so the paper treats it as an open problem. The paper then constructs SparseMaze, a maze with no wall to follow, where a FunSearch-synthesized program implementing breadth-first search generalizes to 100x100 maps while PPO with a GRU fails to learn even the small map.
Load-bearing premise
The load-bearing premise is that the programmatic results imported from the earlier TORCS and KAREL studies are directly comparable to the newly trained neural policies, even though they came from different codebases, seeds, observation preprocessing, and possibly reward settings.
Editorial extensions
If this is right
- The OOD results on TORCS and KAREL should not be used as evidence that programmatic representations generalize better than neural ones; comparisons must match observation spaces, reward functions, and training budgets.
- Adding the previous action to a sparse observation can turn a feedforward network into a policy that generalizes to much larger KAREL grids, suggesting that reported LSTM advantages in partially observable benchmarks deserve re-examination.
- Reward shaping that slows the agent down can convert a non-generalizing TORCS policy into one that generalizes, so claims about representation effects in continuous control should control for the learned policy's risk profile.
- PARKING remains a domain where both programmatic and neural policies struggle, so it does not support either side's generalization claims.
- The SparseMaze proof of concept shows a concrete benchmark where a programmatic, queue-based solution generalizes perfectly while a neural policy fails, which is the kind of problem the field should use to test programmatic advantages.
Reading between the lines
- If this argument extends, many published programmatic-vs-neural OOD comparisons may shrink once training pipelines are matched, so the field would benefit from standardized evaluation protocols that report observation, reward, and seed counts.
- The last-action augmentation trick is a cheap way to give feedforward policies a limited memory; it may solve other benchmarks that were thought to require recurrent networks.
- The cautious-reward intervention suggests a testable symmetry: training a programmatic search method with a fast, aggressive reward may erase its OOD advantage too, which the paper conjectures but does not test.
- SparseMaze points to a broader classification of benchmarks by the data structures they require; such a taxonomy could predict where programmatic policies are genuinely needed rather than merely preferred.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This position paper revisits out-of-distribution (OOD) generalization claims from four programmatic-policy papers and argues that the apparent superiority of programmatic representations is partly an artifact of uncontrolled pipeline choices. The authors present three empirical re-analyses. In TORCS (§4.1), they train DDPG agents with a cautious reward (β=0.5) and report that many of the resulting policies generalize to unseen tracks, contrasting with the earlier DRL β=1.0 failures imported from Verma et al. (2018). In KAREL (§4.2), they train PPO with a fully connected network and the previous action appended to a sparse observation, and report generalization to 100×100 grids comparable to or better than the LEAPS/PPO baselines imported from Trivedi et al. (2021). In PARKING (§4.3), they compare PSM and DQN and conclude that both struggle but PSM generalizes slightly better on some metrics. Finally (§5), they propose SparseMaze, a sparse-corridor short-est-path task, and report that a FunSearch-synthesized Python BFS program generalizes while PPO with a GRU fails. The paper concludes that benchmarks undervalue programmatic policies because simple neural training changes close the OOD gap, and suggests future benchmarks that require algorithmic data structures.
Significance. If the central comparison were tightly controlled, this would be a valuable contribution: it would undermine the evidence base for the common claim that programmatic representations generalize better on TORCS and KAREL, and it would redirect attention to benchmark design. The paper's strengths include public code, explicit hyperparameter sweeps in appendices, and an honest presentation of the metric-dependent PARKING result. However, as it stands, the load-bearing comparisons are not controlled: programmatic and neural baselines are drawn from different codebases, seed protocols, and sometimes reward/observation settings, and the neural success rates are computed after filtering out seeds that failed to learn the training task. The evidence therefore supports a weaker claim than the abstract states: certain neural training choices can help OOD generalization on these benchmarks, but the paper does not yet show that the programmatic-vs-neural gap disappears under a fair controlled comparison.
major comments (5)
- [§4.1, Table 1] The central TORCS comparison is not controlled. The NDPS and DRL β=1.0 rows are imported from Verma et al. (2018), while DRL β=0.5 is run in the authors' own DDPG implementation. Thus the reward coefficient β changes together with codebase, environment wrapper, observation preprocessing, and evaluation seeds. To support the claim that 'simple changes to the reward function' close the OOD gap, the authors must re-run DRL β=1.0 in their own code and, ideally, run NDPS under the same protocol; otherwise the observed gap closure could be an implementation effect rather than a reward effect.
- [§4.1, Table 1] The reported generalization fractions 0.76, 0.69, and 1.00 are computed only over seeds that successfully completed training laps (13 of 30 and 4 of 15). As fractions of all trained seeds, the corresponding success rates are 0.33, 0.30, and 0.27 (10/30, 9/30, and 4/15). Selecting on training success inflates the OOD generalization estimate, and the paper does not report the training-success rate of the imported programmatic and β=1.0 baselines under the same criterion. Without a common denominator, the 'most models trained with β=0.5 generalize' statement is not supported.
- [§4.2, Table 2] The KAREL comparison has the same confound: LEAPS, PPO-ConvNet, and PPO-LSTM rows are imported from Trivedi et al. (2021) (marked †), while the new 'PPO with at−1' rows are produced by the authors' code. The observation change (sparse perception plus last action) is therefore entangled with differences in environment implementation, reward setup, training protocol, and evaluation seeds. A stronger design would run at least the fully observable PPO-ConvNet and partially observable PPO-LSTM baselines in the same codebase, or report that the imported numbers were reproduced under identical conditions. The claim that sparse observations and a simpler model cause the improvement is not yet isolated.
- [§4.3, Table 3] The PARKING conclusion is metric-dependent and the text acknowledges this but still draws a directional conclusion. By test 'Success Rate', DQN (0.18) outperforms PSM (0.16); by the training-to-test gap, PSM looks better (0.10 vs 0.68); by 'Successful-on-100', both are near zero (0.06 vs 0.00). The summary statement that 'programmatic policies generalized slightly better than neural policies' is not robust to the choice of metric, and no confidence intervals or significance tests are provided. The paper should either commit to a prespecified primary metric or present the result as inconclusive for both representations.
- [§5, Table 4] The SparseMaze experiment is a proof-of-concept but is not yet evidence for the paper's benchmarking proposal. FunSearch results are reported for a single run ('a single run of the system'), while PPO results are averaged over 30 seeds; moreover, the PPO-GRU baseline fails to learn the training task (return 0.09 on Original), so the comparison does not demonstrate OOD generalization advantage over a neural policy that actually solves the training distribution. Multiple FunSearch runs (or at least a statement of run-to-run variance) and a neural baseline that learns Original are needed before concluding that programmatic representations uniquely handle this task.
minor comments (5)
- [§4.1, Equation (2)] The reward expression is referred to as 'Equation 2' in the text, but it is not numbered in the manuscript; please add a number or remove the reference.
- [§4.3, Table 3] The table header says 'Successful Rate' while the text consistently uses 'Success Rate'; please harmonize the terminology.
- [§4.2, Table 2] For 'PPO with at−1', please specify exactly which observation features are included (the four local sensors, the last action, and any absolute information such as marker presence) and how this maps to the perception functions of LEAPS. The current description leaves ambiguity about whether the observation spaces are truly matched.
- [Appendix C, Table 10] The selected value for 'Action resolution' is listed as '2 million', which appears to be a copy-paste error from the replay buffer size; this makes the hyperparameter table internally inconsistent.
- [References] Several reference entries contain formatting artifacts, e.g., '733?742' in the Grooten et al. entry and 'wake?sleep' in the Ellis et al. entry; these should be corrected to proper en-dashes or hyphens.
Circularity Check
No circular derivation: the paper's claims rest on new experiments and external published baselines, not on self-referential definitions or fitted predictions.
full rationale
This is an empirical position paper rather than a derivation. The central claim is that neural policies can match programmatic policies on OOD benchmarks when given sparse observations or cautious reward functions. Each supporting experiment is run against external published results (Verma et al. 2018, Trivedi et al. 2021, Inala et al. 2020), and the new neural baselines are trained and evaluated with standard RL pipelines. The TORCS manipulation varies the reward parameter beta; slower driving is induced by the reward, but the OOD generalization result is a measured outcome, not an identity or a fitted prediction. The KAREL experiments compare PPO variants with the programmatic LEAPS baseline and report new results; the conclusion that sparse observations plus a simpler model generalize is an empirical finding. The PARKING and SPARSEMAZE experiments are also new evaluations against external systems. No load-bearing step reduces by construction to its own inputs, and no central premise is justified only by a self-citation. Concerns about cross-codebase comparability of imported baselines or about success-rate denominators are threats to experimental validity, not circularity, and do not warrant a nonzero circularity score under the stated criteria.
Assumptions & free parameters
free parameters (2)
- TORCS reward speed-penalty coefficient beta =
0.5 (original 1.0)
- PARKING reward shaping weights =
2 (x-distance weight), 1 (y-distance weight), -1 step penalty, terminal rewards +/-2 x max episode length
assumptions (3)
- domain assumption The MDP formulation and DSL grammars from Verma et al. (2018), Trivedi et al. (2021), and Inala et al. (2020) are correctly summarized and the prior results are accurate.
- domain assumption The sparse observation used by programmatic policies is sufficient for the neural agents to solve the tasks, or can be made sufficient by appending the last action.
- domain assumption Recurrent neural networks are practically limited when tasks require stack or queue memory.
Cite this review
Pith. "Pith review of Common Benchmarks Undervalue the Generalization Power of Programmatic Policies." pith.science (2026). https://pith.science/paper/HGECUWRE
@misc{pith2026250614162,
author = {Pith},
title = {Pith review of: Common Benchmarks Undervalue the Generalization Power of Programmatic Policies},
year = {2026},
howpublished = {\url{https://pith.science/paper/HGECUWRE}},
note = {Machine review of arXiv:2506.14162}
}
read the original abstract
Algorithms for learning programmatic representations for sequential decision-making problems are often evaluated on out-of-distribution (OOD) problems, with the common conclusion that programmatic policies generalize better than neural policies on OOD problems. In this position paper, we argue that commonly used benchmarks undervalue the generalization capabilities of programmatic representations. We analyze the experiments of four papers from the literature and show that neural policies, which were shown not to generalize, can generalize as effectively as programmatic policies on OOD problems. This is achieved with simple changes in the neural policies training pipeline. Namely, we show that simpler neural architectures with the same type of sparse observation used with programmatic policies can help attain OOD generalization. Another modification we have shown to be effective is the use of reward functions that allow for safer policies (e.g., agents that drive slowly can generalize better). Also, we argue for creating benchmark problems highlighting concepts needed for OOD generalization that may challenge neural policies but align with programmatic representations, such as tasks requiring algorithmic constructs like stacks.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[1]
write newline
" write newline "" before.all 'output.state := FUNCTION fin.entry add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sentence 'output.state := if if FUNCTION not #0 #1 if FUNCTION and 'skip pop #0 if FUNCTIO...
-
[2]
Aws Albarghouthi, Sumit Gulwani, and Zachary Kincaid. Recursive program synthesis. In International Conference Computer Aided Verification, CAV , pages 934--950, 2013
work page 2013
-
[3]
Unveiling options with neural network decomposition
Mahdi Alikhasi and Levi Lelis. Unveiling options with neural network decomposition. In The Twelfth International Conference on Learning Representations , 2024
work page 2024
-
[4]
Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, Binyuan Hui, Luo Ji, Mei Li, Junyang Lin, Runji Lin, Dayiheng Liu, Gao Liu, Chengqiang Lu, Keming Lu, Jianxin Ma, Rui Men, Xingzhang Ren, Xuancheng Ren, Chuanqi Tan, Sinan Tan, Jianhong Tu, Peng Wang, Shijie Wang, Wei Wang, Shengguang Wu, Benfeng X...
work page 2023
-
[5]
Verifiable reinforcement learning via policy extraction
Osbert Bastani, Yewen Pu, and Armando Solar-Lezama. Verifiable reinforcement learning via policy extraction. In Proceedings of the International Conference on Neural Information Processing Systems , pages 2499--2509, 2018
work page 2018
-
[6]
Look where you look! saliency-guided q-networks for generalization in visual reinforcement learning
David Bertoin, Adil Zouitine, Mehdi Zouitine, and Emmanuel Rachelson. Look where you look! saliency-guided q-networks for generalization in visual reinforcement learning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems , 2022
work page 2022
-
[7]
Olausson, Lionel Wong, Gabriel Grand, Joshua B
Matthew Bowers, Theo X. Olausson, Lionel Wong, Gabriel Grand, Joshua B. Tenenbaum, Kevin Ellis, and Armando Solar-Lezama. Top-down synthesis for library learning. Proceedings of the ACM on Programming Languages , 2023
work page 2023
-
[8]
Babble: Learning better abstractions with e-graphs and anti-unification
David Cao, Rose Kunkel, Chandrakana Nandi, Max Willsey, Zachary Tatlock, and Nadia Polikarpova. Babble: Learning better abstractions with e-graphs and anti-unification. Proceedings of the ACM on Programming Languages , 2023
work page 2023
Show all 34 references
-
[9]
Empirical evaluation of gated recurrent neural networks on sequence modeling, 2014
Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks on sequence modeling, 2014
2014
-
[10]
Dijkstra
Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik , 1:269--271, 1959
1959
-
[11]
Dreamcoder: growing generalizable, interpretable knowledge with wake?sleep bayesian program learning
Kevin Ellis, Lionel Wong, Maxwell Nye, Mathias Sabl-Meyer, Luc Cary, Lore Pozo, Luke Hewitt, Armando Solar-Lezama, and Joshua Tenenbaum. Dreamcoder: growing generalizable, interpretable knowledge with wake?sleep bayesian program learning. Philosophical Transactions of the Roya...
2023
-
[12]
Taylor, A
Bram Grooten, Tristan Tomilin, Gautham Vasan, Matthew E. Taylor, A. Rupam Mahmood, Meng Fang, Mykola Pechenizkiy, and Decebal Constantin Mocanu. Madi: Learning to mask distractions for generalization in visual deep reinforcement learning. In Proceedings of the International Co...
2024
-
[13]
Long short-term memory
Sepp Hochreiter and J \"u rgen Schmidhuber. Long short-term memory. Neural Computation , 9(8):1735--1780, 1997
1997
-
[14]
Synthesizing programmatic policies that inductively generalize
Jeevana Priya Inala, Osbert Bastani, Zenna Tavares, and Armando Solar - Lezama. Synthesizing programmatic policies that inductively generalize. In International Conference on Learning Representations , 2020
2020
-
[15]
Inferring algorithmic patterns with stack-augmented recurrent nets
Armand Joulin and Tomas Mikolov. Inferring algorithmic patterns with stack-augmented recurrent nets. In Advances in Neural Information Processing Systems (NeurIPS) , volume 28, 2015
2015
-
[16]
Kingma and Max Welling
Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In International Conference on Learning Representations , 2014
2014
-
[17]
Lillicrap, Jonathan J
Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning, 2019
2019
-
[18]
Rubinstein, and Yohai Gat
Shie Mannor, Reuven Y. Rubinstein, and Yohai Gat. The cross entropy method for fast policy search. In Proceedings of the International Conference on Machine Learning , pages 512--519, 2003
2003
-
[19]
Human-level control through deep reinforcement learning
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature , 518(7540):529--533, 2015
2015
-
[20]
Palmarini, Christopher G
Alessandro B. Palmarini, Christopher G. Lucas, and N. Siddharth. Bayesian program learning by decompiling amortized knowledge. In Proceedings of the International Conference on Machine Learning , 2024
2024
-
[21]
Programmatic reinforcement learning without oracles
Wenjie Qiu and He Zhu. Programmatic reinforcement learning without oracles. In International Conference on Learning Representations , 2021
2021
-
[22]
Synthesizing libraries of programs with auxiliary functions
Habibur Rahman, Thirupathi Reddy Emireddy, Kenneth Tjhia, Elham Parhizkar, and Levi Lelis. Synthesizing libraries of programs with auxiliary functions. Transactions on Machine Learning Research , 2024
2024
-
[23]
Pawan Kumar, Emilien Dupont, Francisco J
Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M. Pawan Kumar, Emilien Dupont, Francisco J. R. Ruiz, Jordan Ellenberg, Pengming Wang, Omar Fawzi, Pushmeet Kohli, and Alhussein Fawzi. Mathematical discoveries from program search with large l...
2023
-
[24]
A reduction of imitation learning and structured prediction to no-regret online learning
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics , pages 627--635. PMLR, 2011
2011
-
[25]
Proximal policy optimization algorithms
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 , 2017
2017 arXiv
-
[26]
Siegelmann and Eduardo D
Hava T. Siegelmann and Eduardo D. Sontag. Analog computation via neural networks. Theoretical Computer Science , 131(2):331--360, 1994
1994
-
[27]
Siegelmann and Eduardo D
Hava T. Siegelmann and Eduardo D. Sontag. On the computational power of neural nets. Journal of Computer and System Sciences , 50(1):132--150, 1995
1995
-
[28]
Jasper Snoek, Hugo Larochelle, and Ryan P. Adams. Practical bayesian optimization of machine learning algorithms. In Advances in Neural Information Processing Systems , volume 25, pages 2951--2959, 2012
2012
-
[29]
Dweep Trivedi, Jesse Zhang, Shao - Hua Sun, and Joseph J. Lim. Learning to synthesize programs as interpretable and generalizable policies. In Advances in Neural Information Processing Systems , pages 25146--25163, 2021
2021
-
[30]
Deshmukh, Sela Mador-Haim, Milo M.K
Abhishek Udupa, Arun Raghavan, Jyotirmoy V. Deshmukh, Sela Mador-Haim, Milo M.K. Martin, and Rajeev Alur. Transit: Specifying protocols with concolic snippets. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation , pages 287--296. ACM, 2013
2013
-
[31]
Programmatically interpretable reinforcement learning
Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri. Programmatically interpretable reinforcement learning. In Proceedings of the International Conference on Machine Learning , volume 80, pages 5045--5054. PMLR, 2018
2018
-
[32]
Imitation-projected programmatic reinforcement learning
Abhinav Verma, Hoang Le, Yisong Yue, and Swarat Chaudhuri. Imitation-projected programmatic reinforcement learning. Advances in Neural Information Processing Systems , 32, 2019
2019
-
[33]
On the practical computational power of finite precision rnns for language recognition
Gail Weiss, Yoav Goldberg, and Eran Yahav. On the practical computational power of finite precision rnns for language recognition. In Proceedings of the Annual Meeting of the Association for Computational Linguistics , pages 740--745. Association for Computational Linguistics, 2018
2018
-
[34]
Torcs, the open racing car simulator
Bernhard Wymann, Eric Espi \'e , Christophe Guionneau, Christos Dimitrakakis, R \'e mi Coulom, and Andrew Sumner. Torcs, the open racing car simulator. Software available at http://torcs. sourceforge. net , 4(6):2, 2000
2000
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.