30.01.2025, 11:30 Uhr
Universität Wien
Besprechungsraum 4.34
Währinger Str. 29
1090 Wien
Titel: On Constant Regret for Low-Rank MDPs
Kurzfassung:
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, UniSREPUCB
nach einigen Aufwärmepisoden einen Expected-Regret von O ˜ (H4d1/2|A|T2/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.