We thank Reviewer 9Wzo for his/her constructive comments that will surely turn our paper into a better shape.

Q1 Could the author explain intuitively why the benefit of reduced action space outweighs the problem of extended episode length with sparse reward?

A1 Thank you for your thoughtful question. We believe this discussion is valuable and will significantly help readers better understand our work. We plan to add a dedicated discussion section on this topic in the revised version.

At first glance, action decomposition indeed extends the episode length, seemingly exacerbating the sparse reward problem. However, we can analyze this issue more deeply from different perspectives:

1. Efficiency of credit backpropagation. The increased episode length due to action decomposition could lead to inefficient training if using a 1-step TD, as credit would only backpropagate one step per training epoch. Fortunately, BAD can be combined with n-step TD or GAE to achieve efficient propagation comparable to action-level Bellman backup within a single training epoch. For this reason, our POAD implementation is based on GAE. We appreciate the reviewer's reminder and will explicitly state in future versions that BAD is best used in conjunction with GAE or N-step TD methods to avoid confusion and misuse.
2. Credit decay. While the extended episode length could cause exponential decay of credit strength based on the discount factor, which makes it difficult for sparse reward signals to act on actions/tokens in the early stages of an episode, BAD removes the intra-action discount factor. This theoretically prevents the exponential decay of signal strength caused by action decomposition. Our experimental results, where POAD significantly outperforms NTPO, confirm this point.
3. Credit estimation variance. Even with addressing the efficiency and decay issues, increased horizons often lead to higher variance in credit estimation. However, in linguistic action environments, the dynamics between intra-action tokens are strictly deterministic. In this case, we are reasonable to expect that the additional variance introduced by action decomposition would be much less severe than that in traditional RL problems with increased episode length.

We hope this discussion intuitively explains why the benefit of reduced action space outweighs the problem of extended episode length with sparse reward when using BAD. Besides, our experiments on the VirtualHome also empirically confirm this. When the agent only receives a binary reward signal upon task completion or reaching the maximum step limit (50 steps), our POAD still outperforms the action-level method, TWOSOME, despite such a sparse reward setting.

Q2 Conduct an ablation showing the intuition in Fig. 2 is actually true.

A2 We are very grateful for this insightful suggestion and we have conducted a case study/ablation for in-depth analysis to validate the effectiveness of BAD. Please refer to the Figure 3: Case Study section in meta-responses for detailed settings and experiemental results.

By comparing the credit assigned to each token in a symmetric (positive, negative) action pair by the BAD-learned critic in different states, our experimental results confirm that the BAD critic can effectively assign most of the credit to the key tokens while rarely influencing other irrelevant tokens. By investigating the volume of credits assigned to key tokens by POAD and NTPO, compared with the credit assigned to the entire action by TWOSOME, results show that the POAD enjoys a far smaller discrepancy than NTPO.

Q3 compare with ArCHer to further show that token-level Bellman update is better.

A3 We are very grateful to the reviewer for recommending this timely work. Although ArCHer [1] adopts sentence-level critics, it also aims to provide fine-grained token-level supervision for optimizing language agents in interactive (multi-turn) tasks. Upon further investigation, we found that its key idea for token-level credit assignment plays an intermediate role between NTPO and POAD. Thus, in our revised manuscript, we have incorporated ArCHer as a new baseline in our experiments with comparative analysis.

Please refer to the Figures 1 and 2: New Baseline, ArCHer and Corresponding Analysis section in meta-responses for detailed comparison between ArCHer and our methods, as well as preliminary experimental results. Thanks again for the reviewers’ valuable recommendation, we believe these comparisons and analyses involving ArCHer will better illustrate the advantage of our method as well as the research trajectory in the community toward providing finer-grained supervision for language agents.

Q4 Minor Issue: The colors of the lines are inconsistent throughout the paper.

A4 Thanks to the reviewer for his/her careful examination, we have adjusted the related figures and unified the color used in our updated version.

Q5 Lack of societal impact.

A5 We appreciate the reviewer's suggestion. In our updated version, we have added the following paragraph addressing the societal impact:

Social Impact. The advancements in RL for language agents can significantly enhance decision-making processes in various domains such as healthcare, finance, and autonomous systems. Improved decision-making can lead to better outcomes, increased efficiency, and reduced errors. However, we acknowledge that when optimizing agents using our method, language agents may potentially resort to unscrupulous means to maximize rewards, which could lead to potentially harmful results. Thus, we advocate for a more comprehensive consideration when designing the reward function, or combining it with safety-constrained RL methods to mitigate these risks.

[1] Zhou, Yifei, et al. "Archer: Training language model agents via hierarchical multi-turn rl." arXiv preprint arXiv:2402.19446 (2024).

Thank you very much for your recognition of our efforts.

Yes, ArCHer adopts sentence-level critics exclusively and does not utilize token-level critics. However, the absence of token-level critics does not always imply that there is no discount factor applied within sentences. In Section 3.4 of the original ArCHer paper, the part of "Low-level token actor," authors stated: "We update the token-level policy with the policy gradient computed via REINFORCE (also known as the Monte Carlo Policy Gradient)". This indicates that rather than approximating token-level credits with critic networks, they employ Monte Carlo estimation to backpropagate token-level credits from sentence-level advantage values, $A(s_c, a_t)$, which serve as terminal rewards (and thus bypass the need for token-level critic networks).

We also noted that in one instance provided by ArCHer, specifically in Equation (3), they applied a vanilla (relatively old) version [2] of REINFORCE that does not involve a discount factor (they didn't explain why). However, it is important to highlight that in most contemporary practices involving Monte Carlo estimation or REINFORCE, the use of a discount factor is standard for managing horizons and balancing bias-variance (e.g. $G_t=\sum_{k=0}^\infty \gamma^k r_{t+k+1}$, see Equation (13.8) in Section 13.3 and Equation (3.8) in Section 3.3 of [3]). Furthermore, considering that the authors claim ArCHer is a framework that can integrate with other reinforcement learning approaches, we decided to retain the discount factor in the REINFORCE process as depicted in Figure 1 of the global PDF for a more general representation.

Nevertheless, we have considered ArCHer without a discount factor, which aligns with our insights presented in the paper. We conducted an ablation study on this aspect, as illustrated in Figure 2 of the global PDF, i.e. the ArCHer-BAD variant in the right one. In this case, the performance of ArCHer should theoretically match that of POAD, as they share the same theoretical results of credit assignment. Unfortunately, due to the inherent challenges associated with extra network complexity and the difficulties of hyperparameter tuning, ArCHer still falls short of achieving the performance levels of POAD.

Thank you so much again for this valuable feedback, we will add this clarification along with Figure 1 of the global PDF in our later version.

[2] Williams, Ronald J. "Simple statistical gradient-following algorithms for connectionist reinforcement learning." Machine learning 8 (1992): 229-256.

[3] Sutton, Richard S., and Andrew G. Barto. Reinforcement learning: An introduction. MIT press, 2018.

We thank Reviewer 671a for his/her constructive comments that will surely turn our paper into a better shape.

Q1 BAD has a significant correlation with some existing token-level optimization methods [2][3] and hierarchical optimization methods [1]. Can the authors make a more in-depth comparison between BAD and these methods? Is there any equivalence between BAD and these methods? Is it just extending existing methods, such as [2][3], from single-turn to multi-turn?

A1 We appreciate the reviewer for recommending these relevant works. Firstly, [2] and [3] primarily focus on single-turn RL problems, performing decomposition and token-level optimization on single-step outputs. While these works, including [3] here, emphasize the importance of fine-grained token-level supervision, they didn’t take policy consistency into account (which has a minor impact on single-turn tasks). Our work, however, concentrates on multi-turn scenarios, where the discrepancy grows with the number of turns, making it an unavoidable challenge in multi-turn RL. Moreover, one of the baselines in our paper - the naive token-level Bellman backup behind NTPO - can be viewed as a direct extension of [2] and [3] from single-turn to multi-turn. BAD, then, is an improvement that further addresses the inconsistency issue. This highlights both the differences and connections between our method and [2][3]. Our experimental results demonstrate that resolving the inconsistency problem, beyond simply extending, has a significant improvement on the ultimate performance of language agents in multi-turn RL problems. We will incorporate these comparisons in our Related Work section.

As for ArCHer [1], we are very grateful to the reviewer for recommending this timely work. ArCHer aims to provide fine-grained token-level supervision for optimizing language agents in interactive (multi-turn) tasks. Upon further investigation, we found that its key idea for token-level credit assignment plays an intermediate role between NTPO and POAD. Thus, in our revised manuscript, we have incorporated ArCHer as a new baseline in our experiments with comparative analysis.

Please refer to the Figures 1 and 2: New Baseline, ArCHer and Corresponding Analysis section in meta-responses for detailed comparison between ArCHer and our methods, as well as preliminary experimental results. Thanks again for the reviewers’ valuable recommendation, we believe these comparisons and analyses involving ArCHer will better illustrate the advantage of our method as well as the research trajectory in the community toward providing finer-grained supervision for language agents.

Q2 This paper emphasizes that BAD can perform efficient and reasonable credit assignment at the token level, but the experimental section lacks in-depth analysis, such as case studies. Can the authors demonstrate the token-level credit assignment learned by the BAD method through a case study?

A2 We are very grateful for this insightful suggestion and we have conducted a case study in updated manuscript for in-depth analysis to validate the effectiveness of BAD. Please refer to the Figure 3: Case Study section in meta-responses for detailed settings and experiemental results.

By comparing the credit assigned to each token in a symmetric (positive, negative) action pair by the BAD-learned critic in different states, our experimental results confirm that the BAD critic can effectively assign most of the credit to the key tokens while rarely influencing other irrelevant tokens. By investigating the volume of credits assigned to key tokens by POAD and NTPO, compared with the credit assigned to the entire action by TWOSOME, results show that the POAD enjoys a far smaller discrepancy than NTPO.

Q3 Lines 201-203, the authors mention that the action space is reduced from exponential to polynomial compared to works like GLAM and TWOSOME. However, from Equation 16, it can be seen that the algorithm learned by BAD still samples each token from the entire vocabulary, which does not seem to change the action space?

A3 We apologize for the confusion. BAD does not change the action space. In lines 200-203, we intended to convey that, by using BAD, the critic can provide more fine-grained token-level supervision signals, i.e. the token-level advantage values as shown in Equation 16, for the language agent's policy updates, which reduces the complexity of policy optimization from exponential to polynomial. Specifically, before using BAD, we have an action-level signal, which is used to optimize a policy with an action space of $O(|V|^{|a|})$. After using BAD, we have $|a|$ signals, each guiding an optimization with a token space of $O(|V|)$. Essentially, BAD decomposes a large problem into several smaller problems, thereby reducing the complexity of solving it. Thank you for your comment, we acknowledge that our initial statement might have caused some confusion, and we will further clarify our statement in lines 200-203 based on this discussion to avoid any unnecessary confusion.

[1] Zhou, Yifei, et al. "Archer: Training language model agents via hierarchical multi-turn rl." arXiv preprint arXiv:2402.19446 (2024).

[2] Rafailov, Rafael, et al. "From 𝑟 to 𝑄∗: Your Language Model is Secretly a Q-Function." arXiv preprint arXiv:2404.12358 (2024).

[3] Zeng, Yongcheng, et al. "Token-level Direct Preference Optimization." ICML 2024

Dear reviewer 671a,

We sincerely appreciate the time and effort you dedicated to our work and we have made every effort to address your concerns in our rebuttal submission. Given that the discussion deadline is less than 24 hours away, we wanted to kindly inquire if you have any further comments or concerns regarding our responses. Your insights are incredibly important to us, and we are eager to ensure that all of your points have been adequately addressed. If you feel that our responses have addressed your concerns, we would greatly appreciate your consideration in reflecting this in the final evaluation of the manuscript.

Thank you once again for your time and support throughout this process. We look forward to hearing from you soon.

Best regards,

Authors

We thank Reviewer JxkT for his/her constructive comments that will surely turn our paper into a better shape.

Q1 The unclear formalism and notation errors.

A1 We apologize for the confusion caused to the reviewers and readers. Indeed, we recognize that the use of POMDP in our formulation was unnecessary, as our paper does not delve into discussions related to partial observability. The inaccurate use of POMDP and the resulting omissions have inadvertently introduced additional confusion and distraction for the readers. To address this issue, in the updated version of our manuscript, we have:

1. referring to TWOSOME, replaced the POMDP formulation with MDP and adjust all related notations accordingly. We believe this change will make our formulation and derivation more clear and concise.
2. after these modifications, thoroughly reviewed all notations and equations to ensure that all relevant variables are properly defined and clearly explained.

Q2 There is a well-known equivalence between time-discounted MDP and adding an auxiliary state  $s_0$ with zero reward and transition probabilities $T(s,s_0)=\gamma$ for every other state $s$. As far as I understand, it fits into the paradigm in the paper by postulating that additional transitions are added from completed actions only. Do authors have any additional insight into this?

A2 Yes, we agree with the reviewer's insight about the equivalence between adding the additional transitions for only completed actions, i.e., action-level, and our BAD paradigm. Meanwhile, we appreciate the reviewer providing us with another perspective to understand why removing the intra-action discount is necessary. Specifically, in environments with linguistic actions, the dynamics between intra-action tokens within an action are strictly deterministic. That is, given a token $w^j$ for $(s,w^{1:j−1})$ , we can only transition to $(s,w^{1:j})$. In this case, if we do not remove the intra-action discount, it would be equivalent to adding an extra transition for intra-action tokens, which contradicts the deterministic nature of linguistic action generation.

Additionally, we can consider the implications of setting different discount factors for intra-action and inter-action tokens from another perspective. Originally, the discount factor was used to balance short-term and long-term rewards, with a large discount factor typically applied in scenarios where actions within the horizon are strongly correlated. In our work, given the particularity of intra-action tokens—where meaningful environmental feedback can only be obtained if intra-action tokens can be combined into a valid action—it is crucial to encourage agents to generate highly correlated intra-action tokens. Therefore, it is reasonable to consider setting the intra-action discount factor to 1, then agents will evaluate each of its intra-action tokens based on the action-level feedback. This approach aligns with the core idea of solving specific MDPs using time-varying discount factors, as seen in works like [1].

Q3 Did the authors think about incorporating the discount factor trick into ReAct?

A3 Yes, we recognize the potential benefits of integrating different discount factors into distinct components of the language agent's outputs, such as actions and thoughts. Based on the following intuitions:

1. The thoughts do not directly affect the final state-action transition—only the final action does—instead, thoughts guide the generation to converge to specific low-level actions (they play different roles in interactive tasks).
2. We can remove the gamma in intra-action tokens since words later in an action may not be more expressive than earlier ones. However, thoughts usually present a progressive structure, i.e. content closer to the final action may be more closely related to the final action, which makes it reasonable to distinguish them from final actions, e.g. with a low discount factor.

For now, we have observed that discount factors significantly influence the final policy of language agents learned from RL algorithms. Thus, considering separate outputs with varying intentions in a ReAct-like agent, we believe applying different discount factors to these components could be beneficial, whether through heuristic methods or learning-based approaches. For instance, [2] proposed a gradient-based meta-learning approach to optimize the discounting ratio of future rewards, while [1] solves specific MDPs using time-varying discount factors. Both could be promising directions to explore in the future.

Q4 Figure 2 should be more readable.

A4 Thanks very much for the reviewer's suggestion. We are working hard to improve the readability of this figure. Figure 4 (b) in the meta-responses is a current version of this diagram, hopefully more readable than the previous one. Besides, to facilitate understanding the effects of BAD shown in this figure, we also conducted a case study (See the Figure 3: Case Study section in meta-response) to visually demonstrate the token-level credit assignment results learned by the BAD.

Q5 Typos and subfigures swapping issue.

A5 Thanks to the reviewer’s careful examination, we have addressed these typos and adjusted the figures in our updated version.

[1] Gan, Jiarui, et al. "Markov decision processes with time-varying geometric discounting." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 10. 2023.

[2] Xu, Zhongwen, Hado P. van Hasselt, and David Silver. "Meta-gradient reinforcement learning." Advances in neural information processing systems 31 (2018).

We thank Reviewer H4uQ for his/her constructive comments that will surely turn our paper into a better shape.

Q1 More baselines should be included for comprehensive analysis.

A1 We appreciate the feedback from H4uQ and also extend our gratitude to Reviewers 671a and 9Wzo for recommending the recent relevant method, ArCHer [1]. ArCHer aims to provide fine-grained token-level supervision for optimizing language agents on interactive (multi-turn) tasks. Upon further investigation, we found that its key idea for token-level credit assignment plays an intermediate role between NTPO and POAD. Thus, in our revised manuscript, we have incorporated ArCHer as a new baseline in our experiments with comparative analysis.

Please refer to the Figures 1 and 2: New Baseline, ArCHer and Corresponding Analysis section in meta-responses for detailed comparison between ArCHer and our methods, as well as preliminary experimental results. We believe the extra comparisons and analyses involving ArCHer will better illustrate the advantage of our method and the research trajectory in the community toward providing finer-grained supervision for language agents.

Q2 If you use full-scale finetuning instead of Lora, what do you expect? Could you experiment with this?

A2 We conducted an ablation comparing our method with the action-level baseline, TWOSOME, on both full-scale and LoRA fine-tuning settings, with results referring to Figure 4 (a) in our meta-responses.

1. Comparing POAD's performance under full-scale fine-tuning and LoRA fine-tuning, we observed consistent performance, indicating that POAD remains effective under full-scale fine-tuning. However, due to increased memory consumption with full-scale fine-tuning, we significantly reduced the batch size during training, leading to slightly reduced stability in the training process. This accounts for the observed larger fluctuations in the curves during full-scale fine-tuning compared to LoRA fine-tuning.
2. Contrasting the two methods under full-scale fine-tuning, POAD demonstrated greater advantages over the action-level baseline method compared to Lora fine-tuning. Potential reasons for this include: a) full-scale fine-tuning's heightened sensitivity, requiring higher precision and granularity of supervised signals compared to Lora; b) the further increase in demand for precision of supervised signals due to the drastically reduced batch size.

We greatly appreciate the reviewer for this valuable suggestion. These experimental results further underscore the importance of our approach, highlighting that in scenarios involving full-scale fine-tuning, fine-grained and precise supervision signals are more critical compared to situations involving LoRA fine-tuning.

Q3 How did you tune the baseline?

A3 Regarding the baseline, such as TWOSOME, we integrated its implementation into our code framework based on the official repository. Throughout this process, for fair experimental comparisons, we ensured the following:

1. Key components of the baseline method aligned with those in the original repository.
2. Be able to replicate the performance reported in the paper using the original hyper-parameters list in their papers.
3. Regarding the code framework, apart from necessary adaptations specific to the method, we maintained consistency in other aspects.
4. When tuning hyperparameters, we utilized the same search ranges to maintain consistency (we reused the search ranges as defined in TWOSOME).

Q4 How would this method work on standard NLP tasks?

A4 Theoretically, our method can also be applied to standard NLP tasks such as QA, writing, coding, etc (DataSciCoding in our experiments is a coding environment where agents can generate code freely). Notably, the most suitable application scenarios would be those language tasks involving multi-turn interactions (which language agents usually target). In multi-turn situations, our method's advantage in decomposing inter-action and intra-action credit assignments can be fully leveraged. For other single-turn tasks, in the worst-case scenario, our method would be similar to standard RL approaches with terminal rewards derived from environmental feedback or a reward model.

[1] Zhou, Yifei, et al. "Archer: Training language model agents via hierarchical multi-turn rl." arXiv preprint arXiv:2402.19446 (2024).

Dear reviewer H4uQ,

We sincerely appreciate the time and effort you dedicated to our work and we have made every effort to address your concerns in our rebuttal submission. Given that the discussion deadline is less than 24 hours away, we wanted to kindly inquire if you have any further comments or concerns regarding our responses. Your insights are incredibly important to us, and we are eager to ensure that all of your points have been adequately addressed. If you feel that our responses have addressed your concerns, we would greatly appreciate your consideration in reflecting this in the final evaluation of the manuscript.

Thank you once again for your time and support throughout this process. We look forward to hearing from you soon.

Best regards,

Authors