Neuer Algorithmus garantiert replizierbare RL-Politiken

Reinforcement Learning (RL) steht seit langem vor dem Problem der Replizierbarkeit: kleine Änderungen in den Trainingsbedingungen führen häufig zu stark unterschiedlichen Ergebnissen. Um dieses Problem systematisch anzugehen, wurde der Begriff der „List Replicability“ im PAC‑RL‑Rahmen eingeführt.

Bei List Replicability muss ein Algorithmus eine nahezu optimale Politik liefern, die in einer kleinen Liste von Politiken – unabhängig von der jeweiligen Ausführung – enthalten ist. Die Größe dieser Liste definiert die „List Complexity“. Es gibt zwei Varianten: die schwache Form verlangt lediglich, dass die finale Politik in der Liste vorkommt, während die starke Form zusätzlich sicherstellt, dass die gesamte Folge ausgeführter Politiken ebenfalls in einer kleinen Menge bleibt.

Die vorgestellte Arbeit liefert einen tabellarischen RL‑Algorithmus, der sowohl schwache als auch starke List Replicability garantiert. Durch sorgfältige Analyse bleibt die List Complexity polynomiell in Bezug auf Zustände, Aktionen und die Horizon‑Länge, was bisher bei bestehenden Algorithmen nicht möglich war.

Der Durchbruch beruht auf zwei wesentlichen Innovationen: Erstens wählt ein neues Planungsverfahren Aktionen lexikografisch aus einer Menge nahezu optimaler Optionen, die innerhalb eines zufällig gewählten Toleranzschwellenwertes liegen. Zweitens wird ein Mechanismus zur Testung der Erreichbarkeit von Zuständen eingeführt, der die Stabilität der Lernprozesse weiter erhöht.