Sparse Rewards Can Self-Train Dialogue Agents (2025)

Abstract: Recent advancements in state-of-the-art (SOTA) Large Language Model (LLM) agents, especially in multi-turn dialogue tasks, have been primarily driven by supervised fine-tuning and high-quality human feedback. However, as base LLM models continue to improve, acquiring meaningful human feedback has become increasingly challenging and costly. In certain domains, base LLM agents may eventually exceed human capabilities, making traditional feedback-driven methods impractical. In this paper, we introduce a novel self-improvement paradigm that empowers LLM agents to autonomously enhance their performance without external human feedback. Our method, Juxtaposed Outcomes for Simulation Harvesting (JOSH), is a self-alignment algorithm that leverages a sparse reward simulation environment to extract ideal behaviors and further train the LLM on its own outputs. We present ToolWOZ, a sparse reward tool-calling simulation environment derived from MultiWOZ. We demonstrate that models trained with JOSH, both small and frontier, significantly improve tool-based interactions while preserving general model capabilities across diverse benchmarks. Our code and data are publicly available on GitHub.

## introduction large language models (llms) @xcite @xcite have shown a well-marked ability to follow instructions under various tasks. these advancements are often attributed to post-training fine-tuning based on human preferences. this includes multi-turn tool calling tasks where an llmbased agent must solve a task by interacting with both a user and a set of tools (or apis) @xcite . further task-specific alignment for tool-calling tasks can take the form of preference judgments. but these can be expensive to obtain. furthermore, there is usually a more 'crisp' notion of success for such tasks. specifically, was the right tool(s) or api(s) called with the right set of arguments? ideally, alignment should be optimized towards these sparse rewards. in this paper, we propose a self-alignment process josh (juxtaposed outcomes for simulation harvesting) that can be used to improve a model's performance on multi-turn tool calling by optimizing for tool/api completion using simulated rollouts of reward-conditioned conversations. we show that this method is general and can be applied to weak/small or frontier llms, though gains are significantly larger for the former. we also present a new tool calling benchmark, toolwoz, refashioning multiwoz2.0 @xcite to train and evaluate multi-turn tool calling effectively. josh utilizes a beam search inspired simulation approach, employing sparse rewards (in this paper corresponding to successful tool calls) to guide turn-by-turn generation and synthesize preferenceannotated examples. josh allows an agent to generate multiple responses at each conversation turn, exploring various trajectories through a conversation until a sparse reward (goal) is encountered along some path. upon reaching a goal, other beam candidates are pruned and further expansion proceeds only from that point. once a trajectory achieves all possible goals, all remaining trajectories are backtracked, logging unsuccessful paths as negative alignment samples and successful paths as positive ones. this process constructs alignment preference data solely from the model itself. when used to align that same model, we show it enhances model performance. tool use is a critical skill in llms @xcite ; however, there is a large disparity in tool-using capabilities across different model sizes, especially when involving them in multi-turn reasoning @xcite . furthermore, existing benchmarks either lack a real-world multi-turn setup @xcite or intentionally keep the agent's dialogue disjoint from underlying databases and focus more on tool selection @xcite . to demonstrate josh's capability to improve a model used in an agentic system through self-alignment, we introduce a new dataset toolwoz. derived from the taskoriented dialogue (tod) benchmark multiwoz, toolwoz is a multi-turn tool-based simulation environment where an agent model is assessed on its tool-calling capabilities by calling goal apis through collaboration with a user simulator. after self-alignment using josh on the toolwoz training set, a meta-llama3-8b-instruct (meta-llama, 2024) model exhibits a 74% increase in success rate and outperforms ppo @xcite . additionally, after josh self-alignment we see gpt-4o beats it's own baseline to become stateof-the-art on two separate benchmarks: toolwoz and τ -bench @xcite . to show that josh does not degrade general model performance, we evaluate a trained meta-llama3-8b-instruct model across three public benchmarks: mt-bench @xcite , τ -bench , and the lmsys-chatbot arena human preference predictions challenge (lin @xcite . our results confirm that the josh aligned model does not regress relative to its base model, despite its new specialized alignment. ## josh: juxtaposed outcomes for simulation harvesting in this section, we detail the two components of josh, our method for generating synthetic preference-annotated training data to enhance tooldriven multi-turn dialogue. we use the terms "tool" and "api" interchangeably. our approach for generating conversations uses an agent-simulator system and involves a turn-level beam search strategy combined with tool/api-calling reward pruning. unlike traditional token-level beam search, our method maintains multiple active multi-turn conversations (trajectories) over sequences of agent turns. from these synthetic conversations we create preference-annotated training instances. this involves extracting both supervised fine-tuning (sft) data and preference fine-tuning (pft) data. the sft data is derived from the optimal trajectory (or path) through the conversation tree, while the pft data includes pairwise comparisons of good and bad agent turns, facilitating more nuanced model training. ## toolwoz in this section, we introduce toolwoz, a dataset designed to train and benchmark an agent's capabilities in using api tools within a dialogue setting. toolwoz features an agent with access to various api tools that allow it to interact with a real database, engaging in dialogue with a user simulator. each conversation in the dataset is grounded in seed goals, which correspond to specific goal api calls. as illustrated in figure 2 , toolwoz significantly simplifies the analysis of task-oriented dialogue systems compared to earlier dst systems and the multiwoz database. in recent years, task-oriented dialogue systems were typically developed using a pipeline approach @xcite @xcite . these systems were divided into multiple components where each component was often modeled with a separate machine learning or natural language processing model, and the datasets used to build these systems, such as multiwoz, were designed accordingly. we propose transforming multiwoz into a tool-calling benchmark, which can drive the development and evaluation of modern dialogue systems in the llm era. to implement toolwoz, we developed apis for search and booking functionalities across four mul-tiwoz domains (restaurant, hotel, train, and attraction), resulting in seven distinct apis. each api's success is measured through a robust goal completion metric that tracks whether the system correctly invokes the appropriate external tools based on user inputs. this approach provides a more reliable measure of system performance compared to traditional metrics like inform and success rates. full api specifications and implementation details can be found in appendix a. ## related work simulation environments with sparse rewards were used by deepmind in their alphago @xcite and alphago zero @xcite works, enabling the two models to achieve superhuman performance in the game of go. in the alphago works, monte carlo tree search (mcts) in a selfplay simulation environment is used to intelligently explore the space of next possible moves and long term strategy. similarly, josh treats dialogue as a multi-turn game where it explores possible directions and while using sparse rewards to identify ideal paths through a conversation. with the advent of llms @xcite @xcite language agents have seen a sharp increase in effectiveness. agent reasoning has been significantly increased by approaches such as chain of thought (cot) @xcite and act/react @xcite by intelligently scaling inference time compute to reason about a problem before acting. additionally, function calling @xcite abilities have been increased against numerous benchmarks @xcite @xcite . in contrast with toolwoz, existing tool calling benchmarks lack the proper environment setup for multi-turn dialogue and apibased goal sets that josh requires. agentq (putta et al., 2024) -a contemporaneous work to this study -is a webagent training and inference process, has similar motivations of self learning using preference data however it has some key differences from josh. agentq uses mcts, a self-critique mechanism, and online searching of different pathways, while josh is a standalone data extraction algorithm that soley relies on arbitrary sparse rewards. additionally, agentq uses a test time inference strategy while josh purely extracts training data for finetuning models, a form of offline rl. josh focuses on tool calling multiturn dialogue while agentq is in the domain of navigating web agents. approaches such as star @xcite , quiet-star @xcite , and iterative reasoning preference optimization @xcite use downstream rewards based on reasoning to train or preference tune models for increased performance at test time. however, these approaches are focused on single turn output performance rather than a multi-turn dialogue setting. some approaches use rewards to train policies to help tod systems @xcite or extensive test-time search @xcite while josh simply produces data to finetune models rather than make test time changes. in this way josh is conceptually similar to decision transformers (dts) @xcite . dts is a form of offline rl that generates optimal sequences for fine-tuning by conditioning on the rewards, whereas josh uses these rewards to select optimal simuation rollouts. tree of thought (tot) @xcite and chain of preference optimizaiton (cpo) @xcite use search trees to optimizing the performance of cot reasoning. cpo extracts prefer-ence data from a search tree exploring cot reasoning using an llm to issue rewards at each sentence of a single turn response. on the contrary, josh uses sparse rewards in a multi-step simulation environment. the preference tuning paradigm emerged as a simpler alternative to @xcite , replacing the two-step process of reward modeling and rl-based policy learning. starting with dpo @xcite , variants like rs-dpo @xcite and orpo @xcite followed. while early methods required paired good-bad responses, kto @xcite enabled learning from unpaired preferences, which we use in this work. ## conclusions in this work, we devise josh, a self-alignment approach which uses sparse rewards to enable agentic models of all sizes to train themselves. we show that training on josh rollouts significantly increases performance on benchmarks assessing multi-turn dialogue and tool-calling ability while maintaining or improving general model performance. we show josh is general an can be applied to small medium and large models and provide considerable gains in performance. notably, we illustrate how frontier models can outperform themselves with josh to achieve state-of-the-art results on multiple tool-calling benchmarks. additionally, we present toolwoz, a multi-turn, tool-calling simulation dataset with sparse rewards to train and evaluate agent llms.