Problem
Yandex trains a booking agent for its assistant Alice AI: the user asks for a restaurant or a salon with certain features, and the agent searches, asks follow-up questions and completes the booking. Dialogues are long and there is no fixed sequence of tool calls. Standard GRPO scores only the whole trajectory. Scoring single steps makes GRPO compare incomparable steps and compute the advantages wrongly.
Example from the article: at step three, trajectory A makes a search call, B retrieves slots, and C is already booking the venue. The final reward does not say how good the third step was.
Solution in brief
HGRPO groups steps before averaging the reward, so only comparable steps share a baseline. The team tried grouping by dialogue-state features (each step in several weighted groups) and by a decision tree over shared context. Tree grouping raised goal achievement; state grouping raised the confirmation (truthfulness) metric.
Questions this case answers
- How to assign credit to intermediate steps of a multi-turn tool-using agent that is trained only from a delayed final reward
- How to group comparable steps of divergent trajectories so that their average reward is a meaningful baseline for each step
- How to assign credit to individual steps when training a multi-turn LLM agent with GRPO
- How to compute GRPO advantages when trajectories of a tool-using agent diverge and steps are not comparable
Tools and methods
- GRPO — baseline online RL method without a value model
- Verification + LLM judge reward — RLVR-style booking check plus a judge for honesty and product rules
- State-based grouping — steps grouped by dialogue features, with soft membership
- Tree-based grouping — steps grouped by decision-tree branches over trajectories
- LLM judge — offline evaluation of confirmation and goal achievement
Google or a one-time email code. No password.
