Detailansicht
On constant regret for low-rank MDPs
Alexander Sturm
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Data Science
Betreuer*in
Sebastian Tschiatschek
DOI
10.25365/thesis.77471
URN
urn:nbn:at:at-ubw:1-23266.04279.202040-3
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Obwohl bereits problemabhängige Regret-Bounds für lineare Markov Decision Processes (MDPs) und Low-Rank Bandits existieren, bleiben Erweiterungen auf Low-Rank MDPs unerforscht. In dieser Masterarbeit schließen wir diese Lücke und liefern Expected-Regret-Bounds für Low-Rank MDPs in einem problemabhängigen Kontext. Konkret stellen wir einen Algorithmus namens UniSREP-UCB vor, der ein beschränktes Optimierungsziel nutzt, um Representationen mit guten spektralen Eigenschaften zu lernen. Wir zeigen, dass für jeden Low-Rank MDP mit einem positiven minimalen Sub-Optimalitygap, UniSREP-UCB nach einigen Aufwärmepisoden einen Expected-Regret von \(\Tilde{O}(H^{4}d^{1/2}|\mathcal{A}|T^{2/3})\) erreicht. Darüber hinaus zeigen wir, dass eine Identifikation der optimalen Policy möglich ist, solange der minimale Sub-Optimalitygap und die Occupancy-Distributions der optimalen Policies wohldefiniert und bekannt sind. Nach bestem Wissen sind dies die ersten problemabhängigen Regret-Bounds für Low-Rank MDPs.
Abstract
(Englisch)
Although there exist instance-dependent regret results for linear Markov decision processes (MDPs) and low-rank Bandits, extensions to low-rank MDPs remain unexplored. In this master thesis, we close this gap and provide expected regret bounds for low-rank MDPs in an instance-dependent setting. Specifically, we introduce an algorithm, called UniSREP-UCB, which utilizes a constrained optimization objective to learn feature maps with good spectral properties. We show that for any low-rank MDP with positive minimal sub-optimality gap, UniSREP-UCB achieves expected regret \(\Tilde{O}(H^{4}d^{1/2}|\mathcal{A}|T^{2/3})\), after some warm-up episodes. Furthermore, we demonstrate that optimal policy identification is possible, as long as the minimal sub-optimality gap and the occupancy distributions of optimal policies are well-defined and known. To the best of our knowledge, these are the first instance-dependent regret results for low-rank MDPs.
Schlagwörter
Schlagwörter
(Deutsch)
Reinforcement Learning Low-Rank MDP Regret Representation Learning
Schlagwörter
(Englisch)
Reinforcement Learning Low-Rank MDP Regret Representation Learning
Autor*innen
Alexander Sturm
Haupttitel (Englisch)
On constant regret for low-rank MDPs
Publikationsjahr
2024
Umfangsangabe
xi, 71 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Sebastian Tschiatschek
Klassifikation
54 Informatik > 54.72 Künstliche Intelligenz
AC Nummer
AC17402408
Utheses ID
74166
Studienkennzahl
UA | 066 | 645 | |