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

Let $P\subset\mathbb{R}^{2}$ denote a simple polygonal region (the closed set consisting of its interior and boundary), with $n$ vertices at coordinates $x_{1},\dots,x_{n}\in\mathbb{R}^{2}$ and vertex index set $V(P)=\{1,\dots,n\}$. For two points $p,q\in P$ we say that $p$ sees $q$ when the closed segment between them stays inside the polygon, $\overline{pq}\subseteq P$. Guards are placed at vertices: for a vertex-guard set $S\subseteq V(P)$, the visibility region and area-normalized coverage are

The vertex-guard Art Gallery Problem (AGPVG) asks for the smallest vertex-guard set that covers the whole polygon. We define the vertex-guard optimum directly:

Restricting guards to $V(P)$ reduces placement to a finite discrete choice over $n$ vertices — the natural action space for a pointer-network policy [32, 3, 20, 21] — while retaining the full NP-hardness and non-uniform visibility structure of the problem.

Note that equation (2) is a constrained single-objective problem — minimize the guard count subject to the hard constraint $\mathrm{Cov}_{P}(S)=1$ — and is a discrete set-cover instance, where coverage is the submodular union of per-guard visibility regions. This is what separates it from the routing problems on which neural combinatorial solvers are usually studied, where any permutation is feasible and only a single scalar cost is minimized. A learner denied a visibility oracle at inference (the geo-free constraint, Section 2.3) cannot certify the coverage constraint while placing guards; it must instead trade coverage against guard count, so the single constrained objective becomes a two-axis operating curve.

We will say that an inference procedure is geo-free if its inputs at test time are limited to the polygon’s vertex coordinates and learned features derived from them — no polygon visibility matrix, no CGAL-computed visibility regions, no per-vertex area or visibility-fraction feature. Geo-free inference does not preclude using exact visibility during evaluation (to report coverage after the fact) or during training (to compute rewards, gate trajectories, or build supervised targets); it restricts what the model reads at the moment it places guards. A solver allowed to query a visibility oracle at every decision step — as classical local search and active-search decoding both do — can in principle simulate greedy or local search, and a measurement of what such a solver has learned would be conflated with a measurement of what its oracle can compute. The geo-free constraint isolates the first question from the second, which is what makes “no explicit geometric knowledge” a measurable property.

The policy learns to decrease the cardinality but leaves a feasibility tail (Section 6.1). We first verified that this tail is reachable: running a local-search editor (add/remove/swap) on the policy’s own greedy seed restores feasibility on every sub-feasibility in-distribution polygon while reducing the guard count (the LS on policy seed row of Table 3). We treat this as a sanity check that settles the diagnosis — the missing feasibility is a handful of local edits away from the seed, so it reflects decoder calibration rather than absent geometry — and that, as a by-product, yields a concrete target set $S^{\star}_{\mathrm{LS}}$. The open question is then whether that refinement can be learned from the frozen encoder, geo-free. A learned iterative editor over the seed cannot: it does not close the tail in any coverage-preserving regime (Section 6.4), because error accumulation, stop-time miscalibration, and train/inference drift make a rollout-based post-processor unreliable here, contrary to fine-tuning arguments of the policy in [29]. We therefore probe what the policy has learned with a single-shot, rollout-free classifier that recovers the feasibility decision the decoder failed to make. Its inputs are geo-free — the frozen encoder embedding, the vertex coordinates, and the policy’s seed indicator — with no visibility object at inference. Having no rollout and no stop decision, a single pass has nothing to drift and nothing to miscalibrate. We call it the SetPredictor and present it primarily as a representation diagnostic; the threshold sweep in Section 6 makes the diagnostic concrete, but the operating-curve framing is a side-effect of the measurement, not a deployment recipe.

For polygon $P$ with vertex coordinates $x_{1},\dots,x_{n}$, the input feature for vertex $i$ is

that is, the frozen $d$-dimensional encoder embedding $h_{i}$ from the PO/BT policy, the 2D coordinates $x_{i}$, and a single binary indicator for whether vertex $i$ is selected by the policy’s greedy-decoded seed $\pi_{\mathrm{seed}}$.

The architecture is a small Transformer encoder (parameters $\phi$) over the $n$ vertex tokens with a sigmoid output head per token (sizes given in Section 5.2). The features $z_{i}$ are linearly projected to width $d$ and passed through $L$ pre-norm self-attention blocks — each with $H$-head self-attention at width $d$, a GELU feed-forward sublayer of expansion factor $f$, and residual connections — followed by a final layer normalization; we write $v_{i}$ for the resulting per-vertex hidden state. This $v_{i}$ is the SetPredictor’s own encoding of vertex $i$, and is distinct from the frozen policy embedding $h_{i}$, which enters only as part of the input feature $z_{i}$ in Eq. (7). From the $(v_{1},\dots,v_{n})$ we build two context vectors by mean-pooling: a seed context $c_{\mathrm{seed}}=\tfrac{1}{|S(\pi_{\mathrm{seed}})|}\sum_{i\in S(\pi_{\mathrm{seed}})}v_{i}$, averaged over the vertices the policy placed in its seed, and a global context $c_{\mathrm{glob}}=\tfrac{1}{n}\sum_{i=1}^{n}v_{i}$, averaged over all vertices of the polygon. Both are single vectors shared across vertices. Each per-vertex prediction concatenates the vertex’s own $v_{i}$ with these two context vectors and passes the result through a 2-layer GELU MLP head ($3d\to d\to 1$):

The output $\hat{p}_{i}\in[0,1]$ is interpreted as the probability that vertex $i$ should be in the final guard set. Thresholding at $t\in(0,1)$ yields the guard set

We draw polygons primarily from the Art Gallery Problem with Vertex Guards (AGPVG) instance library of Couto, de Rezende, and de Souza [9, 10], which collects several polygon families — random orthogonal (including large-area fat and small-area min variants), random simple (randsimple), random von Koch (randvon), complete von Koch (vonkoch), and boundary-simple (simple) — over vertex counts $n$ ranging from $8$ to $2{,}500$. The library distributes vertex-guard optimal solutions for its instances, which we use directly as $\mathrm{OPT}$.

We supplement the library with $313$ additional random simple polygons (random class, $n\in\{20,40,\dots,600\}$, $30$ instances per size) to increase training density for random simple polygons in the in-distribution range; these share the same rational-coordinate format, and their vertex-guard optima were computed by solving the vertex-guard set-cover integer program. The splits we work with are listed in Table 2.¹¹1The $70/30$ dev$/$test partition uses a seeded random shuffle (seed $1234$) rather than an alphabetical-name split due to instance naming

The PO/BT policy is the existing lstm_bt checkpoint: trained once from a single seed ($1234$) for $200$ epochs, with $R=8$ rollouts per polygon, Bradley–Terry temperature $\alpha=0.05$, and reward weights $\lambda=1.0$ and $\rho=3.0$ at the gate $\tau=0.99$ (Eq. (3)); all PO coverage rewards are computed from discrete-visibility sampling ($M=500$), after which the encoder is frozen.

Inputs: a polygon’s vertices are consumed by the LSTM in the source-library file order — no canonical start vertex and no orientation (clockwise/counter-clockwise) are imposed — and the coordinates are min–max normalized per polygon to $[0,1]^{2}$ before the encoder. The normalization makes the policy invariant to translation and to axis-aligned rescaling by construction; it is not invariant to rotation or to a cyclic re-indexing of the vertices, whose empirical effect we quantify in Section 8.

Targets: for each training polygon we obtain $S^{\star}_{\mathrm{LS}}(P)$ by running local search on the policy’s seed under a coverage gate $\tau=0.99$ against a discrete-visibility reference (Section 4.1); exact coverage-area computation is reserved for evaluation. These targets are not produced by a policy-independent classical solver: they come from a best-improvement editor (add/remove/swap) initialized at the policy’s own greedy-decoded seed and scored on discretized visibility. We refer to this policy-seeded refinement as “LS” throughout; it is the same edit family whose learned counterpart we analyze in Section 6.4, here run to its best-improvement optimum as an oracle teacher rather than learned.

Sizes: the model dimensions of Section 4.2 take the following values:

Optimization: weighted BCE (Eq. (10)) with positive-class weight $w_{+}\approx 5.66$ (the empirical non-guard-to-guard ratio on train), $60$ epochs, batch size $32$, learning rate $3\times 10^{-4}$, AdamW [25]. Both the headline probe and the no-encoder ablation are four independent runs with seeds $\{1234,11,22,33\}$ (reported as mean $\pm$ std); all figures display seed $1234$. Checkpoints are selected on dev; test, ood, and ood-large are touched only after training and threshold selection are complete.

For each polygon we greedy-decode the policy’s $\mathrm{EOS}$-truncated seed and evaluate it with CGAL exact polygon visibility [31]; separately, we run one SetPredictor pass, threshold at $t$ to obtain $S(t)$, and evaluate $S(t)$ with CGAL. Let $N$ be the partition size. We report mean coverage $\frac{1}{N}\sum\mathrm{Cov}_{P}(S)$, the normalized guard count $|S|/n$, and the approximation ratio $|S|/\mathrm{OPT}$ against the vertex-guard optimum. Because the mean hides the tail, we also report the per-polygon counts $\#\{\mathrm{Cov}_{P}(S)\geq c\}$ for $c\in\{0.95,0.99,0.999,1\}$ and the worst case $\min_{P}\mathrm{Cov}_{P}(S)$; we call $\mathrm{Cov}_{P}(S)\geq 0.95$ the feasibility threshold and report the feasibility rate $\#\{\mathrm{Cov}_{P}(S)\geq 0.95\}/N$ with Wilson $95\%$ confidence intervals. Where we compare the policy’s and the probe’s feasibility rates on the same polygons, we test the paired per-polygon outcomes with an exact McNemar test. The reporting threshold $c$ is distinct from the training-time gate $\tau=0.99$ of Eq. (3). As noted in Section 5.1, $\mathrm{OPT}$ values are taken from the vertex-guard optimal solutions distributed with the AGPVG library (for library instances) or computed via ILP (for the random class). For $79$ of the ood-large polygons (all with $n\geq 800$) no optimum is available — most are library instances whose distributed solutions do not cover them (they are open at the source), and for the remainder our ILP did not terminate within budget. Restricting $|S|/\mathrm{OPT}$ to the $206$ solved instances would bias the ratio toward the easier $600$–$700$-vertex polygons, so on ood-large we report coverage and the normalized guard count $|S|/n$ over all $285$ polygons but no approximation ratio.

The geo-free policy on its own (Table 3, seed row) places guards at near-classical cardinality — its mean $|S|/n$ ($0.166$) is close to classical greedy ($0.152$), at $|S|/\mathrm{OPT}\approx 1.09$ — and clears the feasibility line on $293$ of the $362$ test polygons ($81\%$, Wilson $95\%$ CI: $0.766$, $0.847$). The LS oracle (bottom row) achieves $362/362$ feasibility at lower cardinality ($|S|/n=0.137$, $|S|/\mathrm{OPT}=0.885$), but is not geo-free: it reads discretized visibility at every add/remove/swap step and serves here only as the probe’s training target, not as a geo-free competitor. The results show that vertex-guard placement is learnable, to a degree, by a method that never reads an explicit visibility object at inference. The remaining $69$ polygons ($19\%$) fall below the feasibility line under the policy alone; this tail is the paper’s central motivating observation (the distribution is Section 6.2), and the method gives no feasibility guarantee on its own. Figure 2 shows the seed, the seed plus probe at $t=0.20$, and the optimum side by side for an in-distribution and an out-of-distribution polygon.

The policy’s mean coverage hides a bimodal distribution (Table 4): it reaches full coverage on only a handful of polygons and trails a long left tail down to a worst polygon at $0.830$, while the SetPredictor at $t=0.20$ eliminates that tail and lifts the bulk above $0.99$. On the displayed seed the probe clears all $69$ of the policy’s sub-feasibility polygons and introduces no new failures ($69\to 0$ below $0.95$; paired exact McNemar test, $p\approx 3\times 10^{-21}$); the same paired test is applied at OOD scale in Section 6.3. The shift holds under the strict full-coverage requirement that defines the problem ($\mathrm{Cov}_{P}(S)=1$): the probe covers $240$ of the $362$ polygons exactly against the policy’s $3$ (Table 4), so the gain is not an artifact of reading feasibility at the $0.95$ gate.

The next question we ask is whether closing that tail is the encoder’s doing or coordinates alone suffice. We isolate the encoder’s contribution by retraining the probe with the frozen embedding $h_{i}$ masked to zero on every forward pass — architecture, parameter count, optimizer, and training schedule identical (Section 5.2). The $0.95$ feasibility gate does not reveal the encoder’s contribution, as both probes saturate there ($362/362$, Table 3) and the headline mean coverage is likewise nearly identical. The encoder’s contribution lives in the tail. At the stricter $0.99$ gate of Table 4, on the displayed seed the full probe leaves $4$ polygons below against $56$ for the no-encoder ablation, a fourteen-fold difference, and lifts the worst polygon from $0.952$ to $0.977$ (across the four seeds the mean count below $0.99$ is $\approx 11$ for the full probe and $\approx 29$ for the no-encoder, of which the displayed seed’s $56$ is the worst — Table 5). The gap becomes qualitative out of distribution (Section 6.3). This is the direct measurement behind C1 — the frozen encoder carries geometric structure that raw coordinates do not reproduce, even with the decoder’s full parameter budget.

The no-encoder ablation removes the encoder but keeps the policy’s seed indicator among the probe’s inputs, so the recovered feasibility could in principle be credited to the decoder’s guard set rather than to the encoder. We therefore complete the $2\times 2$ design, masking the seed indicator as well (Table 5, four-seed mean $\pm$ std at $t=0.20$). The two axes must be read together, because at a fixed threshold the four conditions trade coverage against guard count differently. Masking the seed alone barely moves the probe: the encoder-only probe nearly matches the full probe both in the tail ($17.2\pm 2.4$ versus $11.0\pm 8.7$ polygons below $0.99$) and in cost ($|S|/\mathrm{OPT}$ $2.42$ versus $2.56$). Masking the encoder alone is markedly worse on the tail ($29.0\pm 18.0$ below $0.99$ at $|S|/\mathrm{OPT}$ $3.11$). The coords-only probe (neither input) appears to have the smallest tail of all, but this is misleading: its threshold barely functions — it selects $0.72$, $0.70$, and $0.67$ of all vertices at $t=0.20,0.25,0.30$ — so it holds coverage by flooding guards rather than selecting them, never entering the guard-count regime the other probes operate in ($|S|/\mathrm{OPT}=4.64$, against $2.4$–$2.6$). Reading the axes together, the seed contributes little, whereas the encoder is what makes economical feasibility reachable at all: it is the representation, not the decoder’s seed, that lets the probe place few guards and still cover.

Since the SetPredictor is itself a small Transformer, one might worry that it computes the geometry and the encoder merely passes coordinates through. To rule this out we strip the probe of all capacity: a plain linear classifier (without any hidden layers or attention) reading only the frozen per-vertex features, asked to separate guard from non-guard vertices. It already reaches $\mathrm{ROC\text{-}AUC}\approx 0.84$, a measure of how reliably the rule ranks a guard above a non-guard ($0.5$ is chance, $1.0$ perfect).²²2$L_{2}$-regularized logistic regression under $5$-fold polygon-grouped cross-validation over $200$ polygons / $12{,}424$ vertices: $\mathrm{ROC\text{-}AUC}=0.843\pm 0.009$ and $\mathrm{PR\text{-}AUC}=0.582\pm 0.027$ (mean $\pm$ std across folds) against a $0.16$ positive-class prior. A linear readout cannot be credited with computing geometry itself [1, 16], so the guard-relevant structure must already be linearly accessible in the frozen embedding — the encoder, not the probe, carries it. Scored by such a linear rule, guard vertices pile up at higher scores than non-guards, with only modest overlap, as visible in Figure 3.

Closing the tail has a price, with the threshold $t$ as the knob: the approximation ratio rises as $t$ falls (Table 6), reaching $\approx\!2.6\times$ optimum at the headline threshold against $\approx 1.1$ for the policy alone. Figure 4 gives the full picture in and out of distribution: the coverage CDF sits to the right of the policy at every threshold, while the $|S|/n$ and $|S|/\mathrm{OPT}$ box plots show the matching cost. We report the trade-off rather than fix one operating point.

The next test of the representation is the ood split, a larger held-out set that spans the training size range and extends well beyond it, reaching $n=1000$ — about five times the largest training polygon. Table 7 reports it. The policy alone drops to mean coverage $0.957$, with $303/2081$ polygons below the feasibility line ($85\%$ feasible). The probe at $t=0.20$ (four-seed mean) cuts that to $16.8\pm 12.2$ ($99\%$ feasible) at mean coverage $0.995$ — roughly an order-of-magnitude reduction in failures. The improvement is significant for every probe seed individually (per-seed failure counts $3$, $8$, $22$, $34$; exact McNemar test on the paired per-polygon outcomes, $p<1.2\times 10^{-75}$ in all four cases), and the per-seed Wilson $95\%$ intervals for the probe’s feasibility rate all lie above $0.977$. The no-encoder ablation leaves $44\pm 23$ below feasibility (four-seed mean) at mean coverage $0.985$ — about $2.6\times$ the full probe’s failures (Table 7), so out of distribution the encoder’s contribution is qualitative, not the saturated tie it is in distribution. This is the evidence behind C2: a small classifier over the frozen embeddings recovers feasibility across this held-out set. The gain is not an artifact of the in-distribution-size majority of ood: on the genuinely larger-than-training polygons alone ($n>198$, $885$ instances) the policy is feasible on $85\%$ and the probe on $98.7\%$ across four seeds ($100\%$ on the displayed seed). The reduction is robust across seeds, though the residual failure count is seed-dependent (the per-seed counts above), so at-scale generalization is partially seed-dependent. Figure 4 (middle and bottom rows) shows the matching coverage and cost distributions for ood and ood-large.