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

Playing to Par. Reinforcement Learning for Provably Optimal Quadrilateral Block Decompositions. By Arjun Narayanan and one other, from U C Berkeley. Published on the twenty-sixth of September. Its code repository is worked out: about one hundred and eighty source files, with a readme and a licence.

Splitting a flat region into quadrilateral blocks is judged on three counts. Is the decomposition complete? Are its elements well shaped? And how many of its vertices are irregular? The third has a floor you can prove. The discrete Gauss-Bonnet identity sets a lower bound on the total vertex irregularity of any all-quadrilateral mesh of a given domain, and that bound depends only on the domain's topology and its corner angles. It holds before a single element is placed. The authors call this bound par, borrowing from golf, where par is the score a hole is set to be played in. Knowing the floor exists is not the same as reaching it, and the question is whether a mesh can be built that actually gets there, while also staying complete and well shaped.

The approach is to train a reinforcement learning agent whose target is par itself. The agent works directly on the mesh's half-edge data structure, making local edits. Its policy network uses convolutions that follow the mesh's own connectivity, and because of that, the same trained network applies unchanged to domains larger than any it saw in training.

The reward points straight at the floor, and that makes it sparse. Random play never reaches par on any domain with more than eight sides, so an agent exploring on its own would rarely see a reward at all. The authors get around this exploration barrier with a trick of construction. Some optimal meshes are trivial to build, so they build them, then walk them backward into demonstrations. The agent first learns from those by behaviour cloning, and only then trains with PPO. The demonstrations give it a starting point from which the sparse reward can actually be found, and reinforcement learning takes over from there.

On ninety-six held-out domains, the agent produces an all-quadrilateral mesh on every one, a usable mesh on ninety-five point seven on average, and a provably optimal mesh on ninety. The comparison is Gmsh in its strongest configuration, at the same element count. It completes fifty-one, is usable on thirty-eight, and reaches optimal on none. Even when Gmsh is allowed three to fourteen times as many elements, it never produces a more regular mesh.

Generalization is the second test. The agent was run on sixty-four domains twice the size of those in training, the case that its connectivity-following network was designed to handle. It completed all of them and was usable on sixty-two. Its median excess over par stayed below one, against thirty-nine for Gmsh at the same element count.

Golf gives the paper its image and also its logic. Par is not an aspiration here but a number fixed in advance by the geometry, so every result can be scored against the best that is possible. The agent reaches that score on ninety of ninety-six held-out domains, and the backward-walked demonstrations are what got it far enough to start learning.