Technische Samenvatting: Het Twee-Heuvel Probleem in Wiskundige Reinforcement Learning

Probleemdefinitie

Het artikel behandelt de uitdaging van het toepassen van Reinforcement Learning (RL) op de Andrews–Curtis (AC) vermoeden, een prominent openstaand probleem in de combinatorische groepentheorie. Het vermoeden stelt dat elke gebalanceerde presentatie van de triviale groep getransformeerd kan worden naar de triviale presentatie $\langle x, y \mid x, y \rangle$ via een eindige sequentie van specifieke operaties (AC1: inversie, AC2: conjunctie/concatenatie, AC3: cyclische permutatie).

De kern van de moeilijkheid ligt in de aard van de zoekruimte:

1. Enorme zoekruimtes: De graaf van mogelijke presentaties is oneindig.
2. Spraarzame beloningen (Sparse Rewards): Een agent ontvangt pas een beloning bij volledige trivialisering; er zijn geen signalen van tussentijdig falen of indicatoren van gedeprogressie.
3. Het "Twee-Heuvel" Fenomeen: De auteurs identificeren een kritieke structurele barrière waarbij probleeminstanties bimodaal verdeeld zijn. De meeste presentaties zijn ofwel triviaal oplosbaar (via eenvoudige greedische lengte-reductie) of effectief onmogelijk (vereisen paden die tijdelijk de lengte vergroten, wat standaard heuristieken afwijzen). Cruciaal is dat er een schaarste is aan "moeilijke-maar-oplosbare" instanties, wat een "vallei" van data creëert die effectief curriculum leren verhindert.

Methodologie

Om de moeilijkheidsgraad-kloof te overbruggen en de Twee-Heuvel distributie te overwinnen, stellen de auteurs een drieledige aanpak voor die algoritmische innovaties, architecturaal ontwerp en gerichte datageneratie combineert.

1. Actieruimte: Substitutie Supermoves

In plaats van te opereren op primitieve AC-moves, introduceren de auteurs substitutie-moves als de primaire actieruimte.

• Mechanisme: Een substitutie behandelt relatoren als cyclische sequenties en voegt de ene in de andere in op een punt waar annulering plaatsvindt. Dit combineert meerdere primitieve moves (AC1, AC2, AC3) tot een enkele actie.
• Voordeel: Dit stelt de agent in staat om grotere, meer betekenisvolle stappen te zetten door de AC-graaf en reduceert de effectieve toestandsruimte aanzienlijk door cyclische permutaties te negeren.
• Theoretische basis: Ivanov (2018) bewees dat als het Andrews–Curtis vermoeden waar is, substituties volstaan om alle AC-transformaties te realiseren.

2. Architectuur: De Dual-Ring Transformer

Om de grote, gestructureerde actieruimte van substituties aan te kunnen en de wiskundige symmetrieën van het probleem te respecteren, hebben de auteurs de Dual-Ring Transformer ontwikkeld.

• Cyclische Symmetrie: In tegenstelling tot standaard Transformers die absolute positionele codering gebruiken, behandelt deze architectuur relatoren als cyclische ringen. Het maakt gebruik van cyclische relatieve positionele coderingen waarbij de aandachtsscore afhangt van de cyclische afstand $d(i, j) = (i - j) \mod L$.
• Cross-Attention: Het netwerk verwerkt beide relatoren parallel en gebruikt cross-attention om overeenkomende substrings tussen $r_1$ en $r_2$ te identificeren, wat cruciaal is voor het bepalen van geldige substitutie-moves.
• Policy Head: De output is een distributie over geldige substitutie-moves, gemaskeerd om te garanderen dat alleen acties die leiden tot annulering (waar $r_1[i] = \pm r_2[j]$) een niet-nul kans krijgen.

3. Datageneratie: Het Vullen van de Vallei

In het besef dat standaard "scrambling" strategieën falen bij het genereren van moeilijke-maar-oplosbare instanties, maken de auteurs gebruik van twee nieuwe datageneratietechnieken:

• Automorfisme Perturbatie: Het toepassen van automorfismen op bekende triviale presentaties (bijv. $AK(2)$) transformeert deze naar presentaties met drastisch andere padkarakteristieken. Terwijl de originele presentatie eenvoudig kan zijn, kan de automorfische afbeelding een pad vereisen dat de lengte vergroot, waardoor het effectief van de "gemakkelijke" heuvel naar de "vallei" beweegt.
• Generator-Solver Game: Er wordt een asymmetrisch tweespelersspel geformuleerd waarbij een Generator (een PPO-agent) sequenties van automorfismen toepast om de moeilijkheid van de presentatie te verhogen, terwijl een Solver (greedy search) probeert deze te trivialiseren. De Generator wordt beloond voor het creëren van instanties die de Solver uitdagen, specifiek gericht op de regio van intermediaire moeilijkheid.
• Resulterende Datasets: Dit proces levert de datasets AC-19 (125.192 korte AC-triviale presentaties, lengte $\le 19$) en AC-1M (1.136.154 moeilijke AC-triviale presentaties, lengte $\le 30$) op, de eerste grootschalige publieke datasets van dit type.

Belangrijkste Resultaten

De auteurs evalueren hun methoden op de 1.190-presentatie Miller–Schupp benchmark dataset.

• Prestatieverbetering: De combinatie van substitutie supermoves en de Dual-Ring Transformer (PPO-Sub-DRT) lost 610 presentaties op (gemiddelde over 5 seeds), een significante stijging ten opzichte van de vorige beste RL-baseline van 457 (PPO-AC-ResNet).
• Data Impact: Het integreren van de gegenereerde AC-1M dataset verbetert de prestaties verder, wat aantoont dat gerichte datageneratie effectief helpt bij het leren van algemene strategieën voor moeilijke presentaties.
• Pad-efficiëntie: Hoewel Greedy Search (GS) met substituties meer instanties oplost (640) vanwege exhaustieve exploratie, ontdekt de PPO-agent substantieel kortere oplossingspaden, met name bij moeilijkere presentaties. PPO identificeert lengte-verhogende omwegen die greedy heuristieken afwijzen, wat bewijst dat de agent niet-voor-de-hand-liggende wiskundige structuren leert.
• Architecturale Superioriteit: De Dual-Ring Transformer (gebruikmakend van cyclische relatieve coderingen) presteert ongeveer 25 opgeloste presentaties beter dan een variant met canonical form preprocessing met absolute coderingen, wat het belang van het leren van symmetrie-bewuste representaties onderstreept.
• Wiskundige Vooruitgang: De auteurs hebben succesvol meer dan 100 voorheen onopgeloste presentaties uit de Miller–Schupp familie getrivialiseerd. Ze hebben de resterende 550 onopgeloste voorbeelden teruggebracht tot 261 onderscheidende AC-equivalentieklassen, wat een concreet checklist biedt voor toekomstig onderzoek.

Betekenis en Claims

Het artikel claimt dat vooruitgang op het gebied van het Andrews–Curtis vermoeden vereist dat men de inherente moeilijkheidsstructuur van het probleem begrijpt, in plaats van enkel de rekenkracht (compute) op te schalen.

• Het Twee-Heuvel Inzicht: De identificatie van de bimodale moeilijkheidsverdeling verklaart waarom eerdere benaderingen moeite hadden en motiveert de noodzaak om algoritmische verbeteringen te combineren met gerichte datageneratie.
• RL in omgevingen met spraarzame beloningen: Het werk demonstreert dat RL kan slagen in extreem spraarzame beloningsomgevingen waar oplossingen honderden nauwkeurige sequentiële beslissingen vereisen, wat inzichten biedt die overdraagbaar zijn naar robotica, bewijsgeneratie en programmasynthese.
• Wiskundige Nut: Ongeacht of het Andrews–Curtis vermoeden uiteindelijk waar of onwaar is, het werk boekt concrete vooruitgang. Als het waar is, draagt elke nieuwe trivialisering bij aan een bewijs; als het onwaar is, verkleint het trivialiseren van schijnbare tegenvoorbeelden de zoektocht naar echte tegenvoorbeelden.
• Overdraagbaarheid: De "Twee-Heuvel" structuur en de ontwikkelde technieken (substituties, cyclische architecturen, generator-solver games) worden gepresenteerd als algemeen toepasbaar op andere wiskundige zoekproblemen waar bimodale moeilijkheidsverdelingen en progressie-verstorende moves voorkomen.

De auteurs concluderen dat verdere vooruitgang niet zal komen van marginale verbeteringen in klassieke zoekmethoden, maar van learning-based methoden die in staat zijn om structuren te exploiteren die verder gaan dan wat vaste heuristieken kunnen vatten.