Playing to Par: Reinforcement Learning for Provably Optimal Quadrilateral Block Decompositions
On the map: Deep reinforcement learning methods → RL with diffusion and flow models
Abstract (arXiv)
A quadrilateral block decomposition of a planar domain is judged by whether it is complete, whether its elements are well shaped, and how many of its vertices are irregular. The last has a provable floor: the discrete Gauss-Bonnet identity enforces a lower bound on the total vertex irregularity of any all-quadrilateral mesh of a given domain purely based on its topology and corner angles. We train a reinforcement learning agent to build decompositions that reach this bound, which we call par. It acts directly on the mesh's half-edge data structure through local edits, with a policy network whose convolutions follow the mesh's own connectivity, so it applies unchanged to domains larger than any seen in training. The reward targets the floor directly, and it is sparse: random play reaches it on no domain with more than eight sides. We overcome this exploration barrier via behaviour cloning on optimal meshes that are trivial to construct, walked backward into demonstrations, before training it with PPO. On 96 held-out domains the agent produces an all-quadrilateral mesh on every one, a usable one on 95.7 on average, and a provably optimal one on 90; Gmsh's strongest configuration at the same element count completes 51, is usable on 38 and optimal on none, and even at three to fourteen times the elements never produces a more regular mesh. On 64 domains twice the training size the agent completes all, is usable on 62, and keeps a median excess over par below one against Gmsh's 39 at the same element count.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL with diffusion and flow models, one of 15 directions in Deep reinforcement learning methods. Builds on 12 of its 35 references that are in the map. First posted on arXiv 26 Sep 2026.
Builds on
12 of 35 references.
References · 12
- 2017Proximal Policy Optimization Algorithmscited by 15,215
- 2017Reverse Curriculum Generation for Reinforcement Learningcited by 198
- 2018Backplay: "Man muss immer umkehren"cited by 21
- 2022Deep Reinforcement Learning for Adaptive Mesh Refinementcited by 20
- 2022Reinforcement learning for automatic quadrilateral mesh generation: a soft actor-critic approachcited by 17
- 2018Solving the Rubik's Cube Without Human Knowledgecited by 15
- 2023SRL-Assisted AFM: Generating Planar Unstructured Quadrilateral Meshes with Supervised and Reinforcement Learning-Assisted Advancing Front Methodcited by 8
- 2022Multi-Agent Reinforcement Learning for Adaptive Mesh Refinementcited by 5
- 2023Learning topological operations on meshes with application to block decomposition of polygonscited by 2
- 2025Optimization of a Triangular Delaunay Mesh Generator using Reinforcement Learningcited by 2
- 2021Quasi-structured quadrilateral meshing in Gmsh -- a robust pipeline for complex CAD modelscited by 1
- 2026Dmsh: A Multi-Agent Reinforcement Learning Framework for All-Quad Mesh Generationcited by 1
Built on by
Not cited yet.
Similar, not cited
Close in wording, no citation either way
- 2026Mesh-RL: Coupled subgrid reinforcement learning
- 2026Geometry-Aware Reinforcement Learning for 2D Irregular Nesting
- 2026TriSearch: Learning to Optimize Triangulations via Bistellar Flips
- 2026RLVR landscapes for iterated multiplications can be benign: Insights from spin-glass theory
- 2026Beyond Euclidean Clipping: Overcoming Exploration Collapse in LLM RL via Riemannian Isometric Policy Optimization
- 2026Anchored Policy Optimization: Mitigating Exploration Collapse Via Support-Constrained Rectification
- 2021Learning from Guided Play: A Scheduled Hierarchical Approach for Improving Exploration in Adversarial Imitation Learning
- 2026Beyond Heuristics: Learnable Density Control for 3D Gaussian Splatting