Sparse Rewards Can Self-Train Dialogue Agents

We would like to thank the reviewer for the feedback. We address each of the stated weaknesses below

1. Novelty. While it's true that the individual components like data rollouts, beam search, and preference fine-tuning have been studied, our work introduces a novel combination of these elements in the context of self-training dialogue agents using sparse rewards. Specifically, JOSH leverages sparse reward simulations to autonomously generate preference-annotated data without external human feedback, which distinguishes it from existing methods that often rely on dense rewards or human annotations.

In our paper, we discuss how JOSH:

• Integrates sparse rewards with beam search simulations to explore and harvest optimal conversation trajectories effectively.
• Generates both supervised and preference data from the agent's own simulations, enabling self-improvement in a way that hasn't been extensively explored.
• Demonstrates significant performance gains across models of varying sizes, including frontier models like GPT-4, showcasing the scalability and effectiveness of our approach.

We acknowledge that we could have more explicitly highlighted the novelty of our method in comparison to prior work. In the revised version, we will emphasize how JOSH differentiates itself and contributes uniquely to the field, providing a clearer articulation of its innovative aspects.

2. Experiments. In this paper we evaluate JOSH against two benchmarks, one introduced in this paper ToolWOZ (Table 2) and another external benchmark Tau-bench (Table 3). These two particular datasets were the only benchmarks used because they have critical aspects needed for JOSH to function: scenarios with multiple ground truth actions that can serve as sparse rewards. Even though the MINT[2] benchmark takes place in a tool calling mult-turn dialogue setting, it lacks a goal set of individual tool calls that can serve as sparse rewards for JOSH to function on, rather there is only a single solution that the bot is iterating towards. While it would be interesting to adapt MINT so JOSH can be applied, this task is beyond the scope of this paper. While we could adapt JOSH to perform on a web based tool using benchmark such as WebLinx[1] we aim in this paper to improve the ability of dialogue agents, thus making web navigation also out of scope for this paper.

Baselines. JOSH introduces a novel approach to sparse reward-based alignment and self-improvement specifically tailored for multi-turn dialogue agents utilizing tools. While there are existing self-alignment methods, most are not designed for dialogue agents or do not operate effectively in multi-turn settings. To the best of our knowledge, JOSH is the first method that enables dialogue agents to self-improve their tool-calling capabilities in a multi-turn conversational context without relying on external human feedback.

The approach outlined in "Trial and Error: Exploration-Based Trajectory Optimization for LLM Agents" (ETO) involves a behavioral cloning step that requires initial training on ground truth examples (human input). However, the core objective of our paper and JOSH is to "autonomously enhance LLM agent performance without external human feedback." Additionally, the ETO's contrastive training phase cannot be executed on closed-source LLMs such as GPT-4, which limits the models that can be trained with ETO.

Similarly, V-STaR: Training Verifiers for Self-Taught Reasoners offers a method for advanced self-training based on output success but is designed for single-turn outputs like GSM8K or MATH. Our paper focuses on techniques for solving multi-turn dialogue problems. While adapting V-STaR for multi-step self-improvement would be interesting, it is also beyond this paper's scope. Additionally, we were not able to find a code implementation of V-STaR which is another impediment for reproducing.

In our work, we provide a comprehensive baseline by experimenting with multiple training methods across various model sizes, including both small and frontier models. This thorough exploration demonstrates the scalability and effectiveness of JOSH, setting a new standard for future research in this area. Our focus on enhancing tool use within multi-turn dialogues distinguishes JOSH from other approaches and highlights its unique contribution to the field.

By establishing this baseline, we aim to facilitate comparisons in future studies and encourage the development of more advanced self-alignment techniques for dialogue agents. We believe that JOSH paves the way for new possibilities in creating autonomous, efficient, and capable dialogue systems.

Questions: The price to finetune gpt-4o is $25.000/1M training tokens and gpt-4o-mini is$3.000/1M training tokens. On average we trained from 3 million training tokens to 10 million training tokens in our experiments depending on the dataset and how many examples were used, so it cost anywhere from $75 to$250 to finetune gpt-4o.

We would like to thank the reviewer for their valuable feedback, we have addressed the questions/weaknesses stated below

1. Thank you for the helpful comments! We have spent considerable time writing out comments that further define and justify the choices made in the design of JOSH. We plan on shortening section 3 ToolWOZ and incorporating these additional definitions into the final version of the paper. A list of topics that we have further fleshed out include:

a. Reviewer 1, point 3 further defining JOSH’s average reward function and comparing this to other types of reward functions

b. Reviewer 2, point 1 further defining what a goal set is, how we use the goal set to enforce chronological execution, and the positive implications and insights of the way we track how goals have been executed by the agent.

c. Reviewer 2, point 2 explores the different ways JOSH could perform branching and why the design decisions that we made are optimal for the problem that we are trying to solve.

We hope that these additional insights further illuminate why certain methodological decisions were made and how they compare to alternative approaches.

2. Thank you for this point, as you can see in the reply to Reviewer 2, point 4, we have seen good results using other RL approaches such as KTO on smaller open source models. These results can be seen in Table 2 with the metal-llama-8B-JOSH-KTO model and is further explored in the Analysis sections 5.2 and 5.3. However, for closed sourced models (GPT) we are limited to only training using supervised fine tuning through their website. Thus to experiment with JOSH on larger or frontier models, we needed to use only SFT baselines. We supplemented this by including some experiments on different branching factors and how that affected SFT training (also seen in Table 2 however we agree that larger companies should allow more exploratory training procedures and it is likely that using KTO models such as GPT would see better results.

1. Thank you for pointing this out, indeed it is not clear. For the purpose of this work, our goal set per simulation is a set of APIs (or tools) that must be called with corresponding parameters. E.g., if a simulation for canceling a flight requires the ‘retrieve_reservation(confirmation_code=ABCDEF)’ API to be called with corresponding confirmation code, that is a goal and it is only achieved once called with the correct parameters. There are a number of considerations here with respect to agent behavior, goal set and the interaction with our beam search. First, our beam search is designed to follow paths once goals are hit, so this naturally will select for trajectories where goals are achieved earlier in the conversation. It is an open question whether this can be suboptimal, but changing the beam search strategy could potentially account for this. Once a goal is achieved, it is removed from the set, so the agent cannot continue to obtain rewards from making duplicate calls. Furthermore, we force an ordering on goals to ensure they are called in the right order. This ordering is enforced by ensuring that some apis require information that can only be found by making other api calls correctly. For example, the “book_train” api call requires a train_id, which can only be found by making a correct call to “search_train”. This way, we ensure that a “book_train” api call cannot be made correctly without first searching for the correct train. Extensions to the goal set and its dynamics are an interesting topic of future work.

2. We agree that the internal action breakup of an episode [conversation] happening between an agent and a user in ToolWoz may differ significantly and not have a clear one to one correspondence to action trajectories as they used to take place in MultiWOZ. Casting the interaction in terms of alternating natural language token sequence generation by the agent and the user naturally requires turn level branching for ToolWoz - if one were to enforce a strict agent action based framework that decomposes the notion of a turn, each token generation step by the agent would have to be considered an “action” ; this would both lead to unnaturally long “action” sequences and make the intuitive passing of control between agent and user a lower-frequency intermediate event that happens once every k actions, rather than being in natural lockstep with the granularity. Also, the user here is a part of the environment, so the user turn that follows an agent turn can be seen as a natural part of the environment’s state transition function. With ToolWoz , we were looking for an approximate example level correspondence to MultiWOZ in terms of the initial information as well as the goals, rather than exactly creating a one to one mappable replication of the action dynamics or trajectories that would take place in MultiWOZ.

Binary trees have a number of 2^h-1 leaf nodes where h is the height of the tree, since JOSH splits at the turn level we can expect t=log_2(max_branches)+1 to be the number of turns t before JOSH can no longer expand the tree. There are roughly 3 actions a per turn on average, so t=3a and thus the number of turns allowed before branching would stop when action splitting is t = (log_2(max_branches)+1)/3. Thus when max_branchs=8 which is used throughout the paper to keep costs reasonable (around $100) we could perform either t=4 turns while still splitting, or t=4/3 turns when splitting on actions. While splitting on actions may provide more diversity, over the course of a multi turn dialogue we can explore more possible paths deep in the tree for the same max_branches when splitting on turns.

In reference to Figure 2, thank you for pointing this out and we have revised the figure to reflect the correct system design and will revise this figure in the final version of the paper.

3. We plan to compress section 3 ToolWOZ in order to spend more time rigorously defining the JOSH process defined in both these replies and replies to the other reviewers into the final version of the paper. For a deep dive into the reward process, we have further outlined many details in points 1 and 2 of this comment, as well as the comment to Reviewer 1.

4. Thank you for this point and we agree wholeheartedly that other RL based methods should be explored further using this approach. For open source models we include the exploration of other RL approaches (metal-llama-8B-JOSH-KTO, in Table 2) and find better results than variants of supervised fine tuning. We also further explore the benefits of using KTO in the Analysis sections 5.2 and 5.3. However, for closed sourced models (GPT) we are limited to only training using supervised fine tuning through their website. Ideally, companies such as OpenAI would allow for more exploratory training techniques but in order to show that JOSH works for all sized models and frontier models we chose to take advantage of the limited training that was available to us.

q1. JOSH provides a baseline for sparse reward based self-improvement in multi-turn dialogue agents. Particularly when considering the improvement in tool calling capabilities, we provide experiments using multiple types of training and along various sized models in order to thoroughly explore this baseline approach so that others may compare to it in future works. Other self-alignment approaches do exist for dialogue agents, however most notable approaches are not built for a multi-turn setting nor for dialogue. We also target improvement of tool use in this multi-turn dialogue setting, which further distinguishes us from any other baseline approaches.

q2. We provide experiments with reflection using ReACT based prompts in both ToolWOZ and TauBench results, across all model sizes. We do find that reflection techniques enhances JOSH's effectiveness as all ReACT based models outperform themselves when trained on JOSH data.

1. We perform an additional analysis comparing the goal based user simulator to the ground truth human conversations in MultiWOZ. We evaluate across three dimensions (naturalness, conciseness, and redundancy) using prompts from the paper LLM-RUBRIC: A Multidimensional, Calibrated Approach to Automated Evaluation of Natural Language Texts. The prompts evaluate the user messages in an entire conversation, assigning a score 1-4 where 4 is the best. We take the average over all 450 conversations in the ToolWOZ test set. We use Claude Sonnet 3.5 as the evaluator. The results are as follows:

dimension human bot

naturalness 4 4

conciseness 3.98 3.94

redundant 3.59 3.42

As we see, both humans and the user simulator are scored as very natural. The conciseness of the user simulator is slightly worse than the human score, which we attribute to the tendency for the user simulator to be verbose in its replies. Finally, the redundancy score for the user simulator is worse than a human, but still achieves a score of 3.42. Our analysis shows that this drop is due to agent errors where information is re-requested, and the user simulator is more willing to reiterate information where humans are less likely to repeat critical information.

2. We have performed a deeper analysis of the API calls and where errors are arising with different models and we plan to include this in the final version of our paper. The table below shows the amount of failed api calls split by type of api. Notably, the search_train and search_attraction apis still have a large gap when comparing sft and kto trained models, where sft is far more likely to fail.

    Method book_train  search_hotel  search_train  book_hotel  search_attraction  book_restaurant  search_restaurant  
    base	83	77	84	59	96	49	47
    sft	56	44	81	36	77	32	36
    kto	45	49	50	41	40	27	31
   

To further investigate this phenomenon, we measured the frequency of required argument groups for search_train and search_attraction that sft failed to call. We observe that while search_train failed calls with “leaveAt” argument steadily decrease from base to sft, calls with the “arriveBy” argument actually slightly increase in failures with sft from base. This pattern is not consistent with kto training, however, where the failures in both sections decrease significantly from base. We find that this phenomenon is due to sft training commonly leaving out arguments when writing API calls, and in the case of “arriveBy” api calls, the “departure” parameter is commonly left out. KTO however avoids this pitfall by training on apis with too few parameters as negative examples, and is thus far more likely to include all parameters.

search_train failure

(base) [(['day', 'departure', 'destination', 'leaveAt'], 37), (['arriveBy', 'day', 'departure', 'destination'], 47)]

(sft) [(['day', 'departure', 'destination', 'leaveAt'], 31), (['arriveBy', 'day', 'departure', 'destination'], 50)]

(kto) [(['day', 'departure', 'destination', 'leaveAt'], 22), (['arriveBy', 'day', 'departure', 'destination'], 28)]

We observe a similar phenomenon in the search_attraction api, where arguments including “area” almost never drop. We observe that this is due to two reasons. First, the sft model often neglected to use the “type” argument alongside the “area” argument, choosing to often only fill in the “area”. Also, the “area” argument was commonly being filled in as “all” for many sft conversations even though this is not a valid value for the area parameter. The KTO trained model manages to avoid many of these pitfalls as well as these invalid apis are commonly found in the negative examples.

search_attraction failure

(base) [(['area'], 9), (['area', 'type'], 32), (['name'], 29), (['type'], 26)]

(sft) [(['area'], 8), (['area', 'type'], 30), (['name'], 21), (['type'], 18)]

(kto) [(['area'], 2), (['area', 'type'], 15), (['name'], 12), (['type'], 11)]

We plan to expand the error analysis in section 5.2 with these findings.

You are absolutely correct, and so we have just revised the PDF version to address all of the comments from reviewers! In reference to your comments, we have updated the paper in the following places:

1. Lines 410-418 to provide analysis relating to the goal based user simulator compared to ground truth humans
2. Lines 432-444 to provide additional analysis of API errors
3. Lines 133-142 defining why we chose our average reward functions and showing other options
4. Lines 486-494 adding relevant advancements in language agents for multi-turn dialogues into the related works.

We would like to thank the reviewer for their ongoing efforts!