用强化学习系统求解图论极值问题，支持多种图结构。
RLGT: A reinforcement learning framework for extremal graph theory
- 将图论极值问题转化为强化学习任务，统一处理各类图结构。
- 成功推翻多个图谱半径不等式，改进若干拉姆齐数下界。
- 框架支持有向、带环、多色边图，适合未来图论研究者使用。
强化学习（RL）是一种关注模型自主学习最优决策策略的机器学习分支。近期，Wagner展示了深度交叉熵强化学习方法如何通过将极值图论问题重新表述为组合优化问题来解决。此后，众多研究者致力于改进和扩展Wagner提出的框架，构建了专门针对图论的强化学习环境，并利用强化学习解决了若干极值图论问题。例如，推翻了关于图拉普拉斯谱半径的多个不等式，获得了某些拉姆齐数的新下界，并对禁止三角形和四边形环的图论极值问题（即塔兰型问题）作出贡献。本文提出一种名为RLGT的新型强化学习框架，系统化了先前工作，支持无向与有向图、带或不带自环、任意数量边颜色的图结构。该框架高效表示图数据，旨在通过优化计算性能和清晰模块化设计，促进未来基于强化学习的极值图论研究。
原文摘要 · Abstract (English)
Reinforcement learning (RL) is a subfield of machine learning that focuses on developing models that can autonomously learn optimal decision-making strategies over time. In a recent pioneering paper, Wagner demonstrated how the Deep Cross-Entropy RL method can be applied to tackle various problems from extremal graph theory by reformulating them as combinatorial optimization problems. Subsequently, many researchers became interested in refining and extending the framework introduced by Wagner, thereby creating various RL environments specialized for graph theory. Moreover, a number of problems from extremal graph theory were solved through the use of RL. In particular, several inequalities concerning the Laplacian spectral radius of graphs were refuted, new lower bounds were obtained for certain Ramsey numbers, and contributions were made to the Turán-type extremal problem in which the forbidden structures are cycles of length three and four. Here, we present Reinforcement Learning for Graph Theory (RLGT), a novel RL framework that systematizes the previous work and provides support for both undirected and directed graphs, with or without loops, and with an arbitrary number of edge colors. The framework efficiently represents graphs and aims to facilitate future RL-based research in extremal graph theory through optimized computational performance and a clean and modular design.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。