DORA Explorer: Improving the Exploration Ability of LLMs Without Training

Probleemstelling

Hoewel Large Language Models (LLMs) krachtige redeneercapaciteiten hebben en veelvuldig worden ingezet als agenten voor sequentiële besluitvorming (bijv. in aanbevelingssystemen, robotics en games), kampen ze met een fundamenteel tekort aan exploratie.

• Het dilemma: In onbekende omgevingen moeten agenten een balans vinden tussen exploratie (het verzamelen van nieuwe informatie) en exploitatie (het maximaliseren van de beloning op basis van bekende informatie).
• De beperking van bestaande methoden: LLM-agenten hebben de neiging om vast te komen zitten in lokale optima of repetitieve loops. Bestaande strategieën zoals temperatuur-sampling (het introduceren van willekeur op token-niveau) of geavanceerde prompt-methoden zoals Chain-of-Thought (CoT) en Tree-of-Thought (ToT) blijken ontoereikend.
  • Temperatuur-sampling zorgt voor diversiteit op token-niveau, maar garandeert geen diversiteit op sequentie-niveau (de volledige actie).
  • LLMs genereren vaak hoge-kans, creatieve maar niet-nieuwe sequenties, wat leidt tot het herhalen van dezelfde acties zonder daadwerkelijke verkenning van de omgeving.

Methodologie: DORA Explorer

De auteurs introduceren DORA Explorer (Diversity-Oriented Ranking of Actions), een trainingsvrij framework dat de exploratie van LLM-agenten verbetert tijdens de inferentie (inference-time). Het framework verschuift de focus van willekeurige token-sampling naar gestructureerde sequentie-exploratie.

Het proces verloopt in vier stappen (geformaliseerd in Algorithm 1):

1. Beslissing: Gierig vs. Exploratie:
   Op elk tijdstip $t$ beslist de agent, gebaseerd op de context (geschiedenis + huidige observatie), of hij "gierig" moet handelen (de meest waarschijnlijke actie kiezen) of moet "exploreren".

2. Generatie van Kandidaat-Acties:
   Als de agent kiest voor exploratie, wordt er een lijst van $n_C$ mogelijke acties gegenereerd via list-level prompting. Door de LLM expliciet te vragen om een lijst te genereren, wordt gedwongen dat het model de breedte van de verdeling verkent in plaats van te convergeren naar één mode. Ongeldige of eerder gebruikte acties worden verwijderd.

3. Scoren van Acties (Scoring):
   Elke kandidaat-actie wordt gescoord op basis van twee statistieken van de token-log-probabiliteiten:

   • Gemiddelde log-probabiliteit ($\mu$): Geeft aan hoe waarschijnlijk de LLM de hele sequentie vindt.
   • Variantie van log-probabiliteit ($\sigma^2$): Geeft aan hoe consistent de sequentie intern is.
     De uiteindelijke score $s$ wordt berekend als: $s = \alpha \cdot \tilde{\mu}(a) - (1 - \alpha) \cdot \tilde{\sigma}^2(a)$. Een hogere score duidt op een waarschijnlijke en coherente actie.

4. Selectie via $\lambda$-probabiliteiten:
   De geselecteerde acties worden gewogen met een exploratie-parameter $\lambda$.

   • De kansverdeling wordt berekend als: $P_\lambda(a) = \text{Softmax}(\lambda \cdot s_a)$.
   • Een lage $\lambda$ resulteert in een vlakkere verdeling (meer exploratie, meer diversiteit).
   • Een hoge $\lambda$ resulteert in een scherpe verdeling (meer exploitatie, selectie van de beste score).
   • $\lambda$ kan vast worden ingesteld via een schema (bijv. exponentieel dalend) of dynamisch worden bepaald door de agent zelf.

Belangrijkste Bijdragen

• Trainingsvrij Framework: DORA vereist geen extra training, fine-tuning of aanpassing van de modelarchitectuur. Het is "plug-and-play" en werkt met bestaande open-source LLMs.
• Gestuurde Diversiteit: In tegenstelling tot pure temperatuur-sampling, controleert DORA de diversiteit op het niveau van de volledige actie-sequentie, wat leidt tot betekenisvolle verkenning in plaats van willekeurige ruis.
• Modulariteit: Het framework kan naadloos worden geïntegreerd in bestaande agent-pipelines en werkt onafhankelijk van de specifieke taak of omgeving.

Resultaten

De auteurs evalueren DORA in twee hoofdsettings: Multi-Armed Bandits (MAB) en de Text Adventure Learning Environment Suite (TALES).

1. Multi-Armed Bandits (MAB):

• DORA presteert concurrerend met klassieke algoritmen zoals Upper Confidence Bound (UCB) en Thompson Sampling.
• Het vermindert de "Suffix Failure Frequency" (het falen om de optimale arm te vinden na de helft van de tijd) tot 0%, terwijl standaard temperaturen en greedy strategieën vaak vastlopen in suboptimale keuzes.
• DORA slaagt erin om vroeg in het proces te exploreren en later over te schakelen naar exploitatie, wat resulteert in een lagere cumulatieve spijt (regret).

2. TALES (Text Adventures):

• Getest op omgevingen zoals TextWorld, AlfWorld, ScienceWorld en Jericho.
• Verbeterde Omgevingsdekking: DORA bezoekt aanzienlijk meer unieke staten (observaties) dan baselines (CoT, ToT, ReAct). In TextWorld en ScienceWorld werd meer dan 2x zoveel unieke staten bezocht.
• Loop-herstel: DORA reduceert het aantal loops drastisch en verbetert het vermogen om uit loops te ontsnappen met een factor 5 tot 20 ten opzichte van baselines.
• Totale Succes: Er is een consistente verbetering in de taak-scores. Bijvoorbeeld, voor Qwen2.5-7B in TextWorld steeg de score van 29,2% naar 45,5%.
• Efficiëntie: Ondanks het genereren van meerdere kandidaten, is de token-overhead laag en de prestatiewinst significant.

Betekenis en Conclusie

DORA Explorer adresseert een cruciale beperking van LLM-agenten: het onvermogen om effectief te exploreren in onbekende omgevingen zonder extra training.

• Het paper demonstreert dat gestructureerde exploratie (het genereren en scoren van diverse acties) superieur is aan puur stochastisch sampling (temperatuur).
• De methode maakt LLM-agenten robuuster in omgevingen met gedeeltelijke observatie en onzekerheid, waardoor ze beter in staat zijn om verborgen informatie te ontdekken en zich aan te passen aan complexe taken.
• Omdat het trainingsvrij is, biedt het een directe en praktische oplossing voor het verbeteren van de prestaties van bestaande LLMs in applicaties zoals robotics, games en wetenschappelijke ontdekking.