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

Hugging Face Daily Papers Papers
reinforcement-learning quadrilateral-mesh optimization mesh-generation deep-learning behavior-cloning computational-geometry

Summary

This paper presents a reinforcement learning agent trained to generate provably optimal quadrilateral block decompositions for planar domains, demonstrating superior performance over existing tools like Gmsh in terms of usability and optimality.

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.
Original Article
View Cached Full Text

Cached at: 09/29/26, 12:10 PM

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

Source: https://huggingface.co/papers/2609.32146

Abstract

Aquadrilateralblockdecompositionofaplanardomainisjudgedbywhetheritiscomplete,whetheritselementsarewellshaped,andhowmanyofitsverticesareirregular.Thelasthasaprovablefloor:thediscreteGauss-Bonnetidentityenforcesalowerboundonthetotalvertexirregularityofanyall-quadrilateralmeshofagivendomainpurelybasedonitstopologyandcornerangles.Wetrainareinforcementlearningagenttobuilddecompositionsthatreachthisbound,whichwecallpar.Itactsdirectlyonthemesh’shalf-edgedatastructurethroughlocaledits,withapolicynetworkwhoseconvolutionsfollowthemesh’sownconnectivity,soitappliesunchangedtodomainslargerthananyseenintraining.Therewardtargetsthefloordirectly,anditissparse:randomplayreachesitonnodomainwithmorethaneightsides.Weovercomethisexplorationbarrierviabehaviourcloningonoptimalmeshesthataretrivialtoconstruct,walkedbackwardintodemonstrations,beforetrainingitwithPPO.On96held-outdomainstheagentproducesanall-quadrilateralmeshoneveryone,ausableoneon95.7onaverage,andaprovablyoptimaloneon90;Gmsh’sstrongestconfigurationatthesameelementcountcompletes51,isusableon38andoptimalonnone,andevenatthreetofourteentimestheelementsneverproducesamoreregularmesh.On64domainstwicethetrainingsizetheagentcompletesall,isusableon62,andkeepsamedianexcessoverparbelowoneagainstGmsh’s39atthesameelementcount.

View arXiv pageView PDFProject pageGitHubAdd to collection

Get this paper in your agent:

hf papers read 2609\.32146

Don’t have the latest CLI?curl \-LsSf https://hf\.co/cli/install\.sh \| bash

Models citing this paper0

No model linking this paper

Cite arxiv.org/abs/2609.32146 in a model README.md to link it from this page.

Datasets citing this paper0

No dataset linking this paper

Cite arxiv.org/abs/2609.32146 in a dataset README.md to link it from this page.

Spaces citing this paper0

No Space linking this paper

Cite arxiv.org/abs/2609.32146 in a Space README.md to link it from this page.

Collections including this paper0

No Collection including this paper

Add this paper to acollectionto link it from this page.

Similar Articles

Discovering Lattice Reduction Strategies via Self-Play

arXiv cs.LG

This paper presents Delta-Star, a deep reinforcement learning approach using AlphaZero-style self-play to discover superior lattice reduction strategies by interacting with the primitive actions of the LLL algorithm. The learned policy generalizes to higher dimensions and unseen moduli without retraining.

Reinforcement Learning for Code Optimization

Hugging Face Daily Papers

This paper addresses challenges in using reinforcement learning for code optimization by proposing three stages: improved testing with DMC-Optim, converting execution time into reward via correctness-speed composition and an offline simulator, and adapting GRPO for noisy timing rewards. The method achieves substantial improvements on code optimization benchmarks.