DORA Explorer: Improving the Exploration Ability of LLMs Without Training

1. Problem Statement

Large Language Models (LLMs) used as agents for sequential decision-making suffer from a critical limitation: insufficient exploration. While LLMs possess strong reasoning capabilities, their auto-regressive nature tends to produce high-probability, repetitive sequences, causing agents to:

• Converge to sub-optimal solutions.
• Get stuck in action loops (repeating the same actions).
• Fail to discover high-reward behaviors in environments requiring active information gathering (e.g., text adventure games, multi-armed bandits).

Existing solutions have limitations:

• Temperature Scaling: Introduces token-level randomness but often fails to generate novel sequences or actions. High temperatures degrade coherence and task accuracy, while low temperatures lead to greedy, non-exploratory behavior.
• Prompting (CoT, ToT): Improves reasoning but does not explicitly control the exploration/exploitation trade-off or guarantee diverse action generation.
• Learning-based Methods: Require additional training or task-specific classifiers, limiting generalizability.

2. Methodology: DORA Explorer

The authors propose DORA (Diversity-Oriented Ranking of Actions), a training-free, inference-time framework designed to explicitly control exploration without modifying the underlying LLM.

Core Workflow

DORA operates in three main stages at each decision step $t$:

1. Candidate Action Generation:

   • The agent decides whether to act Greedy or Explore based on a decision policy $\pi_d$.
   • If Exploring, the LLM is prompted to generate a list of $n_C$ candidate actions simultaneously. This "list-level" prompting forces the model to explore the breadth of its distribution rather than collapsing to a single high-probability token sequence.
   • Invalid or previously used actions are filtered out.

2. Action Scoring:

   • Each candidate action $a$ (a sequence of tokens) is scored based on two metrics derived from token log-probabilities:
     • Mean Log-Probability ($\tilde{\mu}$): Indicates global likelihood (confidence).
     • Variance of Log-Probability ($\tilde{\sigma}^2$): Indicates internal consistency.
   • The final score $s$ is a weighted combination: $s = \alpha \cdot \tilde{\mu}(a) - (1-\alpha) \cdot \tilde{\sigma}^2(a)$.
   • This scoring mechanism favors sequences that are both probable and internally consistent, filtering out incoherent "random" outputs.

3. Probabilistic Sampling via $\lambda$:

   • A tunable exploration parameter $\lambda$ controls the sampling distribution.
   • The probability of selecting an action $a$ is calculated as: $P_\lambda(a) = \text{Softmax}(\lambda \cdot s_a)$.
   • Low $\lambda$: Flattens the distribution, encouraging exploration of lower-scoring (diverse) actions.
   • High $\lambda$: Sharpens the distribution, favoring greedy selection of the highest-scoring action.
   • $\lambda$ can be determined by a fixed schedule (e.g., decreasing over time) or dynamically sampled by the LLM based on context.

Key Design Features

• Training-Free: Requires no fine-tuning or additional model parameters.
• Modular: Plug-and-play integration into existing LLM pipelines.
• State-Aware: Explicitly tracks previously used actions to prevent immediate loops.

3. Key Contributions

1. Novel Framework: Introduction of DORA, the first training-free framework that explicitly decouples candidate generation from selection to control exploration at the sequence level rather than the token level.
2. Mechanism for Diversity: Demonstrates that prompting for multiple candidates jointly, combined with log-probability scoring, recovers latent diversity that standard sampling misses.
3. Dynamic Control: Introduces a flexible $\lambda$ parameter that allows agents to transition smoothly between exploration and exploitation, adaptable via scheduling or policy.
4. Comprehensive Evaluation: Validated across two distinct domains:
   • Multi-Armed Bandits (MAB): A theoretical testbed for exploration-exploitation trade-offs.
   • TALES (Text Adventure Learning Environment Suite): A suite of complex text-based environments (TextWorld, AlfWorld, ScienceWorld, etc.) requiring long-horizon planning.

4. Experimental Results

Multi-Armed Bandits (MAB)

• Performance: DORA achieved UCB-competitive performance, outperforming standard LLM baselines (Zero-shot, CoT, ToT) and even traditional bandit algorithms like Thompson Sampling in specific metrics.
• Regret & Failure: DORA achieved zero Suffix Failure Frequency (never getting stuck on a sub-optimal arm after the first half of the horizon), whereas temperature-scaled baselines failed up to 95% of the time.
• Comparison: DORA significantly reduced cumulative regret compared to greedy and fixed-temperature strategies.

Text Adventure Learning Environment Suite (TALES)

• Task Success: DORA consistently improved success rates across all environments.
  • Example: On TextWorld with Qwen2.5-7B, performance jumped from 29.2% (Zero-shot) to 45.5% (DORA).
  • On Mistral Small 22B, DORA achieved 74.28% in TextWorld, significantly outperforming the next best baseline (57.78%).
• Exploration Depth: DORA agents visited 2x more unique states (observations) than baseline methods, indicating superior discovery of hidden objects and task-relevant signals.
• Loop Recovery: DORA drastically reduced the number of loops encountered and improved loop recovery rates by 5x to 20x compared to baselines (e.g., 19.5% recovery in TextWorld vs. <4% for others).
• Efficiency: Despite generating multiple candidates, DORA incurred low token overhead (approx. 2x the tokens of simple prompting, but with massive performance gains).

Ablation Studies

• Structured vs. Stochastic: Replacing DORA with simple temperature sampling ($\tau$) resulted in performance degradation, proving that DORA's success comes from structured exploration, not just randomness.
• Scoring: The combination of mean log-prob and variance was crucial; removing the variance penalty led to incoherent action selection.

5. Significance

• Bridging the Gap: DORA addresses the fundamental disconnect between token-level sampling and action-level decision-making in LLM agents.
• Generalizability: As a training-free method, it is immediately applicable to any pre-trained LLM and any text-based environment without the cost of fine-tuning.
• Practical Impact: It enables LLM agents to function effectively in "dark" environments where information is sparse and trial-and-error is necessary, making them more robust for real-world applications like robotics, scientific discovery, and complex game playing.
• Paradigm Shift: The paper suggests that for LLM agents, controlled diversity (via candidate generation and ranking) is superior to stochastic diversity (via temperature scaling) for solving sequential decision-making problems.