Technische Samenvatting: Herbezinning op Geregulariseerde Beleidsoptimalisatie voor Stabiele en Efficiënte Versterkende Leer in Spellen met Twee Spelers

Probleemstelling

Spellen met twee spelers, met name bordspellen, hebben traditioneel gediend als benchmarks voor versterkende leer (RL). Hoewel zoekgebaseerde methoden zoals AlphaZero (Silver et al., 2018) supermenselijke prestaties hebben behaald door diepe neurale netwerken te combineren met vooruitkijkende zoekalgoritmen (bijvoorbeeld Monte-Carlo Tree Search, MCTS), brengen ze aanzienlijke rekenkosten met zich mee. Het trainen van AlphaZero vereist bijvoorbeeld naar verluidt meer dan 10 GPU-jaren (Silver et al., 2018; Tian et al., 2019). Deze intensiteit van middelen belemmert reproduceerbaarheid en praktische toepassing in omgevingen met beperkte middelen (Zhao et al., 2022).

Hoewel recente studies hebben geprobeerd de rekenlast van zoekgebaseerde methoden te verminderen door de boomdiepte of het aantal rollouts te beperken (Hessel et al., 2021; Danihelka et al., 2022), vertrouwen zij fundamenteel nog steeds op vooruitkijkende zoekalgoritmen. Daarentegen zijn model-vrije RL-methoden, die efficiënt zijn in robotica en continue regeling, niet volledig onderzocht in bordspellen vanwege de waargenomen instabiliteit in multi-agent zelfspel-omgevingen. De centrale vraag die door dit werk wordt beantwoord is: Kan een puur model-vrij RL-algoritme stabiele en concurrerende leer bereiken in spellen met twee spelers met aanzienlijk minder trainingsmiddelen dan zoekgebaseerde tegenhangers?

Methodologie

De auteurs stellen KLENT (KL en Entropie Geregulariseerde Beleidsoptimalisatie) voor, een model-vrij RL-algoritme dat de noodzaak van MCTS tijdens het trainen elimineert. De aanpak is gebaseerd op het herbezinnen van geregulariseerde beleidsoptimalisatie met twee specifieke componenten: reverse Kullback-Leibler (KL) regularisatie en entropie regularisatie.

1. Beleidswijzigingsregel

De kern van KLENT is een geregulariseerd beleidsoptimalisatieprobleem gedefinieerd als:
$$\max_{\pi'} \mathbb{E}_{A \sim \pi'(\cdot|s)}[Q^\pi(s, A)] - \beta D_{KL}(\pi'(\cdot|s) \parallel \pi(\cdot|s)) + \alpha H(\pi'(\cdot|s))$$
waarbij:

• $\pi'$ het nieuwe beleid is, en $\pi$ het voorafgaande beleid.
• $D_{KL}(\pi' \parallel \pi)$ de reverse KL-divergentie is, die geleidelijke beleidswijzigingen bevordert om om te gaan met non-stationariteit in zelfspel.
• $H(\pi')$ de entropie is, die aanhoudende exploratie aanmoedigt om overfitting op het eigen beleid van de agent te voorkomen.
• $\alpha$ en $\beta$ niet-negatieve hyperparameters zijn.

Gegeven de eindige actieruimte van bordspellen, staat de optimale beleidsstrategie $\pi'$ een gesloten analytische oplossing toe:
$$\pi'(a|s) = \frac{1}{Z(s)} \exp\left( \frac{Q^\pi(s, a) + \beta \log \pi(a|s)}{\alpha + \beta} \right)$$
In KLENT wordt een neurale netwerk $\pi_\theta$ getraind om de cross-entropie tussen zijn output en deze analytisch afgeleide doelstelling $\pi'$ te minimaliseren.

2. Leren van de Waardefunctie

In tegenstelling tot zoekgebaseerde methoden die actiewaarden schatten via MCTS-backups, parameteriseert KLENT de actiewaardefunctie $Q^\pi(s, a)$ direct met behulp van een neurale netwerk. Om het leren te stabiliseren en de afweging tussen bias en variantie te beheren, gebruikt het algoritme $\lambda$-returns ($G^\lambda$) als leerdoel voor de waardefunctie, in plaats van standaard Monte Carlo-returns ($\lambda=1$). Voorlopige experimenten gaven aan dat een intermediaire $\lambda \in (0, 1)$ de som van de gekwadrateerde bias en variantie beter minimaliseert dan $\lambda=1$.

3. Algoritme-structuur

KLENT wisselt af tussen een zelfspelfase (het verzamelen van on-policy data) en een fitting-fase (het updaten van netwerkparameters). De verliesfunctie optimaliseert gelijktijdig de beleids- en actiewaarde-netwerken:
$$L(\theta) = \mathbb{E}_D \left[ -\sum_{a \in A} \pi'(a|S) \log \pi_\theta(a|S) + (Q_\theta(S, A) - G^\lambda)^2 \right]$$
Cruciaal is dat KLENT tijdens het trainen geen boomzoekalgoritme vereist, en uitsluitend vertrouwt op de voorspellingen van het neurale netwerk en de analytische beleidswijziging.

Belangrijkste Bijdragen

Het artikel levert drie primaire bijdragen, met de nadruk op de theoretische en empirische karakterisering van deze specifieke combinatie van regularisatie in plaats van het voorstellen van volledig nieuwe algoritmische ingrediënten:

1. Algoritmische Formulering: De auteurs leiden een praktisch model-vrij RL-algoritme (KLENT) af op basis van de combinatie van reverse-KL en entropie regularisatie, en bieden een gesloten-formule beleidswijzigingsregel.
2. Theoretische Garantiën: Nieuwe convergentiegaranties worden geboden voor de beleidswijzigingsregel in twee scenario's:
   • Spellen in Normaalvorm: Het artikel bewijst lokale lineaire convergentie naar een uniek vast punt onder de voorwaarde $\alpha(\alpha + 2\beta) > \|R\|_2^2/4$. Deze voorwaarde bestrijkt een bredere reeks regularisatiecoëfficiënten dan eerdere resultaten (bijvoorbeeld Sokota et al., 2022).
   • Spellen met Eindige Lengte: De auteurs bewijzen dat het KLENT-beleid convergeert naar een entropie-geregulariseerde optimale beleidsstrategie (Quantal Response Equilibrium) via achterwaartse induktie, uitgaande van een eindige spelhorizon.
3. Empirische Validatie: Uitgebreide experimenten op vijf bordspellen (Animal Shogi, Gardner Chess, 9x9 Go, Hex en Othello) tonen aan dat KLENT aanzienlijk hogere trainings-efficiëntie bereikt dan bestaande zoekgebaseerde en model-vrije baselines.

Resultaten

Trainings-efficiëntie

Experimenten tonen aan dat KLENT efficiënter leert dan bestaande methoden in alle geteste omgevingen.

• Prestatiewinst: Gemiddeld behaalde KLENT tot 4x hogere trainings-efficiëntie in vergelijking met Gumbel AlphaZero (de sterkste zoekgebaseerde baseline in de studie). Bijvoorbeeld, Gumbel AlphaZero vereiste 300 miljoen simulator-evaluaties om een winpercentage van 50% te bereiken, terwijl KLENT slechts 75 miljoen vereiste.
• Schaalbaarheid: Het efficiëntieverschil wordt groter in spellen met hogere vertakkingsfactoren (bijvoorbeeld 9x9 Go, Hex), waarbij zoekgebaseerde methoden aanzienlijke simulator-budgetten vereisen. Het voordeel van KLENT wordt toegeschreven aan het vermijden van vooruitkijkende zoekalgoritmen en het gebruik van stabiele $\lambda$-returns.
• Prestaties op Grote Schaal: In 19x19 Go behield KLENT concurrerende trainings-efficiëntie in vergelijking met AlphaZero, ondanks de toegenomen complexiteit.

Ablatiestudies

De studie valideert de noodzaak van drie sleuteltechnieken:

• Reverse-KL Regularisatie: Het verwijderen hiervan (door $\beta=0$ te stellen) leidt tot abrupte beleidswijzigingen en verslechterde prestaties, met name in 9x9 Go.
• Entropie Regularisatie: Het verwijderen hiervan (door $\alpha=0$ te stellen) zorgt ervoor dat het beleid te deterministisch wordt (de entropie daalt naar bijna nul), wat leidt tot instabiel leren en het instorten van de prestaties.
• $\lambda$-Returns: Het vervangen van $\lambda$-returns door 1-stap backups of Monte Carlo-returns resulteerde in prestatiedalingen, wat het belang bevestigt van het afwegen van bias en variantie.

Prestaties tijdens het Testen

Wanneer uitgerust met test-tijd MCTS (800 rollouts), behaalden KLENT-agenten hoge winpercentages tegen baselines, en presteerden ze beter dan AlphaZero en Gumbel AlphaZero in head-to-head wedstrijden op 9x9 Go en 19x19 Go.

Betekenis en Claims

De auteurs positioneren dit werk als een demonstratie dat het correct herbezinnen van bestaande regularisatietechnieken kan leiden tot stabiel en efficiënt leren in domeinen die lang doorzoekgebaseerde methoden zijn gedomineerd.

• Bescheiden Claims: Het artikel stelt expliciet dat de belangrijkste bijdrage geen nieuw algoritmisch ingrediënt is, maar een nieuwe theoretische en empirische karakterisering van geregulariseerde beleidsoptimalisatie in spellen met twee spelers.
• Beperkingen: De auteurs erkennen dat hoewel KLENT hoge efficiëntie bereikt, het niet noodzakelijk superieure asymptotische prestaties garandeert wanneer onbeperkte rekenmiddelen beschikbaar zijn. Zij sluiten de effectiviteit van zoekgebaseerde benaderingen zoals AlphaZero niet uit wanneer enorme middelen (bijvoorbeeld duizenden GPU's) toegankelijk zijn.
• Breder Impact: De auteurs suggereren dat de onderliggende aanname (MDP met eindige acties) van toepassing is op real-world problemen zoals discrete optimalisatie, algoritmische ontdekking en wiskundig bewijzen, waar zoekgebaseerde methoden momenteel prevalent zijn. Zij hopen dat dit werk aanmoedigt om dergelijke efficiënte, model-vrije benaderingen uit te breiden naar andere velden.

Kortom, KLENT biedt een rekenkundig efficiënt alternatief voor zoekgebaseerde RL voor bordspellen, waarbij concurrerende prestaties worden bereikt met een fractie van de trainingsmiddelen door gebruik te maken van de stabiliteit van reverse-KL en entropie regularisatie.