Neuer Regret‑Bound für Online Q‑Learning ohne Optimismus

Ein neues arXiv‑Veröffentlichungsdokument liefert den ersten hochwahrscheinlichen Regret‑Bound für klassisches Online Q‑Learning in unendlichen, diskontierten Markov‑Entscheidungsprozessen. Dabei verzichtet die Analyse völlig auf die üblichen Optimismus‑ oder Bonus‑Termini, die in der Literatur häufig eingesetzt werden.

Der Beitrag beginnt mit einer detaillierten Untersuchung von Boltzmann‑Q‑Learning, bei dem die Temperatur schrittweise abnimmt. Hier zeigt sich, dass der Regret‑Wert stark vom Suboptimalitäts­gap des MDPs abhängt: Für große Gaps bleibt der Regret sublinear, während er bei kleinen Gaps linear ansteigen kann. Diese Abhängigkeit limitiert die praktische Anwendbarkeit des Ansatzes.

Um dieses Problem zu überwinden, wird ein „Smoothed ε_n‑Greedy“‑Explorationsschema vorgestellt, das ε_n‑Greedy‑ und Boltzmann‑Exploration kombiniert. Für dieses Verfahren wird ein gap‑robuster Regret‑Bound von nahezu \(\tilde{O}(N^{9/10})\) bewiesen, was einen bedeutenden Fortschritt gegenüber bisherigen Resultaten darstellt.

Zur Analyse dieser Algorithmen entwickelt die Arbeit einen hochwahrscheinlichen Konzentrations­bound für kontraktive, markovische stochastische Approximationen mit iterativen und zeitabhängigen Übergangsdynamiken. Der Kontraktions­faktor in diesem Bound wird durch die Mischzeit bestimmt und ist im asymptotischen Verlauf sogar zulässig, sich auf eins zu nähern. Dieser neue Bound könnte daher auch in anderen Bereichen der stochastischen Approximation von großem Nutzen sein.