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

Forum topic · 小凯 · 2026-05-06

Summary

A detailed technical analysis of Odysseus (Shi et al., arXiv 2605.00347), a framework that extends vision-language model (VLM) agents from short-horizon (20-30 turn) tasks to 100+ turn sequential decision-making in games. The post explains why critic-free RL methods like GRPO suffer a variance catastrophe in long-horizon settings: Monte Carlo return variance grows with horizon length, drowning out the advantage signal. Odysseus addresses this with two pillars: (1) PPO combined with a lightweight turn-level critic that provides stable baseline signals at low training cost, and (2) using a pretrained VLM as an action prior that compresses the exploration space by orders of magnitude, dramatically improving sample efficiency. Experiments on Super Mario Land show at least 3x game progress over frontier baselines, with consistent in-game and cross-game generalization and no degradation on standard VLM benchmarks—no catastrophic forgetting. The author argues this signals a paradigm shift from SFT-first to RL-first agent pipelines, since SFT caps performance at human level while RL can surpass it. Open questions include reward design for real-world tasks, critic transferability, and horizons beyond 1000 turns.

Overview

This post analyzes Odysseus: Scaling VLMs to 100+ Turn Decision-Making in Games via Reinforcement Learning (Shi et al., arXiv:2605.00347), which extends vision-language model (VLM) agents from short-horizon settings (20-30 turns) to long-horizon scenarios requiring 100+ consecutive decisions.

The Problem: Short-to-Long Horizon Gap

| Method | Applicable horizon | Core limitation | |:---|:---|:---| | Large-scale SFT | Any | Ceiling = human level, cannot surpass | | Critic-free RL (GRPO/Reinforce++) | 20-30 turns | Long-horizon variance catastrophe | | PPO + Critic | 100+ turns | Requires stable value estimation |

Odysseus identifies and solves two key obstacles in scaling from short to long horizons: 1. The variance catastrophe in credit assignment 2. Poor sample efficiency when training RL from scratch

Why Critic-Free RL Fails at Long Horizons

Policy gradient methods maximize $G_t = \sum_{k=0}^{T-t} \gamma^k r_{t+k}$ , but the variance of the Monte Carlo estimate grows with horizon $$T$$ :

\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

A critic reduces variance by decomposing returns into a baseline plus a low-variance residual:

\[G_t = V(s_t) + (G_t - V(s_t))\]

GRPO's group-relative problem: GRPO estimates advantages via within-group normalization of rollouts. In short tasks, sampled outputs are correlated and variance is manageable. In 100+ turn tasks:

Tiny early decisions diverge exponentially later
Return distributions across group samples become extremely dispersed
Normalized advantage signals lose discriminative power

Odysseus: Two Pillars

Pillar 1: Lightweight Turn-level Critic

Odysseus uses PPO with a lightweight turn-level value estimate — a small MLP or linear projection rather than a full-scale value network. The insight: in long-horizon tasks, precise absolute value estimates don't matter; what matters is the ordering of relative values between states, which a lightweight critic provides at low cost and high stability.

Pillar 2: Pretrained VLM as Action Prior

Training RL from scratch is extremely sample-inefficient. A pretrained VLM provides a structured prior encoding:

Visual understanding (identifying characters, enemies, coins, obstacles)
Semantic associations ("enemy → jump", "pit → avoid")
Action plausibility (excluding absurd actions)

The effective action space shrinks from $$|A|$$ to $|A_{\text{valid}}| \ll |A|$ , compressing exploration by orders of magnitude.

Experimental Results

| Aspect | Finding | |:---|:---| | Game progress | ≥ 3x over frontier baselines | | Training stability | Stable vs. divergence for critic-free methods | | In-game generalization | Consistent improvement on unseen levels | | Cross-game generalization | Consistent improvement on different games | | Generic VLM benchmarks | No degradation — no catastrophic forgetting |

Ablations: removing the critic or the VLM prior causes significant drops; a standard full-size PPO critic yields only middling results, confirming the lightweight design suffices.

Systemic Implications: Restructuring the Agent Pipeline

The standard pipeline (Pretrained VLM → SFT → optional RL) assumes SFT provides RL's upper bound and that long-horizon capability comes from stacking short-horizon SFT. Odysseus challenges all three assumptions:

1. SFT's ceiling is human level; RL can exceed it 2. RL is not optional fine-tuning but the core capability source 3. Long-horizon capability requires dedicated RL training

The proposed RL-first pipeline: Pretrained VLM → optional SFT (warm-start) → RL + Critic → Agent.

Open Questions

Reward design for real-world ambiguous tasks (inverse RL, preference feedback)
Task-general, transferable value functions
Extremely long horizons (1000+ turns): hierarchical RL, options framework
Multimodal action spaces: continuous control, natural-language actions

Paper Details

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
Environment: Super Mario Land (100+ turn visual decision-making)