# Learning to Place Guards by Reinforcement: A Geo-Free Neural Policy for the Vertex-Guard Art Gallery Problem

arXiv: https://arxiv.org/abs/2606.21604 · HTML: https://mlsanity.com/paper/2606.21604/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 33 references that are in the map.
- First posted on arXiv 19 Jun 2026.

## Builds on (most cited first, 12 of 12)

- [Understanding intermediate layers using linear classifier probes](https://mlsanity.com/paper/1610.01644/) (2016)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Probing Classifiers: Promises, Shortcomings, and Advances](https://mlsanity.com/paper/2102.12452/) (2021)
- [Designing and Interpreting Probes with Control Tasks](https://mlsanity.com/paper/1909.03368/) (2019)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Deep Reinforcement Learning for Multi-objective Optimization](https://mlsanity.com/paper/1906.02386/) (2019)
- [Preference Optimization for Combinatorial Optimization Problems](https://mlsanity.com/paper/2505.08735/) (2025)
- [A Reinforcement Learning Approach to the View Planning Problem](https://mlsanity.com/paper/1610.06204/) (2016)
- [Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods](https://mlsanity.com/paper/2310.05309/) (2023)
- [Pareto Frontier Approximation Network (PA-Net) to Solve Bi-objective TSP](https://mlsanity.com/paper/2203.01298/) (2022)

## Abstract (arXiv)

Neural combinatorial optimization (NCO) has shown that policies trained by reinforcement can construct strong solutions to NP-hard problems directly from raw instances. What such a policy actually learns, as opposed to what its decoder expresses, remains much less clear. We study this distinction on the vertex-guard Art Gallery Problem, the NP-hard task of choosing polygon vertices from which to observe an entire region. A pointer-network policy is trained from a coverage-aware reward over its own rollouts under the constraint we call geo-free inference: at test time it sees only vertex coordinates, with no visibility computation and no geometric oracle. The policy places guards economically but leaves a tail of under-covered polygons that widens far beyond the training range. To locate the cause, we freeze the trained encoder and read its embeddings with a small single-shot classifier, still geo-free at inference. The classifier closes most of the feasibility gap, in and out of distribution and at up to roughly five times the training range, cutting under-covered polygons by about an order of magnitude at an explicitly reported cost in guard count. We read this as evidence that the reinforcement-trained representation already encodes the geometry required for feasibility, and that residual failures reflect decoder calibration rather than missing knowledge. Probing a frozen encoder thus offers a practical way to ask what a neural combinatorial solver has internalized.