Technische Samenvatting: De Horizontdrempel in Coöperatieve Multi-Agent Reward-Free Exploration

Probleemstelling

Dit werk onderzoekt coöperatieve multi-agent reward-free exploration binnen het kader van tabulaire finite-horizon Markov Decision Processes (MDP's). In deze setting interageren $m$ agents parallel met een onbekende omgeving $M = (S, s_0, A, H, P, r)$ over $\rho$ leerfasen. Cruciaal is dat tijdens de exploratiefase de agents de rewardfunctie $r$ niet waarnemen; hun doel is om de overgangsdynamica $P$ nauwkeurig genoeg te leren om een $\epsilon$-optimale policy te berekenen voor elke rewardfunctie die na de exploratie wordt onthuld.

De centrale onderzoeksvraag betreft de afweging tussen twee resources:

1. Parallelle Tijd: Het aantal leerfasen $\rho$.
2. Agentcomplexiteit: Het aantal agents $m$ dat per fase wordt ingezet.

Het artikel tracht te karakteriseren hoe de horizon $H$ de efficiëntie van het leren bepaalt, en specifiek vast te stellen of een polynomiaal aantal agents voldoende is wanneer het aantal fasen beperkt is.

Methodologie

Bovenste Grens: Het H-MARFE-algoritme

De auteurs stellen H-MARFE (H-Phase Multi-Agent Reward-Free Exploration) voor, een algoritme dat is ontworpen om precies in $\rho = H$ fasen te opereren met behulp van een polynomiaal aantal agents.

Kernmechanisme:
In tegenstelling tot sequentiële regret-minimalisatiebenaderingen, maakt H-MARFE gebruik van een laag-voor-laag exploratiestrategie die de schattingenauwkeurigheid schaalbaar maakt met de bereikbaarheid van toestanden.

1. Gefaseerde Dynamica-schatting: In fase $i$ (waarbij $i \in \{0, \dots, H-1\}$) richt het algoritme zich uitsluitend op het schatten van de overgangsdynamica $P_i$ op tijdstap $i$.
2. Bereikbaarheidsfiltering: Het algoritme definieert een set "actieve" toestanden $\hat{S}^\beta_i$ op elk tijdstip, bestaande uit toestanden met een bereikbaarheidswaarschijnlijkheid van ten minste $\beta$ onder de huidige geschatte dynamica. Toestanden met lage bereikbaarheid worden effectief weggesneden door deterministisch over te gaan naar een sink-toestand $s_{sink}$.
3. Policy Constructie: Voor elk actief state-action paar $(s, a)$ berekent het algoritme een policy $\hat{\pi}_{i,s,a}$ die de waarschijnlijkheid maximaliseert om $s$ op tijdstap $i$ te bereiken en actie $a$ te nemen, gebaseerd op de dynamica die in eerdere fasen is geleerd.
4. Parallelle Executie: In elke fase worden $m$ agents toegewezen aan willekeurige state-action paren uit de actieve set. Ze voeren hun toegewezen policies uit om trajecten te verzamelen, die worden geaggregeerd om empirische overgangsschattingen voor de huidige laag te vormen.

Technische Innovatie:
De analyse introduceert een tussenvorm van dynamica-model $P^1$ dat overeenkomt met de ware dynamica $P$ op de actieve set, maar anders overgaat naar $s_{sink}$. Het bewijs berust op het begrenzen van de policy-gewogen fout tussen de geschatte dynamica $\hat{P}$ en $P^1$. Door de additieve fout in bezettingsmaten te controleren ten opzichte van bereikbaarheid, zorgt het algoritme ervoor dat de waarde-schattingfout voor elke rewardfunctie begrensd blijft, waardoor de exponentiële foutaccumulatie wordt vermeden die kenmerkend is voor naïeve parallelisatie.

Constructie van de Onderste Grens

Om de noodzaak van het aantal fasen op horizonschaal vast te stellen, construeren de auteurs een "Key-Dynamic" MDP.

• Structuur: De MDP heeft een toestandsruimte van grootte 2 ($s^\star$ en $s_{sink}$). Er bestaat een verborgen "sleutel"-sequentie van acties $a^\star_0, \dots, a^\star_{H-1}$. Het nemen van de juiste actie $a^\star_h$ in staat $s^\star$ houdt de agent in $s^\star$; elke andere actie leidt tot de absorberende sink-toestand $s_{sink}$.
• Reward: Een specifieke rewardfunctie $r_{key}$ geeft een reward van 1 alleen als de agent het laatste tijdstip bereikt in staat $s^\star$ na het uitvoeren van de juiste laatste actie.
• Implicatie: Om de dynamica (en dus de optimale policy) te leren, moet een algoritme de volledige sleutelsequentie ontdekken. In een enkele fase kunnen $m$ agents ten hoogste $\log_A(m)$ bits van de sleutel onthullen. Als het aantal fasen $\rho$ aanzienlijk kleiner is dan $H, daalt de kans op het ontdekken van de volledige sleutel exponentieel, tenzij het aantal agents $m$ exponentieel groeit met $H/\rho$.

Belangrijkste Resultaten

1. Bovenste Grens (Stelling 3.1)

Het H-MARFE-algoritme bereikt een $\epsilon$-optimale policy voor elke rewardfunctie met hoge waarschijnlijkheid met behulp van:

• Fasen: $\rho = H$.
• Agents: $m = \tilde{O}\left(\frac{S^6 H^6 A}{\epsilon^2}\right)$.

Dit toont aan dat efficiënt leren (polynomiaal in $S, A, H, \epsilon^{-1}$) haalbaar is wanneer het aantal leerfasen lineair schaalt met de horizon.

2. Onderste Grens (Stelling 4.1)

Voor elke coöperatieve multi-agent algoritme dat beperkt is tot $\rho < H$ leerfasen, vereist het bereiken van constante nauwkeurigheid (bijvoorbeeld $\epsilon = 0.1$):

• Agents: $m = \Omega\left(\frac{A^{(H-1)/\rho}}{\rho}\right)$.

Deze onderste grens bewijst dat het verminderen van het aantal fasen onder de horizon een exponentiële toename in het aantal agents noodzakelijk maakt.

3. De Horizontdrempel

De gecombineerde resultaten identificeren een scherpe regimewisseling die wordt gedomineerd door de horizon $H$:

• Polynomiaal Regime: Wanneer $\rho \approx H$, is de agentcomplexiteit polynomiaal.
• Exponentieel Regime: Wanneer $\rho \ll H$, wordt de agentcomplexiteit exponentieel in $H/\rho$.

Betekenis en Claims

Het artikel claimt een fundamentele limiet vast te stellen op de parallelle efficiëntie van reward-free exploration in tabulaire MDP's. De primaire bijdrage is de identificatie van de horizon $H$ als een kritieke drempel voor parallelle tijd.

• Noodzaak van fasen op horizonschaal: Het werk toont aan dat om exponentiële agentcomplexiteit te vermijden, men de exploratie niet zomaar kan comprimeren tot een constant of sub-lineair aantal fasen. Het aantal fasen moet schalen met de horizon.
• Algoritmische Efficiëntie: H-MARFE biedt een computationeel efficiënte methode om deze optimale afweging te bereiken, in contrast met eerdere literatuur over reward-free exploration die inherent sequentieel is of vereist dat de switchkosten lineair schalen met het aantal episodes.
• Theoretische Kloof: De auteurs merken op dat hoewel hun bovenste grens polynomiale complexiteit bereikt, de afhankelijkheid van $S$ en $H$ ($S^6 H^6$) hoger is dan de state-of-the-art single-agent grenzen ($S^2 H^3$). Zij stellen expliciet dat het een open vraag blijft of deze kloof een inherente kost van parallelisatie is of een artefact van hun analyse.

Het artikel concludeert dat coöperatieve multi-agent reward-free exploration alleen haalbaar is met polynomiale resources als de parallelle tijd (fasen) mag schalen met de horizon van het probleem, wat deze setting fundamenteel onderscheidt van scenario's waarbij parallelisme de tijdscomplexiteit willekeurig kan verminderen zonder exponentiële resourcekosten.