Thank you for your valuable review. We give the following response accordingly:

W1: Theoretical contribution (Theorem 4.2) appears weak due to reliance on a strong similarity assumption (Definition 1), and lacks empirical validation of bias.

A1: Definition 1 provides a quantitative criterion: two actions are $\varepsilon$-bisimilar under a history $h$ if both the reward $r(h,a)$ and the transition distribution $P(·\mid h,a)$ differ by at most $\varepsilon$. Theorem 4.2 builds on this, showing that if $\varepsilon$-bisimilar actions are clustered and each individual advantage is approximated by the cluster mean $\tilde{A}$, then the resulting policy gradient bias $|\mathbb{E}\left[\nabla_\theta\log\pi_\theta(a\mid h)\bigl(A(a\mid h)-\tilde A\bigr(a\mid h))\right]|$ is bounded by $O(\varepsilon)$. This formal result guarantees that the clustering-induced bias remains small when ε is small.

In practice, ARIA uses this theoretical insight to cluster semantically similar actions—those with small $\varepsilon$—to reduce reward variance while controlling bias. This trade-off is validated empirically in Table 1 and 2, where ARIA consistently outperforms baselines. Moreover, Figure 5(b) shows faster loss convergence with reduced variance, further confirming the practical effectiveness.

W2: Questions about the choice of baselines and their relevance.

A2: As discussed in Section2 and 5, we select representative and competitive baselines from both offline and online learning paradigms that aim to enhance LLM agents in complex tasks through training.

• Offline baselines include behavior cloning (BC), trajectory-level preference learning (Traj-DPO), and step-level methods (Step-DPO and SPAG).
• Online baselines include hierarchical learning (Archer) and trajectory-based policy optimization (RAGEN).

These methods represent mainstream approaches in the field. By comparison, ARIA demonstrates superior performance by reducing reward variance and achieves faster and more stable reward growth across online iterations.

W3: Insufficient ablation studies on clustering choices such as embedding models and cluster threshold.

A3: We appreciate the suggestion. In addition to the ablations in Section 6.2 (on reward aggregation and decay factor $\gamma$), Section 6.3 (on base models), and Appendix B (on clustering threshold $\tau$), we further add analysis on the choice of embedding models. Results are as follows:

Findings:

(1) ARIA performs robustly with strong embedding models (text-embedding-3-small, Qwen3-Embedding), indicating robust performance across models.
(2) Performance drops with weak models (e5-large-v2), suggesting that embedding quality impacts the accuracy of semantic similarity and should not be too poor.

Q1: Possible applicability of the method to math reasoning tasks.

A4:
While this direction could offer additional insights, we would like to clarify that our focus is on addressing reward sparsity in open-ended language-action tasks with large action spaces. Nonetheless, in math reasoning tasks, semantically equivalent reasoning steps may differ in representative form, and ARIA’s semantic clustering and reward densification could potentially be beneficial. We are open to discussing this possibility further in the revision.

Q2: Marginal improvement of Qwen 1.5B in the Bargaining task.

A5: For Qwen 1.5B in Table 3, ARIA achieves an average improvement of +1.12. The smaller gain is due to the base model’s limited reasoning capability: in the two-player game setup, training data are collected via self-play, followed by evaluation against strong opponents (DeepSeek-V3, Claude 3.5, GPT-4o). Qwen 1.5B struggles during self-play due to its weak strategic reasoning, leading to suboptimal policies that are ineffective against strong adversaries, thereby limiting ARIA’s benefit in this case.

Q3: Generalizability of the method to other environments.

A6: We further evaluate ARIA on a more complex and multi-objective social interaction benchmark SOTOPIA[1]. SOTOPIA sets real social goals with complex intentions and evaluates LLMs from six dimensions such as believability and social rules. Using LLaMA3-8B-Instruct, we collect self-play trajectories on 400 tasks and evaluate on a held-out 50-tasks set (the maximum score is 10):

ARIA consistently improves both social alignment and task completion, indicating that our semantic clustering approach captures rich, intention-relevant structure even in more complex multi-agent dialogue environments.

[1]Zhou X, Zhu H, Mathur L, et al. Sotopia: Interactive evaluation for social intelligence in language agents[J]. arXiv preprint arXiv:2310.11667, 2023.

Thanks for the response. What I mean about the theory vs practice is, beyond the end result of the algorithm getting better results/convergence, can you check the \epsilon-bisimilar condition in your empirically fitted clusters? Are these scenarios really satisfying this for reasonable \epsilon? Otherwise, the theory and experiments would be operating in different regimes, and in that case I'm not sure how much the theory adds or explains.

Thanks for the embedding model ablations. It would be interesting to look at what the stronger embedding models are doing with the clustering that is better than the weaker embedding model, and maybe give a recommendation on how to choose one for a given task (if it's not just use text-embedding-3-small).

Thank you for your valuable review. We give the following response accordingly:

W1:Concern that intention clustering may overlook important aspects of language behavior such as tactics, fluency, and style beyond intent.

A1: In fact, ARIA considers not only high-level intent but also factors such as language tactics, sentence structure, and stylistic choices. The semantic projection in ARIA maps each action into a dense vector that inherently captures these rich features—strategy, intent, fluency, and style included. The clustering is then performed over these semantic vectors, making it a holistic semantic similarity. This helps ARIA generalize across subtle variations in expression. We appreciate the suggestion and will consider refining our wording in the revision to clarify this point.

W2:Request for analysis of performance saturation and the method’s potential ceiling after more training iterations.

A2: Thank you for this valuable suggestion. Understanding ARIA’s performance ceiling is indeed important. As shown in Table 1, ARIA's performance on the Bargaining dataset slightly drops from iter2 to iter3 (58.85 → 58.01), and Figure 3 shows that the reward improvement slows down notably in later iterations. This indicates diminishing returns over time.

We analyze that this is due to decreasing policy entropy as training progresses, which leads to weaker exploration and convergence to a local optimum—a phenomenon commonly observed in RL. Similar trends have been documented in recent literature [1][2][3]. We plan to include a more detailed discussion of ARIA’s performance plateau in future versions of the paper.

W3: Suggestion to test generalization of the method on out-of-domain environments, especially with discrete action spaces.

A3: To assess generalization, we evaluate models trained on single-agent tasks (Twenty. and Guess.) using ARIA in an out-of-domain environment with a discrete action space—ScienceWorld[4]. Results are shown below:

These results indicate that ARIA generalizes well to out-of-domain and discrete action settings, achieving a performance improvement from 11.11 to 13.03.

[1]Song Y, Yin D, Yue X, et al. Trial and error: Exploration-based trajectory optimization for llm agents[J]. arXiv preprint arXiv:2403.02502, 2024.

[2]Xiong W, Song Y, Zhao X, et al. Watch every step! llm agent learning via iterative step-level process refinement[J]. arXiv preprint arXiv:2406.11176, 2024.

[3]Cui G, Zhang Y, Chen J, et al. The entropy mechanism of reinforcement learning for reasoning language models[J]. arXiv preprint arXiv:2505.22617, 2025.

[4]Wang R, Jansen P, Côté M A, et al. Scienceworld: Is your agent smarter than a 5th grader?[J]. arXiv preprint arXiv:2203.07540, 2022.

Sincerely thank you for taking the time to review our paper. We are glad to know that our response addressed your concerns. Thanks for your engagement during the discussion!

Thank you for your valuable review. We give the following response accordingly:

W1 & Q2：Lack of online training experiments in adversarial settings to evaluate scalability and robustness.

A1: We extend online ARIA to adversarial environments (Bargaining and Negotiation), following the same settings as described in Section 5.3. Due to time constraints, we conduct 50 iterations. We evaluate the trained actor against GPT-4o on a held-out test set (N=240), and report results for iterations 10–50:

These results show that Online ARIA achieves faster and stronger reward improvement in dynamic multi-agent environments, surpassing ArCHer and RAGEN (which used 150 iterations) in just 50 iterations. We will include the full 150-iteration results in the final version.

W2: Skepticism about ARIA’s generalization to more complex tasks where intentions are hard to separate.

A2: We further evaluate ARIA on a more complex and multi-objective social interaction benchmark SOTOPIA[1]. SOTOPIA sets real social goals with complex intentions and evaluates LLMs from six dimensions such as believability and social rules. Using LLaMA3-8B-Instruct, we collect self-play trajectories on 400 tasks and evaluate on a held-out 50-tasks set (the maximum score is 10):

ARIA consistently improves both social alignment and task completion, indicating that our semantic clustering approach captures rich, intention-relevant structure even in more complex multi-agent dialogue environments. We will include the results in the final version.

W3: Concern about the assumption of discrete intentions, especially in linguistically nuanced multi-goal dialogues.

A3: In ARIA, the semantic projection embeds actions as dense vectors that encode various linguistic properties—including strategy, intent, and style. Clustering is performed over these vectors, enabling soft aggregation based on overall semantic similarity (including nuanced liguistic styles) rather than strict categorical intentions. This helps ARIA generalize across subtle variations in expression. We also evaluate ARIA on a more complex scenario, SOTOPIA and results in A2 show the effectiveness of ARIA.

W4: Concern about sensitivity to embedding quality and robustness of SplitScore in edge cases and dynamic settings.

A4: We conduct ablation experiments using embedding models of varying capabilities: Text-embedding-3-small (our paper), Qwen3-Embedding-0.6B (strong), and e5-large-v2 (weak). The results are as follows:

Findings:
(1) ARIA performs robustly with high-quality embeddings, confirming stable behavior across strong models.
(2) Performance drops with lower-quality embeddings, highlighting the need for good semantic representations. We will include this ablation and discussion in the final version.

W5: Literature and benchmark justification could be more comprehensive.

A5:
Thank you for the suggestion. We discuss the Natural Language Agent Benchmarks in Related Work and select four open-ended language action tasks with large action spaces to demonstrate ARIA’s ability to mitigate sparse reward issues in such settings. The chosen tasks cover both static (single-agent) and dynamic (two-player) interactions, ensuring evaluation comprehensiveness. We would like to clarify this motivation further and expand relevant citations in the final revision.

Q1: Question on how ARIA deals with multi-label or hierarchical semantics in latent goal structures.

A6: We further evaluate ARIA on a more complex and multi-objective social interaction benchmark SOTOPIA[1]. Results are in A2 and show ARIA can also handle complex multi-objective tasks.

Q3: Concern about ARIA's adaptability to concept drift in evolving language use.

A7: ARIA is inherently capable of adapting to concept drift. In offline settings, ARIA can be applied iteratively on new policies to re-align reward signals. In online settings, ARIA regularly updates the reward model, enabling it to accommodate shifts in action distributions due to evolving user preferences. Empirically, we observe that ARIA effectively reduces reward variance even as policy behavior changes, suggesting good adaptability to distributional drift.

Q4: Whether hierarchical clustering is a bottleneck for very large-scale training.

A8: ARIA clusters actions in the semantic space, where the number of meaningful clusters is not very large (e.g., 10–30 clusters in bargaining/negotiation, see visualization in Appendix I), making hierarchical clustering computationally feasible. Additionally, in complex environments like SOTOPIA, we apply SplitScore to automatically select an appropriate number of clusters (e.g., k=23), and observe consistent gains (see A2). Current results suggest that clustering is not a bottleneck.

[1]Zhou X, Zhu H, Mathur L, et al. Sotopia: Interactive evaluation for social intelligence in language agents[J]. arXiv preprint arXiv:2310.11667, 2023.

Thank you for your valuable review. We give the following response accordingly:

W1 & Q2：Concern about the sensitivity of the method to the choice of embedding models.

A1: We conduct ablation experiments using embedding models of varying capabilities: text-embedding-3-small (our paper), Qwen3-Embedding-0.6B (stronger), and e5-large-v2 (weaker). The results are as follows:

Findings:
(1) ARIA performs robustly with stronger embedding models (text-embedding-3-small, Qwen3-Embedding), indicating stable performance across embedding choices.
(2) Performance drops with weaker models (e5-large-v2), suggesting that embedding quality is critical for capturing accurate semantic similarity.

We will include this ablation study in the Appendix of the final version.

W2: Not clear how the method integrates with existing variance reduction techniques like Actor-Critic or PPO.

A2: We would like to clarify that ARIA is complementary to standard variance reduction techniques such as Actor-Critic and PPO-style losses. For example, Actor-Critic methods reduce variance by training a critic model to approximate the reward function $R$, learning a stable distribution. In contrast, ARIA reshapes the reward into $R'$ through aggregation, which naturally exhibits lower variance. This reshaped reward R' can also be used to train the critic model itself, potentially improving its stability. In fact, our Online ARIA implementation trains a reward model on $R'$ and demonstrates faster reward improvement in online iterations (Figure 3).

Q1: Question regarding why the variance appears unchanged in the bottom plots of Figure 4 after aggregation.

A3: The bottom two plots correspond to single-agent tasks, where agents perform poorly in early iterations (mostly scoring 0). As a result, the reward variance is inherently low and the impact of aggregation appears minimal in the figure. To show the effect of aggregation, we compute the reward variance before and after aggregation in the Guess and Twenty tasks after one iteration of ARIA:

This confirms that aggregation still significantly reduces variance in these tasks.

Q3: Suggestion to include visualizations of embeddings and resulting clusters for better interpretability.

A4:
Thank you for the suggestion. We provide clustering results for the Bargaining task in Appendix I. While the rebuttal format limits our ability to include figures, we will include detailed visualizations of both the embeddings and the resulting clusters in the revised version of the paper.