Agentic Reinforcement Learning with Implicit Step Rewards

🕒 Published (v1): 2026-01-01 · Source: ICLR · Venue: ICLR 2026 · link

Why this paper was selected

Alibaba DAMO (Huang, Li); implicit step rewards solve sparse-reward bottleneck in agentic RL

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

iStar is a credit-assignment framework for multi-turn LLM agent RL that eliminates the need for hand-annotated step labels by jointly training an implicit process reward model (PRM) with the policy via a multi-turn DPO objective. The implicit PRM generates dense step rewards measuring how much each action shifts probability mass relative to the old policy snapshot, which are combined with episode-level advantages for policy updates. iStar achieves state-of-the-art results on WebShop, VisualSokoban, and SOTOPIA while improving sample efficiency ~2× over vanilla RL.

Problem

Training LLM agents with RL suffers from three compounding difficulties: (1) rewards are sparse and delayed, creating hard credit-assignment across long multi-step trajectories; (2) trajectories are long and non-Markovian at the token level, inflating gradient variance; (3) environments are open-ended and often yield unverifiable rewards (e.g., social dialogues), blocking prior process supervision approaches that require either costly hand-labeled step annotations, LLM-as-judge consistency, token-level rewards (too fine-grained → high variance), or same-state grouping (rarely possible in language spaces).

Method

iStar alternates between two optimization targets each RL training step:

Implicit PRM update. Rollouts from the old policy \(\pi_{\theta_\text{old}}\) are ranked by an outcome reward verifier to form positive/negative trajectory pairs. The implicit PRM \(\pi_\phi\) is updated via a multi-turn DPO objective: $\(\mathcal{J}_\text{PRM}(\phi) = -\mathbb{E} \left[\log \sigma\!\left(\beta \log \frac{\pi_\phi(\tau^+|x)}{\pi_{\theta_\text{old}}(\tau^+|x)} - \beta \log \frac{\pi_\phi(\tau^-|x)}{\pi_{\theta_\text{old}}(\tau^-|x)}\right)\right]\)$ where \(\pi(\tau|x) = \prod_t \pi(a_t|o_{1:t}, x)\). The reference model is the current \(\pi_{\theta_\text{old}}\) (not a frozen initial model), and the MDP is modeled at the step (action-sequence) level rather than the token level.

Implicit step reward. For action \(a_t\) in a trajectory, the step reward is: $\(r_\phi(o_{1:t}, a_t) = \beta \log \frac{\pi_\phi(a_t|o_{1:t}, x)}{\pi_{\theta_\text{old}}(a_t|o_{1:t}, x)}\)$ This measures how much more probable the action is under the updated PRM than the old policy—positive values mark actions responsible for improvement, negative values mark ones to suppress.

Policy update. Step-level advantages \(A_S(a_t^i)\) are computed by normalizing implicit step rewards across all steps in the group. Episode-level advantages \(A_E(\tau_i)\) are computed from outcome rewards. The combined advantage is: $\(A(a_t^i) = A_E(\tau_i) + \alpha A_S(a_t^i)\)$ The policy is updated with a clipped importance-sampling surrogate (GRPO/RLOO/REINFORCE++ compatible), using step-level importance ratios \(\rho_\theta(a_t^i)\). No KL penalty is applied to allow free exploration. The implicit PRM is initialized from the base policy model (or a matched text model in VLM settings).

Key Contributions

• A label-free, general credit-assignment strategy for agentic RL based on implicit PRMs derived purely from trajectory preferences (outcome rewards suffice).
• A multi-turn DPO objective for online implicit PRM training, proved equivalent to a Bradley-Terry model with a step-wise reward function (Eq. 7–8).
• Step-level (not token-level) granularity, bridging the variance gap between outcome-only RL and overly fine-grained token-level PRMs.
• Plug-in compatibility with GRPO, RLOO, and REINFORCE++ without extra rollouts or annotations.
• Empirical demonstration across verifiable (WebShop, VisualSokoban) and unverifiable (SOTOPIA social dialogue) reward settings.

Results

• WebShop (Qwen2.5-7B): iStar (RLOO) achieves 93.6% success / 91.3% score vs. GiGPO 91.2%/91.2%, PRIME 84.1%/81.5%, vanilla RLOO 86.6%/89.3%; beats GPT-5 ReAct (37.5% success).
• VisualSokoban (Qwen2.5-VL-7B): iStar 91.7% success vs. GiGPO 91.2%, PRIME inapplicable, vanilla RLOO 85.6%.
• SOTOPIA hard self-chat (Llama3.1-8B): iStar GRPO 8.06 vs. best vanilla RL 7.92 (+14% relative over base 5.89).
• SOTOPIA hard GPT-4o-as-partner (Llama3.1-8B): iStar GRPO 7.16 vs. best vanilla RL 6.68 (+48% relative over base 5.82).
• Sample efficiency: iStar reaches vanilla RLOO's final WebShop score in ~105 steps (~2× fewer), reaching 94.7% score by step 165.
• iStar consistently improves all three vanilla RL algorithms (GRPO, RLOO, REINFORCE++) by 6.3% success rate on WebShop and VisualSokoban.

Limitations

• Still requires an outcome reward signal (verifier or model) to rank trajectories; the method reduces but does not eliminate dependence on reward supervision.
• Maintains two models simultaneously (policy + implicit PRM), increasing memory and compute relative to critic-free vanilla RL baselines.
• In multimodal settings (VisualSokoban), the implicit PRM must use a different architecture (text-only) than the VLM policy, complicating initialization and alignment.
• Theoretical guarantee in Eq. 7 assumes both trajectories start from the same state; credit assignment under trajectory pairs with distinct initial states is not formally justified.
• SOTOPIA evaluation uses GPT-4o as a judge (proxy for human judgment), introducing noise that is acknowledged but not fully controlled.

Relevance to Agentic AI / LLM Agents

iStar directly addresses the core bottleneck in training LLM agents end-to-end with RL: getting dense, reliable credit signals over long multi-step rollouts without human step-labeling. By grounding implicit step rewards in trajectory-level preferences (outcome rewards), iStar extends process supervision to open-ended environments with unverifiable rewards—a setting that blocks prior methods like GiGPO or PRIME. The self-reinforcing loop between the implicit PRM and policy is a practically significant training paradigm, as it avoids the separate reward-model training pipeline while remaining compatible with standard critic-free RL algorithms (GRPO, RLOO). This makes it directly applicable to the growing class of agentic systems (web agents, social agents, tool-using agents) where outcome rewards are available but step labels are not.