CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs

Sintesi Tecnica: CayleyPy RL: Ricerca di Percorsi e Apprendimento per Rinforzo su Grafi di Cayley

Enunciato del Problema
Il lavoro affronta il problema della ricerca di percorsi su grafi di Cayley finiti estremamente grandi, focalizzandosi specificamente sul gruppo simmetrico $S_n$ generato da spostamenti ciclici a sinistra ($L$), spostamenti ciclici a destra ($R$) e una trasposizione dei primi due elementi ($X$). Questa configurazione, nota come grafo di Cayley LRX, corrisponde alla sequenza OEIS A186783. La sfida matematica fondamentale consiste nel decomporre un elemento del gruppo nel prodotto più breve possibile di generatori (trovare il percorso più breve nel grafo). Questo problema è NP-difficile per grafi di Cayley finiti generici. I sistemi algebrici classici, come GAP, si basano sull'algoritmo di Schreier-Sims, che spesso produce percorsi esponenzialmente lunghi e fallisce nel gestire gruppi con dimensioni superiori a $10^{30}$ (circa $n \approx 20$ per $S_n$). Gli autori mirano a sviluppare approcci efficienti basati sull'intelligenza artificiale capaci di gestire grafi con dimensioni fino a $10^{70}$ (ad esempio, $n \approx 40$ fino a $100$) producendo percorsi ottimali o quasi ottimali.

Metodologia
Gli autori propongono una metodologia ibrida che combina l'Apprendimento per Rinforzo (RL), in particolare il Deep Q-Learning (DQN), con una strategia di pre-addestramento basata sulle distanze di diffusione.

1. Framework di Apprendimento per Rinforzo: Il problema della ricerca di percorsi è inquadrato come la ricerca del percorso più breve da uno stato $s$ all'elemento identità $e$. Questo è modellato utilizzando l'equazione di Bellman, dove la funzione di distanza $d(s)$ soddisfa $d(s) = 1 + \min_{t \in N(s)} d(t)$. Il DQN standard è adattato per approssimare questa funzione di valore utilizzando reti neurali.
2. Pre-addestramento con Distanza di Diffusione: Per affrontare il problema della "ricompensa sparsa" e il rumore intrinseco nell'inizializzazione standard del DQN, gli autori introducono una fase di "riscaldamento". Generano dati di addestramento tramite camminate casuali (diffusione) partendo dall'obiettivo. Una rete neurale viene inizialmente addestrata a prevedere il numero di passi in queste camminate casuali (distanza di diffusione).
3. DQN Modificato: La rete pre-addestrata viene quindi affinata utilizzando un algoritmo DQN modificato. Crucialmente, gli obiettivi dell'aggiornamento di Bellman vengono limitati (clipped) in base al passo temporale $k$ in cui uno stato è stato visitato per la prima volta durante la generazione della camminata casuale. Questo impedisce alla rete di sovrastimare le distanze e stabilizza l'addestramento.
4. Ricerca a Raggio Guidata: Una volta che la rete neurale è addestrata a stimare le distanze, funge da funzione euristica per un algoritmo di ricerca a raggio (beam search). La ricerca a raggio mantiene un numero fisso ($W$) degli stati più promettenti a ogni passo, espandendo i loro vicini e selezionando i primi $W$ basandosi sulle previsioni della rete. Questo evita di rimanere intrappolati in minimi locali, un comune modo di fallimento per la ricerca greedy.
5. Il "Trucco X": Viene introdotta una specifica modifica euristica per i generatori LRX. Se i primi due elementi di una permutazione sono già ordinati, il generatore $X$ (che li scambia) viene escluso dall'insieme dei vicini. Questa modifica in una sola riga riduce drasticamente lo spazio di ricerca e migliora i tempi di mescolamento.
6. Non-Ritorno: Gli autori incorporano vincoli di non-ritorno sia nella generazione delle camminate casuali che nella ricerca a raggio per ridurre la varianza nelle stime delle distanze e prevenire lo stagnamento nei minimi locali.

Contributi Chiave

• Avanzamenti Algoritmici: Il lavoro presenta una combinazione innovativa di pre-addestramento con distanze di diffusione e DQN modificato. Questo approccio supera i limiti del DQN standard (ricompense sparse, obiettivi rumorosi) e supera i metodi classici.
• Benchmark di Prestazioni: I metodi proposti trovano con successo percorsi per grafi di Cayley LRX fino a $n \approx 44$ senza conoscenze pregresse e fino a $n \approx 100$ quando si utilizza il "trucco X". Questo supera significativamente le capacità di GAP, limitato a $n \approx 20$. I metodi AI producono percorsi più brevi ed eseguono più velocemente di GAP per $n$ comparabili.
• Risultati Matematici e Congetture:
  • Congettura del Diametro: Gli autori supportano fortemente la congettura OEIS-A186783 secondo cui il diametro del grafo di Cayley LRX è $n(n-1)/2$. L'hanno verificata tramite BFS brute-force per $n \le 15$ e tramite decomposizione AI per $n$ fino a 200 (tramite sfide Kaggle), non trovando decomposizioni più corte della lunghezza congetturata.
  • Elemento più Lungo: Identificano un unico "elemento più lungo" $\ell_n = (1, 0, n-1, n-2, \dots, 3, 2)$ e forniscono una decomposizione esplicita di lunghezza $n(n-1)/2$.
  • Limiti: Il lavoro dimostra un limite inferiore per il diametro di $n(n-1)/2 - n/2 - 1$ e un limite superiore di $n(n-1)/2 + 3n$ tramite un algoritmo costruttivo. Un algoritmo empirico suggerisce un limite più stretto di $n(n-1)/2 + n/2$.
  • Distribuzione della Crescita: Gli esperimenti numerici suggeriscono che la funzione di crescita del grafo LRX segue una distribuzione Gumbel asimmetrica a sinistra per $n$ grandi, in contrasto con la distribuzione gaussiana osservata nei grafi di trasposizione di vicini.
  • Tempo di Mescolamento: Mentre le camminate casuali standard hanno tempi di mescolamento tra $O(n^3)$ e $O(n^3 \log n)$, gli autori congetturano che le camminate casuali modificate con il "trucco X" mescolino più velocemente, con una complessità temporale di $O(n^2)$.
  • Spettro: Lo spettro del grafo LRX sembra seguire una distribuzione uniforme.
• Open Source e Crowdsourcing: Gli autori hanno rilasciato il progetto "CayleyPy" e creato sfide Kaggle per raccogliere soluzioni crowdsourced per la decomposizione dell'elemento più lungo e la ricerca di algoritmi ottimali, favorendo la collaborazione tra le comunità AI e matematiche.

Risultati

• Efficienza: Per $n=20$, GAP richiede oltre 41 minuti per trovare un percorso di lunghezza 217.944, mentre il metodo delle distanze di diffusione trova il percorso ottimale di lunghezza 190 in meno di 4 minuti.
• Scalabilità: Con il "trucco X", il sistema ha risolto istanze per $n=100$ (dimensione del grafo $\approx 10^{157}$) in circa 8,5 ore su una singola GPU, trovando un percorso di lunghezza 16.632 (rispetto al diametro congetturato di 4.950).
• Prestazioni del Modello: Modelli semplici come le Reti Neurali a Più Strati (MLP) e il Gradient Boosting (CatBoost/XGBoost) hanno spesso superato architetture complesse come i Transformer e le CNN per questo compito specifico.
• Ricerca a Raggio: Il tasso di successo nel trovare un percorso dipende fortemente dalla larghezza del raggio, mostrando un miglioramento super-lineare all'aumentare della dimensione del raggio, analogo allo "scambio di idee" in una comunità di ricerca.

Significato
Il lavoro afferma che gli esperimenti computazionali, in particolare quelli che sfruttano l'AI, possono avanzare significativamente la ricerca matematica sui grafi di Cayley. Dimostra che i metodi AI possono "superare" i sistemi algebrici classici sia nella scalabilità (gestendo $n$ molto più grandi) che nella qualità della soluzione (trovando percorsi più brevi e quasi ottimali). Il lavoro colma il divario tra la teoria dei gruppi teorica e l'AI pratica, fornendo limiti rigorosi, nuove congetture su crescita e tempi di mescolamento, e un quadro per risolvere problemi di ricerca di percorsi in spazi di stati estremamente grandi che erano precedentemente intrattabili. Gli autori posizionano questo come un passo verso l'applicazione dell'AI ad altri problemi di pianificazione complessi nella scienza teorica.