Neuer Algorithmus liefert optimale varianzabhängige Regret-Bound für MDPs

Online‑Reinforcement‑Learning in unendlichen Markov‑Entscheidungsprozessen (MDPs) ist bislang weniger theoretisch und algorithmisch ausgearbeitet als die episodische Variante. Viele bestehende Verfahren leiden unter hohen „Burn‑In“-Kosten und passen sich nicht optimal an die spezifische Komplexität einzelner Instanzen an.

In der vorliegenden Arbeit werden diese Schwächen für zwei zentrale Ziele – den klassischen durchschnittlichen Regret und den γ‑Regret – adressiert. Die Autoren stellen einen einzigen, handhabbaren UCB‑Stil‑Algorithmus vor, der in beiden Settings anwendbar ist und erstmals optimale varianzabhängige Regret‑Grenzen liefert.

Die Regret‑Grenzen haben die Form Õ(√(SA Var) + untere‑Ordnung‑Terme), wobei S und A die Größen der Zustands‑ bzw. Aktionsräume sind und Var die kumulative Übergangsvarianz beschreibt. Diese Resultate sind minimax‑optimal für den schlimmsten Fall, passen sich jedoch an einfachere Probleminstanzen an – beispielsweise führt der Algorithmus in deterministischen MDPs zu nahezu konstantem Regret.

Ein weiterer Fortschritt liegt in den deutlich verbesserten unteren‑Ordnung‑Termen für das durchschnittliche Regret. Mit Vorwissen über die optimale Bias‑Span liefert der Algorithmus Terme, die proportional zu ||h*||_sp S² A skaliert, und die Autoren zeigen, dass diese Skalierung optimal ist. Ohne Vorwissen beweisen sie, dass kein Algorithmus Terme kleiner als ||h*||_sp² S A erreichen kann, und stellen einen prior‑freien Algorithmus vor, der diese Grenze ebenfalls erreicht.

Diese Ergebnisse markieren einen bedeutenden Schritt nach vorn in der Theorie des Online‑Reinforcement‑Learnings für unendliche MDPs und eröffnen neue Möglichkeiten für effiziente, an Instanzkomplexität angepasste Lernalgorithmen.