Provably Efficient Large-scale Reinforcement Learning via Primal-dual Optimization.

Diaz, Mauro (avtor), Neu, Gergely (mentor), Oblak, Polona (komentor)

In offline reinforcement learning with function approximation, learning from datasets with only partial coverage remains a central challenge. The fundamental difficulty is distribution shift: the learned policy may select poorly covered actions, forcing value estimates to extrapolate beyond the available data. Feature Occupancy Gradient AScent (FOGAS) addresses this problem in linear Markov decision processes (MDPs) and provides strong guarantees under the weakest known partial-coverage condition for this setting, but requires a known linear feature map. This thesis investigates whether its optimization structure remains useful beyond this linear setting. We introduce Generalized FOGAS, an empirical primal--dual algorithm that retains the main update structure of FOGAS while allowing more general function approximation. In the shared linear-feature setting, its objective recovers the empirical FOGAS objective. To the best of our knowledge, we also provide the first systematic empirical evaluation of FOGAS. The results show that Generalized FOGAS preserves much of FOGAS's favorable behavior across different coverage conditions while extending its optimization structure to nonlinear function approximation.

• Jezik: Angleški jezik
• Ključne besede: Offline reinforcement learning, Primal-dual optimization, Partial coverage, Function approximation
• Vrsta gradiva: Magistrsko delo
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2026
• PID: 20.500.12556/RUL-190759
• Datum objave v RUL: 03.11.2026

Sekundarni jezik

• Jezik: Slovenski jezik
• Naslov: Dokazljivo učinkovito spodbujevano učenje velikega obsega s prirejeno optimizacijo.

Izvleček

Pri spodbujevanem učenju brez povezave z aproksimacijo funkcij ostaja učenje iz podatkovnih množic z delno pokritostjo osrednji izziv. Temeljna težava je premik porazdelitve: naučena politika lahko izbere dejanja, ki jih podatkovna množica slabo pokriva, zaradi česar je treba vrednosti ocenjevati z ekstrapolacijo zunaj obsega razpoložljivih podatkov. Algoritem Feature Occupancy Gradient AScent (FOGAS) obravnava ta problem v linearnih Markovskih odločitvenih procesih (MDP) in zagotavlja močna jamstva pod najšibkejšim znanim pogojem delne pokritosti v tem okviru, vendar zahteva znano linearno preslikavo značilk. V tem magistrskem delu raziskujemo, ali optimizacijska struktura algoritma FOGAS ostaja uporabna tudi zunaj linearnega okvira. Predstavimo posplošitev (Generalized FOGAS), empirični primalno--dualni algoritem, ki ohranja glavno strukturo posodobitev algoritma FOGAS, hkrati pa omogoča splošnejšo aproksimacijo funkcij. V primeru skupne linearne preslikave značilk obeh algoritmov, tudi njuni ciljni funkciji sovpadata. Kolikor nam je znano, predstavimo prvo sistematično empirično vrednotenje algoritma FOGAS. Rezultati kažejo, da Generalized FOGAS pri različnih pogojih pokritosti v veliki meri ohranja ugodno delovanje algoritma FOGAS, hkrati pa njegovo optimizacijsko strukturo razširja na nelinearno aproksimacijo funkcij.

• Ključne besede: Spodbujevano učenje brez povezave, Primalno-dualna optimizacija, Delna pokritost, Aproksimacija funkcij