Technische Samenvatting: Over de Complexiteit van Offline Reinforcement Learning met $Q^\star$-benadering en Partiële Dekking

Probleemstelling

Dit werk onderzoekt de theoretische limieten van Offline Reinforcement Learning (RL) onder de setting van $Q^\star$-realiseerbaarheid en partiële dekking. In dit paradigma leert een agent een beleid (policy) uit een vaste, vooraf verzamelde dataset zonder verdere interactie met de omgeving. De dataset wordt gegenereerd door een gedragbeleid (behavior policy) dat mogelijk niet de volledige toestands-actieruimte dekt (partiële dekking).

De centrale open vraag die wordt behandeld is of $Q^\star$-realiseerbaarheid (de ware optimale Q-functie ligt binnen een bekende functieklasse) gecombineerd met Bellman-volledigheid (de Bellman-operator brengt de functieklasse naar een bovengrens-verzameling) en partiële dekking voldoende zijn voor steekproefefficiënt leren. Hoewel deze voorwaarden toelaten om een betrouwbaarheidsset te construeren die de ware $Q^\star$ bevat, stelt het artikel de vraag of dit voldoende is om een robuust beleidsselectie te garanderen.

Methodologie

1. Informatietheoretische Ondergrens

De auteurs stellen eerst vast dat de bovengenoemde voorwaarden onvoldoende zijn voor steekproefefficiënt leren. Zij construeren een familie van Markov Beslissingsprocessen (MDP's) waar:

• $Q^\star$-realiseerbaarheid en Bellman-volledigheid gelden.
• De dekking van het optimale beleid constant is ($\Theta(1)$).
• Ondanks dat de ware waardefunctie goed gelokaliseerd is binnen de functieklasse, de leerling niet in staat is om onderscheid te maken tussen beleids die leiden tot catastrofale fouten en beleids die veilig zijn.
• De vereiste steekproefcomplexiteit schaalt als $\Omega(\frac{1}{\epsilon} \min\{\sqrt{|S|}, \frac{1}{\Delta^2}\})$, waarbij $\Delta$ de waarde-gap is. Dit geeft aan dat zelfs met een kleine gap, de steekproefcomplexiteit prohibitief hoog kan zijn, en dat de moeilijkheid niet alleen voortkomt uit het schatten van $Q^\star$, maar uit het maken van robuuste beslissingen binnen de ambiguïteitsset.

2. Decision-Estimation Decompositie Raamwerk

Om de geïdentificeerde kloof aan te pakken, introduceren de auteurs een algemeen decision-estimation raamwerk, geïnspireerd door de Decision-Estimation Coefficient (DEC) uit online RL. Zij decomponeren de suboptimaliteit van offline RL in twee modulaire componenten:

1. Beslissingscomplexiteit (Decision Complexity): De moeilijkheid van het selecteren van een robuust beleid uit een betrouwbaarheidsset van plausibele modellen.
2. Schatfout (Estimation Error): De fout die optreedt bij het schatten van de waardefunctie of modelparameters vanuit de offline data.

Zij definiëren de Offline Robust Decision-Estimation Coefficient ($Ordec$):
$$Ordec\text{-}OD_\gamma(F_{conf}) := \min_{\rho \in \Delta(\Pi)} \max_{M \in \mathcal{M}_{conf}} \mathbb{E}_{\pi \sim \rho} \left[ J_M(\pi_M) - J_M(\pi) - \gamma \max_{f \in F_{conf}} D_\pi(f \| M) \right]$$
Waar:

• $F_{conf}$ de betrouwbaarheidsset is van plausibele $Q^\star$-functies.
• $\mathcal{M}_{conf}$ de geïnduceerde verzameling van plausibele modellen is.
• $\rho$ een distributie over beleids is.
• $D_\pi(f \| M)$ een discrepantiemaat is (bijv. Bellman-fout) tussen een functie en een model, geëvalueerd onder het optimale beleid van het kandidaatmodel $\pi_M$ (in tegen tegenstelling tot online DEC, dat het beleid van de leerling gebruikt).

Het raamwerk stelt een algoritme voor (E2D.OR) dat een mengbeleid (mixture policy) $\hat{\pi}$ oplevert dat voldoet aan:
$$J(\pi^\star) - \mathbb{E}[J(\hat{\pi})] \leq Ordec + \text{Schatfout}$$

Belangrijkste Bijdragen

1. Negatief Resultaat op Voldoendheid

Het artikel levert een informatie-theoretische ondergrens die bewijst dat $Q^\star$-realiseerbaarheid, partiële dekking en Bellman-volledigheid niet voldoende zijn voor steekproefefficiënt offline RL. Dit benadrukt dat de kernuitdaging in settings met partiële dekking het "beslissingsprobleem" is — het onderscheiden van veilige beleids van onveilige beleids binnen de betrouwbaarheidsset — in plaats van enkel het "schattingsprobleem".

2. Verenigd Raamwerk en Verbeterde Grenzen

Het voorgestelde $Ordec$-raamwerk verenigd en verbetert bestaande resultaten:

• Value-Gap Setting: Herstelt de resultaten van Chen en Jiang (2022), maar elimineert de noodzaak om de gap-waarde te kennen of extra online interactie uit te voeren. De grens past zich automatisch aan aan de werkelijke gap.
• Geregulariseerde Setting: Verbetert de steekproefcomplexiteitsgrens voor soft Q-learning onder partiële dekking van $\epsilon^{-4}$ (Uehara et al., 2023) naar $\epsilon^{-2}$. Dit wordt bereikt via een nieuwe tweede-orde performance difference lemma voor geregulariseerde MDP's.
• Gekromde Beslissingsgrens (Curved Decision Boundary): Introduceert een nieuwe leerbare setting gebaseerd op de kromming van de beslissingsgrens in continue actieruimtes, wat praktische zorgen adresseert over de strikte waarde-gap assumptie.

3. Nieuwe Leerbare Regimes voor Schatfout

Het artikel karakteriseert de rol van structurele assumpties bij het beheersen van de schatfout-term:

• Bellman-volledigheid: Biedt de eerste steekproefcomplexiteitsanalyse voor Conservative Q-Learning (CQL) onder algemene functiebenadering (voorheen beperkt tot tabulaire gevallen).
• Lage Bellman-rang (Low Bellman Rank): Onderzoekt de offline leerbaarheid van MDP's met een lage Bellman-rang (een canonieke online RL-setting). De auteurs tonen aan dat onder standaard data-assumpties, een lage Bellman-rang onvoldoende is voor offline leren. Zij introduceren twee noodzakelijke voorwaarden voor leerbaarheid in dit regime:
  1. Double Policy Sampling: Data moet worden gegenereerd door een beleid te samplen en vervolgens twee onafhankelijke transities te nemen.
  2. Policy Feature Coverage: Een specifieke dekkingconditie op de feature-ruimte van beleids.
     Het versoepelen van één van beide voorwaarden verbreekt de polynomiale steekproefcomplexiteitsgarantie.

Samenvatting van Resultaten

• Ondergrens: Gedemonstreerd dat $Q^\star$-realiseerbaarheid + Bellman-volledigheid + partiële dekking $\nRightarrow$ steekproefefficiënt leren.
• Bovengrens: Een algemene suboptimaliteitsgrens vastgesteld, gedecomponeerd in $Ordec$ (beslissingscomplexiteit) en schatfout.
• Specifieke Grenzen:
  • Niet-geregulariseerd (Value Gap): $\tilde{O}(\frac{H^2}{\gamma \Delta^2} + \gamma \frac{C_{\pi^\star}}{n})$. Past zich aan aan onbekende gaps.
  • Geregulariseerd: $\tilde{O}(\sqrt{\frac{C_{\pi^\star}}{n}})$, wat een $\epsilon^{-2}$ steekproefcomplexiteit oplevert.
  • CQL: Eerste algemene functiebenadering garantie voor CQL onder partiële dekking.
  • Lage Bellman-rang: Bewezen onmogelijkheid onder standaard assumpties; geïdentificeerd dat double policy sampling en policy feature coverage noodzakelijk zijn voor leerbaarheid.

Betekenis en Claims

Het artikel claimt een omvattender begrip te bieden van de potentie en beperkingen van offline RL onder $Q^\star$-benadering en partiële dekking. De betekenis ligt in:

1. Verheldering van de Bron van Moeilijkheid: Het verschuift de theoretische focus van louter schattingsfouten naar de beslissingscomplexiteit die inherent is aan settings met partiële dekking, waarbij wordt aangetoond dat zelfs met perfecte schatting, robuuste besluitvorming onmogelijk kan zijn zonder aanvullende structurele assumpties.
2. Unificatie: Het biedt een modulair raamwerk dat eerdere resultaten (Chen en Jiang, 2022; Uehara et al., 2023) herstelt, verbetert en uitbreidt door beslissingscomplexiteit en schattingscomplexiteit te scheiden.
3. Praktische Relevantie: Door CQL onder algemene functiebenadering te analyseren en de specifieke structurele vereisten voor low-Bellman-rank problemen te identificeren, overbrugt het werk de kloof tussen praktische algoritmen en theoretische garanties in settings die voorheen als onhandelbaar of slecht begrepen werden beschouwd.
4. Nieuwigheid in Settings: Het vestigt de eerste leerbaarheidscondities voor low-Bellman-rank MDP's in offline RL en biedt de eerste $\epsilon^{-2}$ grens voor geregulariseerde soft Q-learning onder partiële dekking.

De auteurs merken op dat hoewel het raamwerk theoretisch solide is, het exact oplossen van het minimax-algoritme computationeel moeilijk is, maar dat dit benaderd kan worden via actor-critic methoden. Het werk dient primair om nieuwe leerbare regimes te identificeren en de structurele condities te karakteriseren die vereist zijn voor hen.