# Playing to Par: Reinforcement Learning for Provably Optimal Quadrilateral Block Decompositions

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

## 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.

## Placed in

- Deep reinforcement learning methods / [RL with diffusion and flow models](https://mlsanity.com/deeprl/rl-with-diffusion-and-flow-models/)

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Reverse Curriculum Generation for Reinforcement Learning](https://mlsanity.com/paper/1707.05300/) (2017)
- [Backplay: "Man muss immer umkehren"](https://mlsanity.com/paper/1807.06919/) (2018)
- [Deep Reinforcement Learning for Adaptive Mesh Refinement](https://mlsanity.com/paper/2209.12351/) (2022)
- [Reinforcement learning for automatic quadrilateral mesh generation: a soft actor-critic approach](https://mlsanity.com/paper/2203.11203/) (2022)
- [Solving the Rubik's Cube Without Human Knowledge](https://mlsanity.com/paper/1805.07470/) (2018)
- [SRL-Assisted AFM: Generating Planar Unstructured Quadrilateral Meshes with Supervised and Reinforcement Learning-Assisted Advancing Front Method](https://mlsanity.com/paper/2305.00540/) (2023)
- [Multi-Agent Reinforcement Learning for Adaptive Mesh Refinement](https://mlsanity.com/paper/2211.00801/) (2022)
- [Learning topological operations on meshes with application to block decomposition of polygons](https://mlsanity.com/paper/2309.06484/) (2023)
- [Optimization of a Triangular Delaunay Mesh Generator using Reinforcement Learning](https://mlsanity.com/paper/2504.03610/) (2025)
- [Quasi-structured quadrilateral meshing in Gmsh -- a robust pipeline for complex CAD models](https://mlsanity.com/paper/2103.04652/) (2021)
- [Dmsh: A Multi-Agent Reinforcement Learning Framework for All-Quad Mesh Generation](https://mlsanity.com/paper/2606.10601/) (2026)

## 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.