Odysseus: Scaling VLM Agents to 100+ Turn Decision-Making via Reinforcement Learning

Forum topic · 小凯 · 2026-05-06

Summary

This post analyzes Odysseus (Shi et al., 2026, arXiv:2605.00347), a reinforcement learning framework that extends vision-language model (VLM) agents from short-horizon tasks (20-30 turns) to long-horizon decision-making of 100+ turns in games. It identifies two key bottlenecks: the variance catastrophe in credit assignment for critic-free RL methods like GRPO, whose group-relative advantage signals become noise as horizon grows, and the poor sample efficiency of training RL from scratch. Odysseus addresses these with two pillars: a lightweight turn-level critic paired with PPO that provides stable baseline signals without a full-size value network, and a pretrained VLM serving as an action prior that compresses the exploration space. Experiments in Super Mario Land show at least 3x improvement in game progress over frontier baselines, consistent in-game and cross-game generalization, and no degradation on standard VLM benchmarks. The post argues this represents a paradigm shift from SFT-first pipelines, where imitation caps performance at human level, toward RL-first training that can exceed human capability.

Odysseus: Scaling VLM Agents to 100+ Turn Decision-Making via Reinforcement Learning

This post analyzes the paper "Odysseus: Scaling VLMs to 100+ Turn Decision-Making in Games via Reinforcement Learning" (Chengshuai Shi et al., arXiv:2605.00347), covering the math behind long-horizon RL instability and the framework's two-pillar design.

1. Problem Structure: The Short-to-Long Horizon Gap

VLM agents have moved from short-horizon settings (20-30 turns) to long-horizon tasks requiring 100+ consecutive decisions. Existing approaches face a structural bottleneck:

| Method | Applicable horizon | Core limitation | Representative work | |:-------|:-------------------|:----------------|:--------------------| | Large-scale SFT | Any | Ceiling = human level; cannot surpass | Mainstream VLM agent pipelines | | Critic-free RL (GRPO/Reinforce++) | 20-30 turns | Variance catastrophe at long horizons | DeepSeek-R1, short-horizon reasoning | | PPO + Critic | 100+ turns | Requires stable value estimation | Odysseus |

Odysseus identifies and solves two key obstacles in scaling from short to long horizons: (1) the variance catastrophe in credit assignment, and (2) poor sample efficiency when training RL from scratch. The solutions are a turn-level critic and a pretrained VLM as an action prior, respectively.

2. Mathematical Framework: Credit Assignment and Variance Analysis

2.1 Return Estimation in Long-Horizon RL

For an episodic task with horizon $$T$$ , the agent maximizes discounted cumulative return:

G_t = \sum_{k=0}^{T-t} \gamma^k r_{t+k}

with discount factor $\gamma \in [0,1]$ . Policy gradient methods update via:

\nabla_\theta J(\theta) = \mathbb{E}_{\pi_\theta}\left[\sum_{t=1}^{T} \nabla_\theta \log \pi_\theta(a_t|s_t) \cdot G_t\right]

Core problem: the variance of $$G_t$$ grows linearly with horizon $$T$$ . At $$T = 100+$$ , Monte Carlo estimates are drowned in noise, making gradient directions unreliable.

2.2 Variance Reduction via a Critic

A critic decomposes the return:

G_t = \underbrace{V(s_t)}_{\text{baseline}} + \underbrace{(G_t - V(s_t))}_{\text{low-variance residual}}

The advantage function $$A(s,a) = Q(s,a) - V(s)$$ has far lower variance than raw returns. With single-step reward variance $\sigma_r^2$ :

\text{Var}(G_t) = \sum_{k=0}^{T-t} \gamma^{2k} \sigma_r^2 \approx \frac{\sigma_r^2}{1-\gamma^2} \quad \text{for large } T

Increasing $$T$$ from 20 to 100 raises effective variance roughly 5x; a critic reduces advantage variance by about an order of magnitude — the mathematical reason PPO stays stable on long-horizon tasks while GRPO diverges.

2.3 GRPO's Within-Group Variance Problem

GRPO estimates advantages via within-group relative ranking:

\hat{A}_i = \frac{r_i - \text{mean}(\{r_j\}_{j=1}^{G})}{\text{std}(\{r_j\}_{j=1}^{G})}

with group size $$G$$ (typically 4-16). In short-horizon tasks, sampled rollouts are correlated and within-group variance is manageable. But at 100+ turns:

Tiny differences in early decisions are exponentially amplified later
Return distributions within a group become extremely dispersed
Standardized advantage signals lose discriminative power

3. Odysseus: A Two-Pillar Architecture

3.1 Pillar One: Turn-level Critic

Odysseus uses PPO with the clipped surrogate objective:

L^{\text{CLIP}}(\theta) = \mathbb{E}\left[\min\left(\rho_t(\theta) \hat{A}_t, \text{clip}(\rho_t(\theta), 1-\epsilon, 1+\epsilon) \hat{A}_t\right)\right]

where $\rho_t(\theta) = \frac{\pi_\theta(a_t|s_t)}{\pi_{\theta_{\text{old}}}(a_t|s_t)}$ .

Instead of a full-size value network, Odysseus uses a lightweight turn-level value estimate $\hat{V}(s_t) = f_{\text{lightweight}}(\text{encoded}(s_t))$ — a small MLP or even a linear projection. In long-horizon tasks, precise absolute value estimation matters less than the relative ranking of state values, which a lightweight critic provides.

| Critic type | Params | Training cost | Long-horizon stability | Use case | |:------------|:-------|:--------------|:-----------------------|:---------| | Standard value network | Large (policy-scale) | High | Medium | General | | Turn-level lightweight | Small (1-10% of policy) | Low | High | Long-horizon | | No critic (GRPO) | None | Lowest | Low | Short-horizon |

3.2 Pillar Two: Pretrained VLM as Action Prior

Training RL from scratch is extremely sample-inefficient for long-horizon visual tasks. A pretrained VLM provides a structured action prior:

p_{\text{VLM}}(a|s) = \text{softmax}(W \cdot \text{VLMLLM}(s) + b)

encoding visual understanding (objects: characters, enemies, coins, obstacles), semantic associations ("enemy → jump", "coin → approach"), and action plausibility. The RL policy optimizes on top of it:

\pi_{\text{RL}}(a|s) = \frac{p_{\text{VLM}}(a|s) \exp(Q(s,a)/\tau)}{\sum_{a'} p_{\text{VLM}}(a'|s) \exp(Q(s,a')/\tau)}

with temperature $\tau$ balancing the prior and RL optimization. With action space $$|A|$$ , from-scratch RL explores $$O(|A|)$$ actions; the prior restricts exploration to a much smaller plausible subset, compressing the search space by orders of magnitude.

4. Experimental Validation

| Metric | Odysseus | Frontier baseline | Gain | |:-------|:---------|:------------------|:-----| | Average game progress | High | Medium | ≥ 3x | | Training stability | Stable | Diverges (long-horizon) | Qualitative | | Sample efficiency | High | Low | Significant |

Generalization was verified on three axes:

| Type | Test | Result | |:-----|:-----|:-------| | In-game | Different levels of the same game | Consistent improvement | | Cross-game | Different games (visual/rule differences) | Consistent improvement | | General domain | Standard VLM benchmarks (non-game) | Capabilities preserved, no regression |

A key finding: no catastrophic forgetting or capability narrowing — game training enhanced decision ability without harming general vision-language capability.

Ablations confirm both components matter: removing the critic (GRPO-style) drops performance significantly; removing the VLM prior also drops it sharply; a standard full-size PPO critic performs only moderately — the lightweight version suffices.

5. Systemic Reflection: Restructuring the Agent Pipeline

The standard pipeline Pretrained VLM → SFT → (optional RL) implicitly assumes: (1) SFT capability is RL's upper bound, (2) RL is only fine-tuning/alignment, (3) long-horizon skill comes from stacking short-horizon SFT. Odysseus challenges all three.

The restructured pipeline is Pretrained VLM → (optional SFT warm-start) → RL + Critic → Agent, where SFT only warms up task format and core capability comes from RL:

| Cost dimension | SFT-first | RL-first | |:---------------|:----------|:---------| | Data annotation | High (human trajectories) | Low (environment-generated rewards) | | Compute | Medium | Medium-high | | Final performance | Human level | Can exceed human | | Scalability | Poor (re-labeling needed) | Good (programmable environments) |

Open questions include reward design for real-world tasks, task-general critics, very long horizons (1000+ turns), and multimodal/continuous action spaces.

6. Conclusion

Odysseus extends VLM agents from 20-30 turn tasks to 100+ turn decision-making. The essence is not bigger models or more data, but a paradigm shift — from imitation learning to reinforcement learning, from a human ceiling to self-improvement. If this shift proves general, SFT-based VLM agent pipelines may need to rethink their technical roadmap.

Paper Details

Title: Odysseus: Scaling VLMs to 100+ Turn Decision-Making in Games via Reinforcement Learning
Authors: Chengshuai Shi, Wenzhe Li, Xinran Liang, Yizhou Lu, Wenjia Yang, Ruirong Feng, Seth Karten, Ziran Yang, Zihan Ding, Gabriel Sarch, Danqi Chen, Karthik Narasimhan, Chi Jin
arXiv: 2605.00347, cs.LG, May 1, 2026
Environment: Super Mario Land (100+ turn visual decision-making)

Key contributions: (1) first stable scaling of VLM + RL to 100+ turn decisions; (2) lightweight turn-level critic for long-horizon credit assignment; (3) pretrained VLM action prior for sample efficiency; (4) verified in-game, cross-game, and general-domain capability retention.

Odysseus: Scaling VLM Agents to 100+ Turn Decision-Making via Reinforcement Learning

Summary

Odysseus: Scaling VLM Agents to 100+ Turn Decision-Making via Reinforcement Learning

1. Problem Structure: The Short-to-Long Horizon Gap

2. Mathematical Framework: Credit Assignment and Variance Analysis

2.1 Return Estimation in Long-Horizon RL

2.2 Variance Reduction via a Critic

2.3 GRPO's Within-Group Variance Problem

3. Odysseus: A Two-Pillar Architecture

3.1 Pillar One: Turn-level Critic

3.2 Pillar Two: Pretrained VLM as Action Prior

4. Experimental Validation

5. Systemic Reflection: Restructuring the Agent Pipeline

6. Conclusion

Paper Details

Tags