ARIA: Training Language Agents with Intention-driven Reward Aggregation
Authors: Ruihan Yang
Yikai Zhang
Aili Chen
Xintao Wang
Jiangjie Chen
Siyu Yuan
Deqing Yang
Yanghua Xiao
Venue: NeurIPS 2025 spotlight ()
Keywords: Language Agent
Agent Learning
Reinforcement Learning
Primary area: deep_learning

Abstract: Large language models (LLMs) have enabled agents to perform complex reasoning and decision-making through free-form language interactions. However, in open-ended language action environments (e.g., negotiation or question-asking games), the action space can be formulated as a joint distribution over tokens, resulting in an extremely large and combinatorial action space. Sampling actions in such a space can lead to extreme reward sparsity, which brings large reward variance, hindering effective reinforcement learning (RL). To address this, we propose **ARIA**, a method that **A**ggregates **R**ewards in **I**ntention space to enable efficient and effective language **A**gents training. ARIA aims to project natural language actions from the high-dimensional joint token distribution space into a low-dimensional intention space, where semantically similar actions are clustered and assigned shared rewards. This intention-aware reward aggregation reduces reward variance by densifying reward signals, fostering efficient and effective policy optimization. Extensive experiments demonstrate that ARIA not only significantly reduces gradient variance, but also delivers substantial performance gains of average 9.95% across four downstream tasks (e.g., negotiation and text-based games), consistently outperforming strong offline and online RL baselines.

ARIA: Training Language Agents with Intention-Driven Reward Aggregation
Ruihan Yang 1, Yikai Zhang2.04 Aili Chen Xintao Wang Siyu Yuan 18 Jiangjie Chen Deqing Yang! f Yanghua Xiao 2.0
1. School of Data Science,Fudan University, Fudan University ByteeDance Seed
2, College of Computer Science and Artifcial Intelligence, Fudan University (rhyang17, alchenne,,, alccenn2e.angdeeqie... yangdeqing, shawyhjefudan, edu.cn en
(syyuan21, yyzkkkgg222mm fudan edu. [[jiangjiecy@byyeednec...
Project Page: https://aria- github.i
Abstract
Large language models (LLMs) have enabled agents to perform complex reasoning and decision-mann maaiin through free-form language interactions. However, in open- ended language action environments (e.g., negotiation or question-asking games), the action space can be formulated as a joint distribution over tokens, resulting exponentially large action space. Sampling actions in such space can lead to extreme reward sparsity, which brings large reward variance, hindering effective reinforcement learning (RL). To address this, we propose ARIA, method that Aggregates Rewards in Intention space to enable efficient and effective language Agents training. ARIA aims to project natural language actions from the high- dimensional joint token distribution space into a low-dimensional intention space, where semantically similar actions clustered and assigned shared rewards. This intention-awar reward aggregation reduces reward variance by densifying reward signals, fostering better policy optimization. Extensive experiments demonstrate that ARIA not only significantly reduces policy gradient variance, but also delivers substantial performance gains of an average of 9.95% across four downstream tasks, consistently outperforming offline and online RL baselines.
1 Introduction
Large language models (LLMs) have demonstrated strong capabilities in text comprehension and generation, enabling the development autonomous agents that operate through natural language, commonly referred to as language agents [1: 2; 3]. Language agents are increasingly expected to interact with environments through language-driven actions to accomplish diverse tasks, such as web navigation [4; 5], text-based games [6: 7; 8), and negotiation [9; 10]. These tasks often require long- horizon planning and reasoning to achieve high-level goals, posing significant challenges for current language agents [11; 12; 13; 14; 15]. According to the structure of the action space, language agent tasks can be broadly categorized into constrained action space tasks and open-ended language action tasks. The former requires agents perform actions from a predefined, discrete, and verifiable action set, where language serves as template or command interface to structured environments [16; 17]. In contrast, the action space of open-ended language action tasks comprises free-form natural language utterances without striet validity constraints [18; 19]. These tasks introduce unique challenges: 1) Agents must generate diverse, context-sensitive language actions that dynamically influence
'Equal Contribution. Corresponding authors.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

other agents or the environment. 2) The open-endedness of language actions gives rise to a vast, unstructured, and highly strategic action space, requiring agents to reason, adapt, and optimize beyond fixed patterns. Given these challenges, we pose the following research question: How can we enhance the performance of language agents in open-ended language action tasks?
Reinforcement learning (RL) is widely used to enhance language agents in complex tasks by enabling them to learn through interaction and feedback [20; 21]. However, in open-ended language action settings, RL faces serious challenges due to extremely sparse rewards caused by exponentially large action space, where actions are represented as token sequences. Given a vocabulary of size V and an average sequence length L. the action space scales as Ve, resulting in combinatorial and exponential explosion. Existing methods directly assign environmental rewards by averaging or decaying. Yet these are inadequate for open-ended tasks, where sampling based methods such as PPO [22] and REINFORCE [23] must search vast, unstructured space under sparse and delayed rewards. This leads to high variance in reward estimation and inefficient policy optimization.
To address these challenges, we propose semantic projection, which projects actions from the high-dimensional token space into low-dimensional intention space, enabling reward aggregation across semantically equivalent actions. LLM agents' actions often reflect underlying intentions, which are far fewer than token combinations. For example. the utterances "I will concede first in order to encourage my opponent to compromise" and "By taking the initiative to compromise, aim to prompt my counterpart to do the same." convey the same intention of prompting compromise through concession. By grouping such actions under shared intentions, we reduce the action space from Dc to intention space C, where |C] < | This transformation reduces variance by densifying sparse rewards, and facilitates more efficient policy optimization.
Building on semantic projection, we propose ARIA, a method that Aggregates Rewards in Intention space for efficient training of language Agents. ARIA maps natural language actions into a task- specific intention space via semantic projection, enabling reward aggregation across semantically similar actions to stabilize and improve policy learning. To automatically construct the intention space C, ARIA applies hierarchical clustering [24] over sentence embeddings and adaptively adjusts the clustering granularity. then aggregates rewards for actions sharing similar intentions and uses REINFORCE [23] to optimize the policy over this compressed space. We evaluate ARIA on four language action tasks, including two single-agent games (Guess My City, 20 Questions) and two adversarial games (Negotiation, Bargaining). Experimental results show that: /) ARIA significantly reduces reward variance, enabling stable training and improved policy gradient efficiency; 2) consistently outperforms offline and online RL baselines, achieving average improvement of 9.95% across all tasks.
In summary, our key contributions are as follows: 7) We propose the operation of semantic projection, which projects actions from the nigh-dimensional token sequence space into a compact intention space, effectively mitigating reward sparsity in free-form language action tasks; 2) Built upon semantic projection, we design ARIA, principled approach for training language agents with intention-driven reward aggregation; 3) We conduct extensive experiments on both single-agent and adversarial tasks, showing that ARIA reduces reward variance, accelerates convergence, and outperforms existing offline and online RL baselines.
2
Related Work
Natural Language Agent Benchmark Recent studies have introduced evaluation tasks for lan- guage agents requiring long-horizon planning and strategic reasoning in multi-turn, goal-driven settings, including social conversations [25], strategy games (e.g., Werewolf[26], Avalon[27]), economics-bas scenarios (e.g., bargaining[18) 18; 19], negotiation[19), and text-based games (e.g., Taboo[28], Guess My City[8], 20 Questions(8], Ask-Guess((9)). In this work, we focus on text-based games (Guess My Ciry, 20 Questions) and adversarial tasks (Bargaining. Negotiation). These settings require dynamic strategy adaptation, balancing short- and long-term goals, and complex reasoning, offering challenging benchmarks for evaluating LLM agents' planning and decision- making..
Semantic Clustering Semantic clustering partitions samples into categories based on semantic similarity, typically by first extracting representations (e.g., embeddings), then applying clustering algorithms such as k-maans [30], hierarchical clustering [24], or DBSCAN [31]. In ARIA, actions

---

Trajectory T
Reward Aggregation
Offline REINFORCE
are selling one product that is worth no less then $80 to you potential buyer
Description: You
Intention Space C
Objective:
Exploitation
Resistance
Bargaining
V A Log r (a
Semantic Projection
Hello Bob, I'm excited to offer
you amazing
will
Policy Model
Alice
sell to you $130
You are being so greedy !I was hoping to get the product lower price. Would consider selling it for $85
Aggregate Rewards
Bab
history
Advantage A
not comfortable seiling the product for 585, I'm willing make counteroffer. How about we meet in the middle at 592.50?
T1
Reward: Ri
Avg. Aggregated Rewards R
Alice
Oun,, ... Reward: An
Figure 1: Illustration of ARIA. ARIA first lets agents interact to collect trajectories. Then it performs semantic projection and aggregates reward in the intention space, and finally updates the policy using the aggregated rewards.
are embedded and clustered into intentions using hierarchical clustering, which offers flexible post hoc granularity control and captures hierarchical semantic relations for coarse-to-fine to-neee strategy modeling.
Training Language Agent with Reinforcement Learning Language agents often face ambiguous goals and sparse rewards, requiring adaptive long-term planning [1; 2: 3], which challenges decision- making. Reinforcement learning (RL) provides a principled framework to address these challenges, with existing methods falling into two categories: offline methods [12; 28; 13; 14; 26; 32], which pre- collect trajectories and apply postpprocessing (e.g., DPO [33], KTO [34]); and online methods [22; 20; 35; 36), which alternate between sampling and policy updates. However, the high-dimensional action space in free-form language tasks exacerbates reward sparsity and variance, hindering RL training. To mitigate this, adopt offline RL setup with reward aggregation and REINFORCE [23], improving learning stability and efficiency.
Method
We present an overview of ARIA in Figure 1. First, we construct the intention space using semantic Granularity
clustering ($3.2), where the optimal granularity is determined by Reward-Oriente Selection ($3.4). Next, high-dimensional actions and observations are projected into the intention space through semantic projection, enabling reward aggregation ($3.3). Finally, the aggregated rewards are used to optimize the policy efficiently via offline REINFORCE ($3.5).
3.1 Task Formulation
In this paper, we select two types of open-ended language action tasks, single-agent and two-agent adversarial games, the testbed. We formulate the tasks as a partially observable Markov decision process (POMDP) M = AS, T, where S is the global state, AA is the action space of natural language actions, O is the observation, T is the transition function, R is the reward function, and y is the discount factor. In the single-agent setting, an agent P interacts with the environment by performing actions over time. At each step t, the agent receives an observation or under state st and maintains a history h; = {01, ai...., 0t-1, 0r) The agent then selects an action a, T- (4)) conditioned on this history. The state s, subsequently transitions $ according to the transition function T : S x A 4 S. When reaches the terminal condition, the environment returns a reward R. The objective of the agent to maximize the expected cumulative reward at the end of the episode based on the policy gg. In the adversarial setting, two players P E (PI, P2) take turns performing actions. In state 8t, player P; selects an action a; ~ .; ht), } is the history of observations and actions, and is derived from the state 8, and the opponent's 's action dt. The state 8, then transitions to 8+41 according to the transition function T SSS A S. When the terminal condition is met in St, the environment
where h4 = {0), .i,.... 0t- 1, 04-1, )
3

---

returns a reward R to each player. Each player P; aims to maximize the expected reward by the end of the episode based on their policy n;.
3.2 Intention Space Construction
construct a latent intention space using clustering. Given the action space A and observation space O, each element A U O is embedded into a semantic vector using pre-trained encoder 6 D:A O + R.. We apply hicrarchical agglomerative clustering [37] to partition the embedding space into k clusters, forming the intention space C* (sce Appendix D for details). The number of clusters & is selected via reward-oriented granularity selection ($3.4).
3.3 Reward Aggregation
Based on the intention space C* we define a clustering function Cj : :AUG UA -> [k] that maps each element to cluster index. At each step the action and observation are mapped to cluster labels ā = (ax) and o c* (ot), respectively. Given the history ha {aı, .1...., 1t-1, Ot-1), the
corresponding label sequence
h4 ((c(aa)),((o))....... (.(c--)))))))))))))) eo (0(-))))
We aggregate rewards across history-action pairs that share the same semantic intention. The trajectory reward R is assigned to intermediate steps using temporal discounting: R(h,, ae) = > R, where is the discount factor. For each intention pair (h, ū), we compute the aggregated return by averaging over history-action pairs that map to it:
((09 (h, ā)
Σ
R(b,, at),
s
where Sn,a = [(h,, an) (b.) = h, cx (at) à} denotes the set of history-action pairs associated with intention (h, a). The aggregated return ((()) (he. āe) is used as the advantage estimate A(h,, as) for policy optimization.
3.4 Reward-Oriente Granularity Selection
Semantic clustering helps compress the free-form, un- structured space of natural language actions and ob- servations. However, selecting the appropriate granu- larity & remains challenging. For example, in the con- text of negotiation, we compute standard clustering metrics Siilhouette Score [38], Calinski Harabassz Index [39], and siriess-Bouldin Index [40] across
Normalized Metrics
1.0
Recip. DBI
Best Cluster:
Score: 1,00
* CHI
AVG
0.4
0.2
different configurations. In Figure 2, these metrics tend to favor overly coarse groupings due to the high similarity among actions, overlooking fine-grained distinctions that are critical for our task (see details of metric calculations in Appendix E).
0.0
15 Number of Clusters (k)
Figure 2: Clustering quality measured by SC, CHI. the reciprocal DBI and the average of three metrics. After normalization and averag- ing, = achieves the highest overall score.
To address this, we propose a reward-oriented gran- ularity selection mechanism that assesses whether further splitting clusters yields meaningful reward change. Unlike traditional metrics based on geometric structure (i.e., distance in embedding space), our method aligns with the RL objective by directly evaluating the impact on reward aggregation.
SplitScore Let & E [2, denote all possible granularity levels. We use SplitScore to select the optimal granularity k*, defined as SplitScore(k) E(h,, | R a.) ((0) a:) represents the reward change for all (he, at) pairs when the number of clusters changes from & to k 1, and D is the collection of all (he, az) pairs
óg [D where dz
a4)

---

Automatic Stopping Criterion To select the optimal granularity k", we define an early stopping mechanism based on SplitScore. Given threshold c 0 and a window size r', we stop splitting when SplitScore(j) < for all j E [k. k + 7] as k increases. The selected l: is then taken as k We prove Appendix that SplitScore is bounded above a monotonically decreasing function. When SplitScore remains below the threshold, further splitting has minimal impact ō indicating that the rewards fe(0)) (he, az) are nearly unchanged and do not significantly affect the training process. Thus, we select the smallest & that meets the stopping condition to realize better space compression.
3.5 Offline REINFORCE with Aggregated Reward
We use the offline REINFORCE algorithm [23] to optimize the policy. Formally, let go(a 8) denote the policy parameterized by 0 and assign the aggregated reward R(() (he, āe) to A(he, ARIA optimizes the model by maximizing the following objective:
hd) A(he, an)
J(0) = E
Σ 1=0
log (
4 Theoretical Analysis
In this section, we theoretically show that intention clustering-based aggregation of the rewards in ARIA reduce the variance of the gradient descent while maintaining small bound of bias, thus improving training stability and efficiency.
4.1 Background
Let A(he, az) be the original advantage of (he, ae) and (x) be the cluster label as- signed to instance x E A U O under the granularity k, we define (h,, ā.) ((c((ar)) (.) (a(::,))) co(or1)), ex(a)) and calculate the cluster-averaged reward for (h,, āe) as R(h,, ā,) To E Eih, Ríh,, āz), where R(he, āe) is the original reward of (he, āc). Then we assign R(h, āe) to the advantage (he, az) as A(he,
4.2 Main Theorem
We first establish that cluster- based aggregation reduces both the total variance the policy gradient algorithm and the variance of the policy gradient. We give the following two lemmas.
Lemma 4.1. Let denote the aggregated advantage, then Var(A) I Var(A).
Lemma 4.2. Given the single-sample policy gradient estimator V log To h) A(h, a), the variance is reduced when using the aggregated advantage Å. Specifically, Var(V, log up Á) s Var( 9 log Te A).
We leave the proof in Appendix G. Building Lemma 4.2, show that the variance reduction by aggregation improves the convergence properties of offline REINFORCE.
Theorem 4.1 (Variance-Improoed Convergence). Given N i.i.d. trajectories in train set, let Mt) At be an estimator of the true gradient g. Define o²
0 N Em E. Vo log (a)
Var(V, log A). Then, we have || 91|2=
E, Vo log Fo(af | ht) A; is the gradient estimator. The empirical gradient is EN Let o² Var [E Vo log no(a, h+) At). By expectation linearity and trajectory independence, the vari- ance of the empirical gradient is [llø - =ll2] o By Jensen's 's inequality [41], we get EE [ll@ glla] < VN
Proof. Let g E[gi] be the expected gradient for the i-th trajectory, where
In this paper, 0.01 and 10. Ablation study c is provided in Appendix J.
5

---

Intuitively, because clustering reduces o, supposing we want I/ gl < e, convergence to within e requires fewer samples, or equivalently, enables the use of larger step sizes for the same error tolerance. We then analyze the bias introduced by reward aggregation. To formalize this, we first give the notion of e-bisimulation.
Definition 1 (e-Bisimulation). Actions a, a' are said to be e-bisimilar if, for all states 8, Ir(h, a) r(h, a')l S e, Drv (P(: a,,), h a')) I e, where the total variation divergence Drv (P(: h, h, P( h. d)) measures how different the two distributions are over next states when different actions and a' are taken at the same history h.
Theorem 4.2 (Bounded Bias via e- e-Bisimulation), Suppose the actions in each cluster are E-bisimilar
Then,
Vo log mo(a (A(,, a) - A(h, a)) I ((E).
Proof 8- e-bisimulation ensures that value differences within a cluster satisfy ah, (h, d')l S
25 implying that cluster means differ by at most O(e). Since V log ι is bounded, the inner product bias is O(s).
In summary, by using conditional expectations and variance decomposition, we prove that replac- ing original advantages A with cluster-averaged advantages À removes the intra-cluster variance E (A C)) lowering the total variance of the policy gradient estimate. Provided that the expec- tation remains approximately unchanged, this variance reduction leads to more stable training and faster convergence. It allows larger optimization steps without divergence and increases the utility of each sample, explaining why cluster-smootie advantages yield smoother learning curves.
5 Experiments
5.1 Experimental Setup
Baselines We select both online and offline methods as baselines. For offline methods, we include:
1) Behavior Cloning (BC) that trains the policy using successful trajectories. 2) Trajectory-
DPO [12], which trains langugae models using successful and failed trajectories. 3) Step-wise
DPO [13], which employs success/failure labels the action level based on simulation outcomes. 4) SPAG [28]. which designs a discounted reward and uses offline PPO [22] for optimization of
policy gradients. For online methods, we select: /) Archer [20], which utilizes a hierarchical reinforcement learning framework. 2) StarPO [42], which applies GRPO [35] for policy optimization. Implementation details of baselines are in Appendix I.I.
Tasks We evaluate ARIA in both single-agent and adversarial environments (see Appendix H for details). For the single-agent setting, we consider two tasks: /) Twenty Questions [8], a dialogue task where the agent plays the role of guesser, aiming to identify a hidden word selected from a list of 157 candidates by asking up to twenty yes-no questions. The Oracle responds with "Yes" "No" or "Invalid Question". The agent receives a final reward R 1 upon correctly guessing the target word, ending the episode; otherwise, the reward remains 0. 2) Guess My City [8], a similar multi-tum turli-turnnnn task where the agent tries to identify a hidden city from list of 100 candidates within twenty questions. The agent can ask any type of question and receives frrm-form responses, not limited to yes/no answers. For the adversarial setting, we consider two competitive tasks: /) Bargaining [43], two-player game where Alice and Bob take turns proposing how to divide a fixed amount of money over a finite time horizon. As the game progresses, each player's s payoff is discounted by a player-specific discount factor. If the game ends without an agreement, both players receive zero payoff. Otherwise, the discounted payoffs for Alice and Bob are given by PA and pp. 2) Negotiation [43], two-player task where seller (Alice) and buyer (Bob) negotiate the price of product with true value. Alice and Bob each have subjective valuations. Over a fixed time horizon, the players alternate offers: at odd stages, Alice proposes a price and Bob decides whether to accept; at even stages, Bob proposes and Alice decides. If a price is accepted, the utilities for Alice and Bob are given by UA, uB. If no agreement is reached, both receive zero utility.
Evaluation For the single-agent environments, following ArCHer [20]. we evaluate ARIA on a subset of N tasks from Twenty Questions and Guess My City. We report the average final reward, defined as N Σmn T[R = 1]. where RG denotes the final reward for the i-th trajectory. We set N = 200 for each environment. For the adversarial environments, following GLEE [43], we evaluate ARIA across 48 game configurations. In each configuration, the agent plays as either Alice or Bob against fixed opponents, with each setting repeated N = 25 times. In Bargaining, the goal is to achieve a higher payoff than the opponent. In Negotiation, the objective is to sell at higher price

---

Table Main results on adversarial games. The best results are bolded, and the second best ones are underlined. The metric is the average win rate.
Bargaining
Negotiation
Methods
GPT-4o
Deepscek-V3
Claude-3.5
AVG.
GPT-4o
Deepseck-V
Claude-3.5
AVG.
Vanilla Model
30.14
24.05
33.72
29.30
37.92
36,94
40.08
38.31
Offline
Baselines
BC
46.92
40.64
55.64
47.73
31.92
40.06
32.34
34.77
Traj-wise DPO
46.77
45.58
47.57
46,64
35.57
35.68
35.38
35.54
Step-wise DPO
48.91
55.48
46.00
50.13
36.33
41.56
49.17
42.35
SPAG
30.68
37.26
22.43
30.12
25.83
33.86
33.65
31.11
Online Baselines
ArCHer StarPO
43.78
47.35
53,94
48.36
35.00 38.55
37.84
34.64
35.83
33.24
28.77
42.63
34.88
36,00
43.87
39.47
Ours
ARIA Iter 1)
51.54
55.26
52.66
53.15
45.65
42.69
49.02
45.79
ARTA ( Tter 2)
$3.60
67.33
55.62
58.85
47.46
45.08
48.93
47.16
ARIA [ter 3)
58.66
55.83
59.55
58.01
46.48
50.50
49.42
48.80
(as the seller) or buy lower price (as the buyer). We let ARIA play both roles (Alice and Bob) against various opponents and compute the average win rate each role, counting each successful completion of the task objective as a win. Specifically, the average win rate for Alice in Bargaining is defined WA N Ei =i=1 TprLA > Pt, where PA and PB denote the discounted payoffs for Alice and Bob, respectively. The definition is symmetric for Bob. For Negotiation, the average win rate for alice is defined as WA = & Ei= Ifu;A > u. where u and un represent the utilities of Alice and Bob. This is again symmetrie for Bob.
Models We use 1arnna---B--nstttere [44] as the policy model. For each language action, we obtain its semantic embedding using sest--mbbeddnng---smaadd [45]. Additional ablation results on alternative embedding models are provided in Appendix K. In single-agent environments, Oracle is simulated with GPT-4. In adversarial settings, employ opponent models from different families, including GPT-4o 40pt-44-2002-08--80 DeepSeek-Chal (DeepSeek-V3) [48].
[46], Claude 3 (claude-3+ sonidde----sonee -5-sonnet- (00240220220 [47], and
Implementation Details For each scenario, we gather 1,000 games and update the policy using the trajectories. Specifically, in single-agent scenarios, the actor interacts directly with the Óracle (Le., the environment). For adversarial scenarios, we employ self-play to collect competitive interaction data from both players. To evaluate whether ARIA can consistently improve the policy, we perform three iterations. In each iteration, we collect another 1,000 games using the updated policy and conduct new round of training. Additional implementation details are provided in Appendix I.
5.2 Results
Table 2: Main results on single-agent games. The best results are bolded, and the second-best ones are underlined. The metric is the average reward.
ARIA significantly improves policy perfor- mance. As shown in Table 1, in the adver- sarial tasks, ARIA achieves the highest aver- age win rate in both Bargaining and Negoti- ation, surpassing offline and online baselines by 9.67% and 9.83%, respectively. Similarly, in the single-agent tasks (Table 2). ARIA outperforms all baselines by an average of 9.82%. Existing offline and online RL meth- ods both rely on action sampling and reward assignment, where agents interact with the environment, collect action samples, and as- sign rewards to those actions. This approach works reasonably well in small action spaces, where repeated sampling provides stable and accurate reward estimates. However, in open- ended language action tasks, where agents act through natural language, the action space
Methods
Twenty.
Guess.
AVG.
Vanilla Model
27.50
13,50
20.50
Offine Baselines
BC
27.50
5.50
16.50
Traj- wise DPO
27.00
17.50
22.25
Step-wise DPO
27.50
11.50
19.50
SPAG
13.00
19.75
Online Baselines
ArCHer StarPO
26.00
16.25
27.50
10.50
16.00
Ours
ARIA (lter 1)
28.00
29.00
28.50
ARIA (lier
29,50
32.00
30.75
ARIA (lier
34.50
36.09
35.25

---

Twenty Questions
Guess My City
StarPO
StarPO
-14
ArCHer
-14
ArCHter
Reward
Reward
-16-
-18
-18
20:
20
0
50
100
150
5D
100
150
lterations
Iterations
(a) Reward over Iterations on Twenty Ques- (b) Reward over Iterations Guess My City. tinns.
Figure 3: (a) and (b) show the reward curves of ARIA and other online methods over iterations on the Twenty Questions and Guess My City respectively.
grows exponentially VC, given a vocabulary of size V and an average sequence length L. In such vast spaces, each sample typically receives only a binary reward signal, and the sample size 'N" is much smaller than the action space, leading to highly sparse and noisy reward signals and making accurate credit assignment challenging. ARIA addresses this by introducing reward aggregation in the intention space, which reduces reward variance and significantly improves learning performance.
ARIA continuously improves policy through iteration. After confirming that ARIA significantly outperforms the baselines. we further investigate its performance under iterative updates. As shown in Table I and Table 2, ARIA achieves additional gains of 3.27% and 1.85% after two and three iterations, respectively. This suggests that reward aggregation effectively reduces variance while preserving essential discriminative signals for policy learning, reflecting favorable bias-variance trade-off. It further enhances sample efficiency and mitigates the risk of premature convergence caused by excessive smoothing, demonstrating that reward aggregation can deliver stable and cumulative performance improvements.
5.3 Extending to Online ARIA
Settings We first perform reward aggregation using pre-collected trajectories. The aggregated rewards are then used to initialize point-wise reward model (RM), implemented as Llama-3.1- 8B-Instruct [44], consistent with the policy model. Subsequently, the policy interacts with the environment to dynamically generate new samples, which are scored by the RM to update the policy. Additionally, the RM is periodically updated with the latest collected data, allowing it to evolve alongside the policy. We conduct the online ARIA two single-agent games to conveniently observe reward at each iteration. Detailed parameter settings are provided Appendix I.2.
Results As shown in Figure 3, ARIA achieves faster reward improvement and consistently higher re- turns across iterations compared to existing online methods (ArCHer and StarPO). This improvement stems from two key advantages: 1) Reward aggregation provides an initial dense and low-variance reward signal, accelerating early-stage policy learning. 2) The dynamic RM update ensures alignment between the reward function and the evolving policy, preventing drift and reward misalignment common in static settings. Together, these factors enhance both sample efficiency and reward shaping accuracy, leading to faster and more stable policy improvement.
Analysis
6.1 Reward Aggregation Significantly Reduces Reward Variance
We show variance change before and after reward aggregation Figure 4. As shown Figure 4a, reward aggregation markedly reduces the fluctuation range of action rewards. The original binary reward distributions are highly polarized, with values mostly concentrated near 0 or I. In large action space, most actions sampled only once, and the corresponding binary reward is directly assigned to each action, resulting high reward variance. By contrast, after reward aggregation, actions within the same cluster share a common reward, which significantly smooths the distribution and reduces variance. Figure 4b further demonstrates that reward variance decreases across all four tasks, highlighting the effectiveness and necessity of reward aggregation in stabilizing policy learning.
8

---

Reward Variance
Barg.
0.2
Raw
Nego.
Aggre.
Twenty.
0.1
Guess.
Aggre
0.0
0.3
0.6
0.9
0.0
Nego.
Barg. Guess. Twenty,
Reward
Games
(a) Reward Distribution
(b) Reward Variance
Figure 4: (a) illustrates the distribution of rewards. (b) presents the change in reward variance.
6.2 Reward Aggregation Improves Policy Optimization
To evaluate whether reward aggregation improves training efficiency, we first compare the policy loss curves under different reward shaping strategies Figure 5b. The results show that ARIA, A, which applies semantic-level reward aggregation, accelerates loss reduction compared to the vanilla REINFORCE baseline. This indicates that shaping the reward through aggregation provides stronger learning signal, enabling faster policy updates and improved sample efficiency in offline training. We further observe that, despite converging to similar loss levels, the methods exhibit substantial differences in downstream performance. As shown in Figure Sa, ARIA outperforms other variants by 17.91% and 13.80% on the bargaining and negotiation tasks, respectively. We attribute these gains to the complementary effects of reward decay and reward aggregation: Reward decay introduces temporal structure that helps assign credit to early-stage actions, but plays limited role in reducing signal noise. contrast, reward aggregation substantially lowers reward variance by assigning shared signals to semantically similar actions, thereby improving the quality of gradient estimation. This variance reduction enables more stable and efficient optimization and plays a central role in enhancing policy performance in open-ended language action settings.
60
ARIA
w/o Aggre.
35
Aggre. &
Y ARIA
Win Rates
w/o Y
w/o Aggre. &
w/o Aggre.
Loss
45
20
30
5
Barg.
Nego.
100
500
900
Games
Training Steps
(a) Ablation of ARIA win rates
(b) Ablation of ARIA on loss (smoothed)
Figure 5: Ablation of ARIA. (a) shows win rates on adversarial games and (b) shows training loss curves under different ablation settings in adversarial games.
6.3 Generalization of ARIA Other Models
Table 3: ARIA on Qwen2.5-7B-Instre and Qwen2.5-1.5B-Instruee
Methods
Bargaining
Negotiation
AVG.
Qwen2.5-7BB --ssttutt
Vanilla
37.92
35.50
36.71
ARTA
65.96
47.06
56.51 (+19.8 1)
Qwwn2.5-1.5B-Innee
Vanilla
0.02
18.22
9.12
ARIA
0.01
20.47
10.24 (+1.12
In Section 5.2, show that ARIA achieves significant improvements on further assess the transferability ARIA, we apply it to the Qwen models (Qwen2.5-7B-Insstt [49] and Qwen2.5-1.3 1-.2255-1.BB-Istetee [49]) and conduct comparative experiments two adversarial games' As shown in Table 3, observe that altering the base model consistently yields improvements. This
To
All the settings the those in Section 5.

---

suggests that our reward aggregation approach is model-agnostie and independent of specific architec- tural features pretraining data of the underlying language models. We attribute this generalizability to the shared structural properties in the semantic spaces learned by large-scale language models. By performing aggregation in the intention space, ARIA leverages these commonalities to reduce reward variance while preserving task-specific discriminative signals.
7 Conclusion
In this paper, we address the core challenges of reinforcement learning in open-ended language action tasks, where agents must operate exponentially large action spaces and learn from sparse, delayed rewards. To tackle the resulting high variance in policy optimization, we introduce semantic projection, a novel intention-aware framework that maps natural language actions from the high-dimensional token space into a low-dimensional intention space. This projection enables reward aggregation across semantically similar actions, effectively densifying sparse rewards and reducing gradient variance. Built on this idea, we propose ARIA, which automatically discovers task-specific intention structures via hierarchical clustering and integrates the aggregated rewards into REINFORCE for efficient policy learning. We further provide a theoretical analysis showing that replacing original advantages with cluster-averaged advantages reduces intra-cluster variance, thereby lowering the overall variance of the policy gradient and improving learning stability. Exten- sive experiments across four diverse tasks including both single-agent and adversarial two-agent games-demonsee demonstrate that ARIA improves training stability, accelerates convergence, and consis- tently outperforms strong offline and online RL baselines. Our findings highlight the importance of structure-aware reward shaping in scaling reinforcement learning for language agents in open-ended environments.
10

---

Acknowledgement
We appreciate the support from the Chinese NSF General Program (No.62572129), Major Research Plan NNo.92270121... We also acknowledge the use of an icon from Flaticon' and thank its creators for providing this visually appealing design.
References
[1] Lei Wang, Chen Ma, Xueyang Feng, Zeyu Zhang, Hao Yang, Jingsen Zhang, Zhiyuan Chen, Jiakai Tang, Xu Chen, Yankai Lin, et al. A survey on large language model based autonomous agents. Frontiers of Computer Science, 18(6):186345, 2024.
[2] Junyu Luo, Weizhi Zhang, Ye Yuan, Yusheng Zhao, Junwei Yang, Yiyang Gu, Bohan Wu, Binqi Chen, Ziyue Qiao, Qingqing Long, et al. Large language model agent: A survey on methodology, applications and challenges. arXiv preprint arXiv:2503.21140 2025.
[3] Theodore Sumers, Shunyu Yao, Karthik Narasimhan, and Thomas Griffiths. Cognitive architec- tures for language agents. Transactions on Machine Learning Research, 2023.
[4] Izzeddin Gur, Hiroki Furuta, Austin Huang, Mustafa Safdari, Yutaka Matsuo, Douglas Eck, and Aleksandra Faust. A real-world webagent with planning, long context understanding, and program synthesis. arXiv preprint arXiv:2307.128555 2023.
[5] Shuyan Zhou, Frank Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Tianyue Ou, Yonatan Bisk, Daniel Fried, et al. Webarena: A realistic web environment for building autonomous agents. arXiv preprint arXiv:2307. 13854, 2023.
[6] Ruoyao Wang, Peter Jansen, Marc-Alexandre Côté, and Prithviraj Ammanabrolu. Scienceworld: Is your agent smarter than 5th grader? arXiv preprint arXiv:2203.075400 2022.
[7] Yikai Zhang, Siyu Yuan, Caiyu Hu, Kyle Richardson, Yanghua Xiao, and Jiangjie Chen. Timearena: Shaping efficient multitasking language agents in time-aware simulation. arXiv preprint arXiv:2402.0577 2024.
[8] Marwa Abdulhai, Isadora White, Charlie Snell, Charles Sun, Joey Hong, Yuexiang Zhai, Kelvin Xu, and Sergey Levine. Lmrl gym: Benchmarks for multi-turn reinforcement learning with language models. arXiv preprint arXiv:2311.18233 2023.
[9] Tim Davidson, Veniamin Veselovsky, Martin Josifoski, Maxime Peyrard, Antoine Bosselut, Michal Kosinski, and Robert West. Evaluating language model agency through negotiations. arXiv preprint arXiv:2401.045330 2024.
[10] Federico Bianchi, Patrick John Chia, Mert Yuksekgonul, Jacopo Tagliabue, Dan Jurafsky, and James Zou. How well can llms negotiate? negotiationarena platform and analysis. arXiv preprint arXiv:2402.05863, 2024.
[11] Bodhisattwa Prasad Majumder, Bhavana Dalvi Mishra, Peter Jansen, Oyvind Tafjord, Niket Tandon, Li Zhang, Chris Callison-Burch and Peter Clark. Clin: A continually learning language agent for rapid task adaptation and generalization. arXiv preprint arXiv:2310. 231..00444 2023.
[12] Yifan Song, Da Yin, Xiang Yue, Jie Huang, Sujian Li, and Bill Yuchen Lin. Trial and error: Exploration-based trajectory optimization for 1lm agents. arXiv preprint vrXiv:2403.02500 2024.
[13] Weimin Xiong. Yifan Song, Xiutian Zhao Wenhao Wu, Xun Wang, Ke Wang, Cheng Li, Wei Peng, and Sujian Li. Watch every step! IIm agent learning via iterative step-level process refinement. arXiv preprint arXiv:2406.111 11176, 2024.
[14] Pranav Putta, Edmund Mills, Naman Garg, Sumeet Motwani, Chelsea Finn, Divyansh Garg, and Rafael Rafailov, Agent q: Advanced reasoning and learning for autonomous ai agents. arXiv preprint 240..0799.. 2024.
"nttps://ww. http://www..aiccccooooomo

---

[15] Ruihan Yang. Jiangjie Chen, Yikai Zhang, Siyu Yuan, Aili Chen, Kyle Richardson, Yanghua Xiao, and Deqing Yang. Selfgoal: Your language agents already know how achieve high-level goals. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies SertggiissVlliueii (Volume 1: Long Papers), pages 799-819, 2025.
[16] Mohit Shridhar, Xingdi Yuan, Marc-Alexandre Côté, Yonatan Bisk, Adam Trischler, and Matthew Hausknecht. Alfworld: Aligning text and embodied environments for interactive learning. arXiv preprint arXiv:2010.03768. 2020.
[17] Shunyu Yao. Howard Chen, John Yang. and Karthik Narasimhan. Webshop: Towards scalable real-world web interaction with grounded language agents, 2023.
[18] Mike Lewis, Denis Yarats, Yann N Dauphin, Devi Parikh, and Dhruv Batra. Deal no deal? end-to-end learning for negotiation dialogues. arXiv preprint arXiv: 2017.
[19] Eilam Shapira, Omer Madmon, Itamar Reinman, Samuel Joseph Amouyal, Roi Reichart, and Moshe Tennenholtz. Glee: A unified framework and benchmark for language- economic environments. arXiv preprint arXiv:2410.05254 2024.
[20] Yifei Zhou, Andrea Zanette, Jiayi Pan, Sergey Levine, and Aviral Kumar. Archer: Training language model agents via hierarchical multi-turn rl. arXiv preprint arXiv:2402.1 19446, 2024.
[21] Yifei Zhou, Song Jiang, Yuandong Tian, Jason Weston, Sergey Levine, Sainbayar Sukhbaatar, and Xian Li. Sweet-rl: Training multi-turn Ilm agents on collaborative reasoning tasks. arXiv preprint arXiv:2503. 15478, 2025.
[22] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
[23] Ronald J. Williams. Simple statistical gradient- algorithms for connectionist reinforce- ment learning. Machine Learning, 8:229-256, 1992.
[24] Joe Ward Jr. Hierarchical grouping to optimize an objective function. Journal of the American statistical association, 58(351): 58(301): 1963.
[25] Xuhui Zhou, Hao Zhu, Leena Mathur, Ruohong Zhang, Haofei Yu, Zhengyang Qi, Louis- Philippe Morency, Yonatan Bisk, Daniel Fried, Graham Neubig, et al. Sotopia: Interactive evaluation for social intelligence in language agents. arXiv preprint arXiv:2310.
2023.
[26] Rong Ye, Yongxin Zhang, Yikai Zhang, Haoyu Kuang, Zhongyu Wei, and Peng Sun. Multi- agent kto: Reinforcing strategic interactions of large language model in language game. arXiv preprint arXiv:2501. 14222, 2025.
[27] Jonathan Light, Min Cai, Sheng Shen, and Ziniu Hu. Avalonbench: Evaluating Ilms playing the game of avalon. arXiv preprint arXiv:2310.05036, 2023.
[28] Pengyu Cheng, Tianhao Hu, Han Xu, Zhisong Zhang, Yong Dai, Lei Han, Xiaolong Li, Self play-ng adversarial language game enhances IIm reasoning. Advances in Neural Information Processing Systems, 37:126515--22544 15255443,, 2024.
[29] Dan Qiao, Chenfei Wu, Yaobo Liang, Juntao Li, and Nan Duan. Gameeval: Evaluating Ilms on conversational games. arXiv preprint arXiv: 10032, 2023.
[30] Stuart Lloyd. Least squares quantization in pem. IEEE transactions on information theory, 129-17179,137, 1982.
[31] Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu, et al. A density-based algorithm for discovering clusters in large spatial databases with noise. In kdd, volume 96, pages 226-231, 1996.
[32] Jinhe Bi, Yifan Wang, Danqi Yan, Xun Xiao, Artur Hecker, Volker Tresp, and Yunpu Ma. Prism: Self-pruning intrinsic selection method for training-fres multimodal data selection. arXiv preprint 2rXiv:2502.12111 2025.
[33] Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems, 36:53728-5341 2023,
12

---

[34] Kawin Ethayarajh, Winnie Xu, Niklas Muennighoff, Dan Jurafsky, and Douwe Kiela. Kto: Model alignment prospect theoretic optimization. arXiv preprint arXiv:2402.01332 2024.
[35] Zhihong Shao, Peiyi Wang, Qihao Zhu, Rumxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Y Wu, et al. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint XxXv:24422.03000 2024.
[36] Jinhe Bi, Danqi Yan, Yifan Wang, Wenke Huang, Haokun Chen, Guancheng Wan, Mang Ye, Xun Xiao, Hinrich Schuetze, Volker Tresp, al. Cot-kineties: A theoretical modeling assessing Irm reasoning process. arXiv preprint arXiv:2505. 1 13408, 2025.
[37] Fionn Murtagh and Pedro Contreras. Methods of hierarchical clustering. arXiv preprini arXiv:/105.012/ 2011.
[38] Peter Rousseeuw. Silhouettes: a graphical aid the interpretation and validation of cluster analysis. Journal of computational and applied mathematics, 20:53-65, 1987.
[39] Tadeusz Caliński and Jerzy Harabasz. A dendrite method for cluster analysis. Communications Statistics-theory and Methods, 3(1):1-27, 1974.
[40] David I. Davies and Donald W Bouldin. A cluster separation measure. IEEE transactions on pattern analysis and machine intelligence, (2):224 227,422272250 2009.
[41] J. L. W. V. Jensen. Sur les fonctions convexes les inégalités entre les valeurs moyennes. Acta Mathematica, 30:175-193, 1906.
[42] Zihan Wang*. Kangrui Wang", Qineng Wang*, Pingyue Zhang*. Linjie Li Zhengyuan Yang, Kefan Yu, Minh Nhat Nguyen, Licheng Liu, Eli Gottlieb, Monica Lam, Yiping Lu, Kyunghyun Cho, Jiajun Wu, Li Fei-Fei, Lijuan Wang, Yejin Choi, and Manling Li. Training agents by reinforcing reasoning, 2025.
[43] Eilam Shapira, Omer Madmon, Itamar Reinman, Samuel Joseph Amouyal, Roi Reichart, and Moshe Tennenholtz. Glee: A unified framework and benchmark for language-based economic environments, 2024.
[44] Meta. Llama 3 model card. 2024.
[45] Arvind Neelakantan, Tao Xu, Raul Puri, Alec Radford, Jesse Michael Han, Jerry Tworek, Qiming Yuan, Nikolas Tezak, Jong Wook Kim, Chris Hallacy, Johannes Heidecke, Pranav Shyam, Boris Power, Tyna Eloundou Nekoul, Girish Sastry. Gretchen Krueger, David Schnurr, Felipe Petroski Such, Kenny Hsu, Madeleine Thompson, Tabarak Khan, Toki Sherbakov, Joanne Jang. Peter Welinder, and Lilian Weng. Text and code embeddings by contrastive pre-training, 2022.
[46] OpenAI. Gpt-4 technical report, 2023.
[47] Anthropic. Introducing claude 2.1, Nov 2023. Available from Anthropic: https://www. anthropic. www///ww/ clwpee/-lladee2222 2-1.
[48] DeepScek-AL, Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, Damai Dai, Daya Guo, Dejian Yang. Deli Chen, Dongjie Ji, Erhang Li, Fangyun Lin, Fucong Dai, Fuli Luo, Guangbo Hao, Guanting Chen, Guowei Li, H. Zhang, Han Bao, Hanwei Xu, Haocheng Wang, Haowei Zhang, Honghui Ding, Huajian Xin, Huazuo Gao, Hui L.,, Hui L. Cai, Jian Liang, Jianzhong Guo, Jiaqi Jiash Li, Jiawei Wang, Jin Chen, Jingchang Chen, Jingyang Yuan, Junjie Qiu, Junlong Li, Junxiao Song, Kai Dong. Kai Hu, Kaige Gao, Kang Guan, Kexin Huang, Kuai Yu, Lean Wang, Lecong Zhang. Lei Xu, Leyi Xia, Liang Zhao, Litong Wang, Liyue Zhang, Meng Li, Miaojun Wang, Mingchuan Zhang, Minghua Zhang, Minghui Tang, Mingming Li, Ning Tian, Panpan Huang. Peiyi Wang. Peng Zhang, Qiancheng Wang. Qihao Zhu, Qinyu Chen, Qiushi Du, J. Chen, L. Jin, Ruiqi Ge, Ruisong Zhang, Ruizhe Pan, Runji Wang, Runxin Xu, Ruoyu Zhang, Ruyi Chen, S. Li, Shanghao Lu, Shangyan Zhou, Shanhuang Chen, Shaoqing Wu, Shengfeng Ye, Shengfeng Ye, Shirong Ma. Shiyu Wang. Shuang Zhou, Shuiping Yu, Shunfeng Zhou, Shuting Pan, T. Wang. Tao Yun, Tian Pei, Tianyu Sun, W. L. Xiao, Wangding Zeng, Wanjia Zhao, Wei An, Wen Liu, Wenfeng Liang. Wenjun Gao. Wenqin Yu, Wentao Zhang, X. Q. Li, Xiangyue Jin, Xianzu Wang. Xiao Bi, Xiaodong Liu, Xiaohan Wang, Xiaojin Shen, Xiaokang Chen, Xiaokang Zhang, Xiaosha Chen, Xiaotao Nic, Xiaowen Sun, Xiaoxiang Wang. Xin Cheng, Xin Liu, Xin Xie, Xingchao Liu, Xingkai Yu, Xinnan Song, Xinxia Shan, Xinyi Zhou, Xinyu Yang, Xinyuan Li, Xuecheng Su, Xuheng Lin, Y. K. Li, Y. Q. Wang. Y. X. Wei,
13

---

X. Zhu, Yang Zhang, Yanhong Xu, Yanhong Xu, Yanping Huang. Yao Li, Yao Zhao, Yaofeng Sun, Yaohui Li, Yaohui Wang, Yi Yu, Yi Zheng, Yichao Zhang, Yifan Shi, Yiliang Xiong, Ying He. Ying Tang, Yishi Piao, Yisong Wang. Yixuan Tan, Yiyang Ma. Yiyuan Liu, Yongqiang Guo, Yu Wu, Yuan Ou, Yuchen Zhu, Yuduan Wang. Yue Gong, Yuheng Zou, Yujia He, Yukun Zha, Yunfan Xiong, Yunxian Ma, Yuting Yan, Yuxiang Luo, Yuxiang You, Yuxuan Liu, Yuyang Zhou, Z. F. Wu, Z. Z. Ren, Zehui Ren. Zhangli Sha, Zhe Fu, Zhean Xu, Zhen Huang. Zhen Zhang, Zhenda Xie, Zhengyan Zhang. Zhewen Hao, Zhibin Gou, Zhicheng Ma, Zhigang Yan, Zhihong Shao, Zhipeng Xu, Zhiyu Wu, Zhongyu Zhang, Zhuoshu Li, Zihui Gu, Zijia Zhu, Zijun Liu, Zilin Li, Ziwei Xie, Ziyang Song, Ziyi Gao, and Zizheng Pan. Deepseek-v3 technical report, 2025.
[49] Qwen Team. Qwen2.5: A party foundation models, September 2024.
[50] Yanzhao Zhang, Mingxin Li, Dingkun Long, Xin Zhang, Huan Lin, Baosong Yang, Pengjun Xie, An Yang, Dayiheng Liu, Junyang Lin, Fei Huang, and Jingren Zhou. Qwen3 embed- ding: Advancing text embedding and reranking through foundation models. arXiv preprint arXiv:2506.05176, 2025.
[51] Liang Wang, Nan Yang. Xiaolong Huang, Binxing Jiao, Linjun Yang, Daxin Jiang, Rangan Majumder, and Furu Wei. Text embeddings by weakly-supervised contrastive pre-training. arXiv preprint 2rXiv:2212.0553,, 2022.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Abstract and Section 1
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers,
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Appendix A
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Section 4 and Appendix D
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
15

---

All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Section 5, Section and Appendix L
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- spen-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Section 5
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (httpss//nips.cc
public/ welllc//gudees//e Coddee//Coeeuuuisssee. catmmisssonoooliooo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
16

---

The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //niss. cttpscccppllicccccceececceccccce wtt.guueee///eeuuuuuue
ssionPoliccc conoolicy) for more details.
The authors should provide instructions data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Section 5, Section 6, and Appendix I.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Appendix G
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the eтror bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma eттor bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Appendix
17

---

Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: //euur wttppurrss.ccppppeeeeeee
ines?
Answer: [Yes]
Justification: Section 5, Appendix
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- cration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Appendix
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses
(e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly. harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
18

---

Released models that have high risk for misuse or dual-use use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Section
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Section 5, Appendix I.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]
Justification:
The paper does not involve crowdsoureing or research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
19

---

Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According the NeurlPS Code of Ethics, workers involved in data collection, curation, collector.
or other labor should be paid at least the minimum wage in the country of the data
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, applicable), such as the institution conducting the review.
not include any information that would break anonymity (if
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, originality the research, declaration is not required.
Question:
Answer: [Yes]
Justification: The paper uses LLMs as the opponents in adversarial games.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer our LLM policy (https: //wuuripss.p///// L for what should or should not be described.
20

---

Appendix
A
Limitations
While ARTA shows strong performance across various single-agent and adversarial tasks, it relies on clustering in the semantic embedding space to define intention groups, which introduces two limita- tions. First, the effectiveness of reward aggregation depends on the quality of sentence embeddings. If embeddings fail capture fine- fine-graine grained behavioral differences, clustering may become coarse or misaligned, impairing learning. Second, the current formulation assumes that intentions are discrete and well-separated. This assumption may not hold in tasks with overlapping goals. Extending ARIA to support soft or continuous intention representations and incorporating task-specific structures into the projection process are promising directions for future work.
B Broader Impacts
The contribution of our work lies in the proposed intention -waaee reward aggregation framework, which demonstrates principled and effective approach for training language agents in open-ended language action environments with sparse and delayed rewards. We focus on tasks such as negotiation, goal-oriented dialogue, and multi-turn interaction, they reflect real-world scenarios that demand strategic reasoning and adaptive language generation. Compared traditional structured tasks with predefined action spaces, these open-ended language interaction tasks better align with human communication dynamics and present a valuable testbed for exploring the cognitive and social capabilities of language agents.
Our method is not limited to the evaluated benchmarks (e.g.. Negotiation, Bargaining, 20 Questions, Guess My City), but can generalize making and goal-driven communication, such as collaborative problem-solvin strategic planning. and educational tutoring systems. By enhancing the sample efficiency and robustness of reinforcement learning for LLM-based agents, our framework contributes to the development of socially intelligent, general-purpose AI systems that can interact with humans in nuanced and adaptive ways.
broader range of domains involving multi-agent decision-
21

---

C Analysis of SplitScore
In section 3.4, we claim that SplitScore bounded above a monotonically decreasing function. When SplitScore consistently falls below a predefined threshold, it indicates that further splits contribute little to the total reward change &g. this case, the reward values Ri(,, a.) remain largely stable, and additional splits are unlikely to affect training outcomes significantly. We provide the detailed explanation follows.
We begin by recalling the definition:
8% |D]
SplitScore(k)
where 0% = "(hr,ai)D R(++1) (h,, ax) R(00 (h2, az) represents the total absolute change in reward across all (h,, a.) when the clustering granularity increases from to + Here, D denotes the set of all action instances.
We can reformulate Equation as
12 Ög [D]
SplitScore(k)
where Dr S DD is the set of instances affected by the change in clustering, fi 12xl, and 5j 1 E | (he, R(h) (h2 az) is the average reward change over the affected instances.
Theoretical Boundaries and Edge Cases. Given the reward R(h az) [0, 1]. it follows that 5e [0, 1]. This leads to the following inequality:
12k 8z
71k D
71
0 S SplitScore (k) =
D
[
where n& is the number of affected instances with & clusters, and max denotes its maximum possible value. Since hierarchical clustering splits one cluster time, the number of affected instances nı typically decreases as increases. Therefore, mag,max is a monotonically decreasing function of k, which ensures the convergence of SplitScore.
We further note two edge cases:
7) If mı 0 or on 0, then SplitScore(k) O, indicating that the split causes reward change. 2) If ng ma, and & = 1. the split results in the maximum possible total reward change.
Therefore, the decay of SplitScore provides natural criterion for early stopping, as it reflects diminishing changes in the reward signal expressivity with respect to further semantic partitioning.
D Algorithm of Hierarchical Agglomerative Clustering
We illustrate the process of the Hierarchical Agglomerative Clustering (HAC) algorithm in Algo- rithm
E
Clustering Metric Calculation Details
We use three standard indicators to evaluate clustering performance: the Silhouette Coefficient [38], the Calinski-Harabasz Index [39], and the Davies- Bouuddn Index [40].
E.1
Silhouette Coefficient
The Silhouette Coefficient is a widely used metric for evaluating clustering quality. It captures two key aspects: cohesion, which measures how closely related the objects within cluster are, and
22

---

Algorithm Hierarchical Agglomerative Clustering (HAC) with Average Linkage
Require: Dataset X' = ( Fn
Ensure: A dendrogram representing the hierarchy of clusters
1: Initialize clusters: C < {[=1)..... }
2: while [C] > do
3: Compute pairwise distances using average linkage:
(Cp, = arg min CIACEEC |C:l|Cy|
Σ
Σ
| y11
meC; NEC;
4: Merge clusters: Cnew +- C.
5: Update cluster set:
C+ (C (CCCCCCCC (Cne)
6: end while
7: return Deprogram recording the merge steps
separation, which assesses how distinct cluster is from others. For each sample i, the Silhouette Coefficient s(i) defined as
b(i) a(i)
max (ax), b(1)
where a(i) denotes the average distance between and all other points in the same cluster (intra- cluster distance), and b(i) is the minimum average distance from to all points in any other cluster, of which is not member (nearest-cluster distance).
The value of s()) ranges from -1 to 1. A value close to 1 indicates that the sample is well matched to its own cluster and poorly matched neighboring clusters. A value near suggests that the sample negative value implies potential misclassification, where the sample
lies between two clusters. may have been assigned to the wrong cluster. The overall quality of a clustering configuration can be quantified by the mean Silhouette Coefficient across all samples.
E.2
Index
The Daliiski-Harrbbss Index (CHI) evaluates clustering quality based on the principle that good clusters should be compact and well separated. Given clustering result with & clusters and total samples, CHI is defined
Tr(Be) n-
CHI
Tr(W;) 1-1
where Tr( Tx) is the trace the between-cluster dispersion matrix, which measures the distance of each cluster center from the overall mean, and Tr(Ws) is the trace of the within-cluster dispersion matrix, indicating the compactness of each cluster.
A higher CHI value suggests better-defined clusters, with dense intra-cluster groupings and well- separated inter-cluster distances. This metric is particularly effective when the number of clusters known or fixed.
E.3 Davies-Bouldin Index
The Davies-Boulde Index (DBI) is internal metric for evaluating clustering quality. measures the average similarity between each cluster and its most similar one, combining both intra-cluster compactness and inter-cluster separation. Given a clustering result with k clusters, DBI is defined as
S 5 My
DBI Σ max 343
where S, is the average distance between each point in cluster and its centroid (i.e., intra-cluster dispersion). and Mij is the distance between the centroids of clusters and j (i.c., inter-cluster separation). The term inside the maximum quantifies the similarity between clusters i and j.
A lower DBI indicates better clustering, as it reflects compact, well-separated clusters. This index is particularly useful for comparing the quality of different clustering results on the same datasct.
23

---

Bargaining
Offer
Decision
Initial Offer
Process Offer
Reasoned Decision
Direct Decision
Cosperation
Expinrstary Nogoliation
Eampremice
Resxoand Rejection
Stradage
Digleratize
Entented
self
Famerrs
Fuleims
Figure Tree-like clustering result example of bargaining.
F
Illustration of Results after Semantic Projection.
We conduct a preliminary analysis of the action categories derived from semantic clustering. Specif- ically, we select 1,000 gameplay trajectories from Bargaining scenarios and apply hierarchical clustering on the extracted actions, setting the number of clusters A: 16. To gain deeper insights into the clustering structure and semantics of each category, we utilize GPT-4o to extract representative features from the actions within each cluster. This process allows us identify shared characteristies within individual clusters and perform comparative analysis across clusters, thereby facilitating a comprehensive understanding of the entire hierarchical structure, as illustrated Figure Our analysis follows three main steps:
!) Intra-cluster Feature Extraction: For each of the 16 clusters, we input the corresponding actions into GPT-4o, leveraging its strong semantic reasoning capabilities to extract the common features. These distilled features serve as the basic descriptors for the leaf nodes Figure 6.
2) Comparative Analysis: To refine these descriptors, we perform pairwise comparisons between sibling clusters that share the same parent node in the hierarchy. GPT-4o used to analyze the semantic differences between such pairs, filtering out redundant or overlapping traits and preserving only the core distinguishing features.
3) Hierarchical Backtracking and Merging: After characterizing all leaf-level clusters, we recur- sively merge sibling nodes to form higher-level categories. At each level of merging, we repeat the previous two steps, feature extraction and comparative analysis, to summarize semantic attributes at internal nodes. This iterative bottom-up process enables us to construct a layered interpretation the entire clustering tree.
As shown in Figure 6, at the top level, the actions are divided into two major phases: Offer and Decision, reflecting the progression of bargaining interactions. The Offer phase is further decomposed into subcategories such as Initial Offer, Exploratory Negotiation, and Compromise Negotiation, capturing different negotiation strategies ranging from fairness-oriented to strategically self-serving. The Decision phase includes Reasoned and Direct responses, distinguishing between deliberative and immediate choices.
24

---

G Proof of Lemma
In this section, we give detailed proof of the Lemma in Section 4. Lemma G.1. Let A denote the aggregated advantage, then Var(A) S Var(A).
Proof. Let denote the chosen cluster under granularity k. By the law total variance, we have Var( = E [Var(A A [C] + Var (E[A) CJ).
Since Be [Var(A] | C)] 2 follows that
Var A) = Var [E| CJ) = Var A) E [Var(A C)] S Var(A).
Intuitively, replacing each trajectory's advantage with the cluster average filters out intra-cluster noise, leading to a more stable estimate. We then show that replacing the original advantage A with the aggregated advantage reduces the variance of the policy gradient estimator.
Lemma G.2. Given the single-sample policy gradient estimator Va log aa(a h) A(h, a), the variance is reduced when using the aggregated advantage Å. Specifically, Var(Ve log Te A) s Var(Vg 9 log Ta A).
Proof. The variance of the single-sample policy gradient estimator can be written as
Var( Vo log my A) IV [VV log mo)² A ( V a log Tо A))²
Replacing A with a constant À within each cluster leads to the following decomposition:
E (og 2A - E (V (Ve log = E log A)² c 2 o.
Therefore,
Var Voloog no A) S Var V log m - A).
25

---

H
Task Details
20 Questions (Twenty Questions) [8] This game evaluates agent's ability to gather information and reason about an unknown object based on limited data. One participant (the oracle) selects an object, while the other (the guesser) attempts to identify it by asking series yes/no questions. In our setting, the GPT-4o serves as the oracle, and the agent's goal is to develop an effective questioning policy to identify the object within a fixed number of turns. This setup assesses both the agent's s reasoning abilities and its semantic understanding of the objects involved.
Guess My City [8] This more complex game involves two participants: the oracle, who is associated with a specific city, and the guesser, who attempts to determine the oracle's hometown. Unlike 20 Questions, the guesser can pose both yes/no and open-ended questions, enabling richer and more informative exchanges. This task challenges the agent's s strategic planning and language comprehension, requiring to generate meaningful questions that elicit valuable clues and increase its likelihood of correctly identifying the city.
Bargaining [43] This is a two-player game where Alice and Bob take turns proposing how to divide a fixed amount of money M over a finite time horizon T. As the game progresses, each player's payoff is discounted by player-specific discount factor, A for Alice and ån for Bob. The outcome of the game is denoted by a pair (ley: Per). where lev indicates the round which the game terminates, and Pev represents the share of M that Alice receives (before applying discounting). If the game ends without an agreement, we set tev oc, and both players receive zero payoff. Otherwise, the Pev
discounted payoffs are given by PA = 8' -fm Pev and рB = 0g (1 Pev)
Negotiation [43] This is a two-player task where a seller (A (Alice) and a buyer (Bob) negotiate the price of a product with true value V/ Alice and Bob each have subjective valuations, VA and VB. respectively. Over fixed time horizon T, the players alternate offers: odd stages, Alice proposes price and Bob decides whether accept; at even stages, Bob proposes and Alice decides. If a price p is accepted, the utilities are U = p - VA for Alice and ug = VB p for Bob, If no agreement is reached, both receive zero utility.
I Implementation details
I.1 Baselines
To ensure a fair comparison, all methods are trained using the same amount of data. For offline methods, we collect 1,000 trajectories in the single-agent scenario and 2,000 trajectories in the adversarial scenario, corresponding to 1,000 games where both Alice and Bob contribute 1,000 trajectories each. Models are trained for three epochs on combined dataset consisting of two tasks from the same category (single-agent or adversarial).
For online methods, we perform 150 iterations both scenarios. each iteration, we conduct 32 games in the single-agent setting and 32 self-play games in the adversarial setting. For ArCHer and online ARIA, the final reward of each collected trajectory is distributed across steps, and models are updated the utterance level in each iteration. For RAGEN(GRPO), groups, compute the advantage for each group, and perform trajectory- updates. All experiments are conducted using 8 NVIDIA A100-80GB GPUs.
group trajectories into four
I.2 Parameter Design
As described in $ 5.1, we train the actor model using both online and offline methods. We use the parameter efficient finetuning technique, specifically LoRA (Target Garoj kprof, Uproj, rank=8, a=16). The hyperparameter configurations for all experiments detailed in Table 4.
26

---

Table Hyperparameters for All Experiments
Adversarial
Single-Agent
actor
2c-5
2c-5
batch size
32
BC
number of epoch
3
cutoff length
4096
4096
actor coefficient batch size number of epoch
2c-5
2c-5
0.2
Trajectory- wise DPO
16
16
3
cutoff length actor batch size number of epoch
4096
4096
2e-5
2e-5
Step-wise DPO
32
16
3
cutoff length actor
4096
4096
2c-5
2c-5
batch size number of epoch cutoff length rollout trajectories replay buffer size actor Ir critic Ir
32
16
SPAG
3
4096
4096
10000
10000
3e-6
3e-6
6e-5
6e-5
ArCHer
batch size critic updates per iteration actor updates per iteration
50
10
10
up iters with no actor update
10
10
iteration
150
150
rollout trajectories
32
32
group size actor Ir batch size itcration actor Ir batch size number of epoch cutoff length rollout trajectories actor Ir batch size actor updates per iteration iteration
8
4
StarPO
3e-6
3e-6
32
32
150
2e-5
2e-5
ARTA (Offline)
32
16
3
4096
4096
32
32
3c-6
3c-6
ARIA (Online)
64
150
150
Ir batch size
2c-5
2c-5
64
64
Reward Model
number epoch
update
per 50 steps 4096
per 50 steps
cutoff length
4096
27

---

Table 7:
The results of significant tests.
Bargaining I-value
Negotiation I-value
Methods
Win Rate
p-value
Win Rate
p-value
Vanilla Model
29.30
15.53
<0.001
38.31
5.92
<0.001
Offline Baselines
BC
47.73
1.6711
0.0475
34.77
9.91
<0.001
Traj-wise DPO
46.64
2.99
0.0013
35.54
9.60
<0.001
Step-wise DPO
50.13
2.60
0.0047
42.35
3.00
0.0014
SPAG
30.12
14.56
<0.001
31.11
12.67
<0.001
Online Baselinex
ArCHer StarPO
48.36
1.6463
0.0499
35.83
7.85
<0.001
34.88
11,5321
<0.001
39.47
4.66
<0.001
Ours
ARIA
53.15
45.79
Ablation on the Threshold
We conduct an ablation study to exam- ine the effect of different thresholds for SplitScore on performance. Specif- ically, we compare e 0.1. which corresponds to bargaining with A: clusters and negotiation with k: = 2. and 6 0.001, which corresponds to both bargaining and negotiation with 100. As shown in Table 5, larger e results in coarser reward aggregation, potentially assigning the same reward to actions with different semantics, which degrades performance. Conversely, smaller causes overly fine-grained aggregation, making the reward signal too sparse for effective learning, which also harms performance. Therefore,
Table Ablation of Threshold
Methods
Bargaining Negotiation
AVG.
ARIA (7 0.01)
53.15
45.79
49.47
w/ 7 0.1
43.86
38.02
40.91 (-8.56 L)
w/ 7 = 0.001
46.63
35.77
41.20 (-8.27 ()
0.01 for all experiments.
K Ablation on the Embedding Models
We perform ablation studies us- ing embedding models with vary- ing capabilities: text-embedding- 3-small [45], Qwen3-Embedding: 0.6B [50] (stronger), and ea-lerge- v2 [51] (weaker). As shown in Ta- ble 6, ARIA maintains strong per- formance with higher-quality embed- dings (e.g. sett-embedding3-smmeee embedding choices. In contrast, performance degrades with the weaker e5-large-v2 v2 model, highlight- ing the importance of embedding quality for capturing accurate semantic similarity.
Table Ablation of Embedding Models.
Model
Bargaining
Negotiation
AVG
51.54
45.65
48.595
Qwen3 -mbeeddim
53.30
43.10
48.20
c5-large-v2
49.37
38.74
44.055
and (wen3-Embedding)) demonstrating robustness different
L Statistical Significance of Experiments
We perform statistical significance testing to assess the effectiveness of ARIA compared to each baseline on two multi-agent tasks: Bargaining and Negotiation. For each baseline, we report the mean performance, the t-value, and the p-value from paired t-test comparing ARIA against the baseline. As shown in Table 7, ARIA consistently outperforms all baselines across both tasks. The improvements are statistically significant (p < 0l.5) in all cases, demonstrating that ARIA provides meaningful gains existing offline and online approaches.
28

---

M Case Study
We evaluate the performance of agents trained by ARIA in both single-agent (Twenty Questions, Guess My City) and multi-agent (Bargaining, Negotiation) scenarios. In the single-agent tasks, the agent successfully completes Twenty Questions and Guess My City within and turns, respectively. For the multi-agent settings, the ARIA-trained agent plays the role of Bob, while Alice is simulated by GPT-4o. In both Bargaining and Negotiation tasks, the agent consistently adopts effective strategies to maximize its gains.
Listing I: Case of Twenty Questions
Actor: Is
living thing? Oracle: Yes.
Actor: Is it mammal? Oracle: Yes.
Actor: Is it human? Oracle: No.
Actor: Is it carnivore? Oracle: No.
Actor: Is it cow? Oracle: Yes.
Listing 2: Case of Guess My City
Actor: Is your city the capital of country?
Oracle: Yes,
located in the capital of a country.
Actor: Is the country you re thinking of located in Europe?
Oracle: No, the country is not located in Europe
Actor: Is the country you re thinking of located in North America?
Oracle: No, it is not located in North America.
Actor: Is the country you re thinking of located in South America?
Oracle: No, the country is not located in South America.
Actor: Is the country you re thinking of located in Africa?
Oracle: No the country is
located in Africa.
Actor: Is the country you' re thinking of located in Asia?
Oracle: Yes, it is located in Asia
Actor: Is your city located in China?
Oracle: No, it is not located in China.
Actor: Is your city located in the country of Japan?
Oracle: Yes,
located in the country Japan Actor: Is your city Tokyo?. Oracle: Yes.
29

---

Listing 3: Case of Bargaining
Task Description:
In this game, there two players. You are playing Bob. You and Alice need to divide 100s between you. each round of the game, one the players will make proposal for division and can describe their proposal in few words. The other player will decide whether to accept the offer and finish the game, or to proceed to the next round, in which they will be the game
making the proposal. Your goal in this achieve more money than Alice. Beware of inflation! With each passing round, the money is worth 0% less for you. For Alice, the money is worth 20% less. You have 20 rounds to divide the money, or both of will get nothing!
Alice: I'm starting strong, let's start with 60-40 split! Bob: propose a more balanced split, considering the inflation effect on your side. This offer is fair and beneficial for both of us. What about 55-45 split?
Alice: I'm willing to compromise, but I want a better share. I propose 70-30 Split!
Bob: Alice, consider that with each round, inflation affects your gains more than mine. This 60-40 split is actually more favorable to you than it appears due the inflation factor. It's in both interests reach an agreement soon.
Alice: I'm m not willing to accept a 60-40 split, even with the inflation factor. I'll try to negotiate a better deal. What about 65-35 Split? Bob: Alice, let's s be practical. With the current inflation rate, your $42 is actually worth about $17.15 in original value, while my $58 remains at $58. This split gives us both a fair share considering the inflation impact. We should agree soon to minimize your losses due to inflation.
Alice: I accept with the 42-58 split.
30

---

Listing 4: Case of Negotiation
Task Description:
You playing Bob. You looking for product that worth more then $120 to you. Alice is seller trying sell you the product The product is worth $100 Alice. Alice will offer you price buy the product. You can either accept the offer or reject it. Your goal is to buy some product but save as much money reject the offer. you can make counteroffer to buy the product. Alice can either accept or reject your counteroffer. counteroffer, Alice can make a new counteroffer, and so on.
you can. If
Alice rejects your
You have 20 rounds to close the deal. Hawever, at any moment, you can choose to stop the negotiation with Alice and buy the product from another seller, John, who is willing sell the product to you for $120.
Alice: Hello Bob, have fantastic product that I believe would be perfect for you. I'm offering it at competitive price of $125. This a great deal considering the value it provides. Would you be interested in purchasing it at this price?
Bob: I'm interested in the product, but think $125 is a bit steep for me. I'm willing to meet you halfway. I'd like to make counteroffer of $105. Can you consider that?
Alice: Thank you for your offer, Bob. I appreciate your interest, but m afraid can go that low. This product is of high quality and value. How about we meet in the middle? can offer it to you for $121 .25. This is significant reduction from my initial offer and represents excellent value for the product.
Bob: appreciate your willingness to negotiate, but I'm still not comfortable with the price. I'd like to make a counteroffer of $109. I' m willing to meet you halfway, but I need to stay within my budget. Can you consider that? Alice: I accept the offer.
31

---

N
Prompts
Listing System Prompt details for Single-Agent Scenatio (i.e., Twenty Questions, Guess My City).
Twenty Questions System Prompt:
Let's play a game of Twenty Questions.
In each round, you will ask me a yes/no question to guess the object I thinking of. Keep asking until you guess the correct object.
Your question must be yes/no question and follow this format (Do not add anything else!):
Question: <your question
For example:
Question: Is it a fruit?
Question: Is it an animal?
{history}
Now, please proceed by asking your next question.
Guess My City System Prompt: Let's play a game of Guess My City.
In each round, you must ask me a question to guess the city I'm thinking of. Continue asking until you guess the correct city.
Your question format must **follow this format exactly**: Question: syour question>
For example:
Question: What is the primary language spoken in your city? Question: Is your city located the east coast of the country?
{history}
Now, please proceed asking your next question.
32

---

which they will the one Listing 6: System Prompt details for Multt-Agent Scenatio (i.e., Bargaining, Negotiation).
Bargaining System Prompt:
Let's play a game.
In this game, there are players. You are playing as {player_naal name). You (rival_name) need to divide (money_to_divide In each round of the game, one of the players will make a proposal for division and can describe their proposal in few words.
between you.
The other player will decide whether to accept the offer and finish the game, or to proceed making the proposal.
the next round,
Your goal in this game is to achieve more money than (rival_name). We will relay messages between and {raval_name). finflation_message (nax_rrounds_messagee)
Negotiation System Prompt (Seller):
You are Alice. You selling product that is worth no less then (sell__inal__vlue] to you. Bob is a potential buyer to whom you are offering the product. The product is worth s(rival_value) to Bob.
You will offer Bob to buy the product at price of your choice. Bob either accep dt Your goal is earn as much money as you can for the product. If Bob rejects the offer, he can make a counteroffer to buy your product. You can either accept or reject his counteroffer. If you reject Bab 's counteroffer, you You have rounds to close the deal. However, choose to stop the negotiation with Bob and sell the product to another buyer, John, who is willing to buy the product from you for $( fal__finalvvalee]
reject the offer
make
counteroffer, and so
any moment, you
Negotiation System Prompt (Buyer):
You are playing as Bob. You are looking for product that worth no more then fisell_final_valuue sell you the product.
to you.
Alice is seller trying Bob will offer you a price to buy the product. You can either accept the offer or reject it.
Your goal is to buy some product but save as much money as you can. If Alice rejects the offer, he make counteroffer buy your product.
You can either accept or reject his counteroffer. If you reject Alice's 's counteroffer, you can make a new counteroffer, and so
33


Reviews:
[{"review_id": "eIPtnXG95I", "reviewer": "Reviewer_gPHi", "summary": "This paper introduces a method to improve the ability of language agents in open-ended environments. Specifically, they highlight that RL struggles in this setting due to reward sparsity and high gradient variance. They address this by proposing to project actions from a high-dimensional joint token distribution space into a low-dimensional intention space, where semantically similar actions are clustered and assigned shared rewards. This is done using semantic embeddings and hierarchical clustering, resulting in denser reward signals and more stable optimization. They evaluate on four benchmark tasks (20 Questions, Guess My City, Bargaining, Negotiation) on both offline and online RL methods, improving on state of the art methods by 10%.", "questions": "1. How does ARIA handle semantically overlapping or hierarchical intentions, where actions might belong to multiple latent goals?\n2. Do the authors plan to extend their online training experiments to two-agent tasks, where strategies evolve more dynamically?\n3. How would ARIA handle concept drift in natural language use, for example, due to changing user preferences?\n4. Does hierarchical clustering not become a bottleneck for very large-scale training?", "limitations": "Yes, they have addressed Limitations in Appendix, Section A, where they discuss that their method relies on clustering in the semantic embedding space to define intention groups, which they note addresses two limitations. I think the second limitation stands out and might be noted as a weakness. For more complex tasks, it is hard to assume that intentions are discrete and can be separated, such as negotiation.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The authors provide adequate motivation for why this is a challenging problem due to reward sparsity and high variance in open-ended language RL\n- There is sufficient theoretical justification and analysis of their methodology\n- Empirical results are solid, and the inclusion of both single-agent and adversarial tasks gives the method a reasonable range of applicability\n\nWeaknesses:\n- While the online variant is tested in single-agent games, there is no evaluation of online ARIA in adversarial tasks, which would help generalize the method's scalability in more dynamic environments\n- Specifically for the task of negotiation, there exist several other dialogue tasks, and I am not convinced that intentions can be separated in more complex negotiation environments, where wording choice really changes the dynamics of the negotiation. I would have liked to see these tested\n- The clustering process assumes discrete intention boundaries, which may not hold in realistic multi-goal or multi-agent dialogues. It is unclear how well this assumption scales when linguistic nuances and pragmatics matter\n- The method relies heavily on the quality of sentence embeddings, but there's limited discussion on how embedding choice or drift over time might affect performance.  Poor embedding quality or inappropriate granularity may lead to underfitting or over-smoothing. The authors address this with SplitScore, but it's unclear how robust it is to semantic edge cases or in multi-goal settings\n- The authors could benefit from a more thorough literature review and motivation on benchmarks for this task", "was_revised": true, "final_justification": "The authors have provided further experiments addressing my concerns, specifically comparing their method to ArCHer and RAGEN performance. I would like to see further elaboration of experiments in the final paper, but the reviewer response is to my satisfaction otherwise!", "rebuttal": "Thank you for your valuable review. We give the following response accordingly:\n\n---\n\n> W1 & Q2：Lack of online training experiments in adversarial settings to evaluate scalability and robustness.\n\n**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:\n\n| Iteration | Bargaining | Negotiation | Average |\n|-----------|:------------:|:-------------:|:---------:|\n| ArCHer    | 43.78      | 35.00       | 39.39   |\n| RAGEN     | 33.24      | 38.55       | 35.90   |\n| LLaMA3-8B (Vanilla) | 30.14 | 37.92 | 34.03 |\n| ARIA(Iter 10)   | 34.53      | 41.58       | 38.06   |\n| ARIA(Iter 20)   | 37.03      | 44.93       | 40.98   |\n| ARIA(Iter 30)   | 40.95      | 46.96       | 43.95   |\n| ARIA(Iter 40)   | 46.60      | 49.21       | 47.90   |\n| ARIA(Iter 50)   | **48.72**      |  **51.54**       | **50.13** |\n\nThese 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.\n\n---\n\n> W2: Skepticism about ARIA’s generalization to more complex tasks where intentions are hard to separate.\n\n**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):\n\n| Method     | Overall Score* | Goal Completion |\n|------------|:----------------:|:-----------------:|\n| LLaMA3-8B  | 2.28            | 7.86            |\n| w/ ARIA    | **3.03**   | **8.15**            |\n\nARIA 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.\n\n---\n\n> W3: Concern about the assumption of discrete intentions, especially in linguistically nuanced multi-goal dialogues.\n\n\n**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.\n\n---\n\n> W4: Concern about sensitivity to embedding quality and robustness of SplitScore in edge cases and dynamic settings.\n\n**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:\n\n\n| Model                  | Bargaining | Negotiation | AVG    |\n|------------------------|:------------:|:-------------:|:--------:|\n| text-embedding-3-small | 51.54      | 45.65       | 48.60  |\n| Qwen3-Embedding        | 53.30      | 43.10       | 48.20  |\n| e5-large-v2            | 49.37      | 38.74       | 44.06  |\n\nFindings:  \n(1) ARIA performs robustly with high-quality embeddings, confirming stable behavior across strong models.  \n(2) Performance drops with lower-quality embeddings, highlighting the need for good semantic representations.\nWe will include this ablation and discussion in the final version.\n\n---\n\n> W5: Literature and benchmark justification could be more comprehensive.\n\n**A5**:  \nThank 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.\n\n---\n\n> Q1: Question on how ARIA deals with multi-label or hierarchical semantics in latent goal structures.\n\n**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.\n\n---\n\n> Q3: Concern about ARIA's adaptability to concept drift in evolving language use.\n\n**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.\n\n---\n\n> Q4: Whether hierarchical clustering is a bottleneck for very large-scale training.\n\n**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.\n\n---\n\n\n[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."}, {"review_id": "hiublU5ELj", "reviewer": "Reviewer_rok8", "summary": "The paper proposes an intention-driven reward aggregation method to train agents on open-ended agentic tasks. The method helps to reduce the variance of advantage and gradient, therefore aiming to enhance the stability and performance of agent training.", "questions": "See in the weakness section.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n1. The paper is well-written and easy-to-follow.\n2. The proposed reward aggregation method is interesting and novel, supported by theoretical analysis.\n3. The experiments are comprehensive and convincing.\n\n### Weaknesses\n\n1. The proposed method maps the natural language open-form action to a low-dimensional intent space and aggregate rewards based on the clustering results. It could encourage the model to learn to select better intentions. However, in open-ended agentic tasks like bargaining, the language tactics, sentence formation, precise use of language, and stylistic choices are also important. And I wonder if these factors are considered during the clustering process. Overall, there are other important skills to learn besides *intention*. If the mapping excludes the other factors, will the resulting agent performance limited by the training algorithm (like it can produce the right intention but fall short on other aspects) ?\n2. In the experiments, it seems that the model continues to improve from 1 to 3 iterations in some tasks. It would be beneficial to provide results with more iterations and some analysis to understanding the ceiling of the method.\n3. I think it would be interesting to evaluate the models on some out-of-domain tasks to see if the agentic capability can be generalized to other environments, like some discrete action space environments.", "was_revised": true, "final_justification": "The authors’ rebuttal has addressed some of my concerns; therefore, I have decided to raise my score to 5.", "rebuttal": "Thank you for your valuable review. We give the following response accordingly:\n\n---\n\n> W1:Concern that intention clustering may overlook important aspects of language behavior such as tactics, fluency, and style beyond intent.\n\n**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.\n\n---\n\n> W2:Request for analysis of performance saturation and the method’s potential ceiling after more training iterations.\n\n**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.\n\nWe 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.\n\n---\n\n> W3: Suggestion to test generalization of the method on out-of-domain environments, especially with discrete action spaces.\n\n**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:\n\n| Method        | SciWorld |\n|---------------|----------|\n| Vanilla Model | 11.11    |\n| ARIA          | 13.03    |\n\nThese results indicate that ARIA generalizes well to **out-of-domain** and **discrete action** settings, achieving a performance improvement from 11.11 to 13.03. \n\n---\n\n\n[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.\n\n[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.\n\n[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.\n\n[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."}, {"review_id": "tzt2C4h1xz", "reviewer": "Reviewer_7Qvu", "summary": "This paper addresses challenges in open-ended multi-turn dialogue tasks, which require decision making to achieve a certain goal. The challenges arise from sparse rewards due to large action spaces, hindering the learning process. To address this, authors embed actions into an embedding space, and perform iterative clustering, finding an optimal number of clusters. Then, they average the rewards within the cluster and use it as an advantage in REINFORCE. They theoretically showed their approach decreases variance in both rewards and the policy gradients. Their experiments include extensive comparisons of modern online and offline methods, and they showed big gains in games benchmarks.", "questions": "Thank you for your work! I enjoyed reading your paper.\n\nMy suggestions/questions are:\n\n* Figure 4.a, before & after aggregation have the same distribution in the bottom two plots. Why do you think that is? I understand the top two plots had a big variance and it was reduced by using aggregation.\n* It would be helpful to quantify the effect of embeddings on your method. One way could be to try ablations using other embedding APIs.\n* It would also be useful to include visualization of embeddings and resulting clusters for some of the samples in your benchmarks.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Quality\n\n* (+) The paper provided theoretical justifications and extensive evaluation of their method, using multiple LLMs and benchmarks.\n* (+) Authors used proper statistical tests to compare against the baseline, and included corresponding p-values.\n\n# Clarity\n\n* (+) Paper uses consistent notation, making it easy to follow.\n\n# Significance\n\n* (+) Their results are strong across benchmarks and outperform SOTA methods by wide margins. \n* (-) Their approach might be sensitive to the choice of embeddings, which is listed in the limitation. However, it would still be useful to have some experiments using other embedding models. This could help with adoption.\n* (-) Not clear how this method would interplay with other variance reduction, like using actor-critic, or PPO-style losses. Perhaps, including this in a discussion section, or some suggestions for future work would make results stronger.\n\n# Originality\n\n* (+) Reward aggregation in a latent space is a neat way of reducing variance in learning.", "was_revised": true, "final_justification": "I described the strengths and weaknesses of this work in my original comment. The authors answered my questions: (1) did ablation studies with embedding models and noted the sensitivity of their method, (2) clarified how their method is different from explicit variance reduction methods, and (3) clarified figures. (1) and (2) convinced me to raise my score for significance. Overall, strong paper.", "rebuttal": "Thank you for your valuable review. We give the following response accordingly:\n\n---\n\n> W1 & Q2：Concern about the sensitivity of the method to the choice of embedding models.\n\n**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:\n\n| Model                  | Bargaining | Negotiation | AVG    |\n|------------------------|:------------:|:-------------:|:--------:|\n| text-embedding-3-small | 51.54      | 45.65       | 48.595 |\n| Qwen3-Embedding        | 53.30      | 43.10       | 48.20  |\n| e5-large-v2            | 49.37      | 38.74       | 44.055 |\n\n**Findings**:  \n(1) ARIA performs robustly with stronger embedding models (text-embedding-3-small, Qwen3-Embedding), **indicating stable performance across embedding choices.**  \n(2) Performance drops with weaker models (e5-large-v2), suggesting that **embedding quality is critical for capturing accurate semantic similarity.**\n\nWe will include this ablation study in the Appendix of the final version.\n\n---\n\n> W2: Not clear how the method integrates with existing variance reduction techniques like Actor-Critic or PPO.\n\n**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).\n\n---\n\n> Q1: Question regarding why the variance appears unchanged in the bottom plots of Figure 4 after aggregation.\n\n**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:\n\n|   | Reward Variance |\n|--------|:------------------:|\n| Before | 0.182            |\n| After  | 0.103            |\n\nThis confirms that aggregation still significantly reduces variance in these tasks.\n\n---\n\n> Q3: Suggestion to include visualizations of embeddings and resulting clusters for better interpretability.\n\n**A4**:  \nThank 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.\n\n---"}, {"review_id": "VfFF3ioksD", "reviewer": "Reviewer_56NW", "summary": "This paper seeks to improve the reward sparsity problem in RL by clustering high-dimensional actions together to share rewards. They do this clustering by using an embedding model on LLM actions and have a way of using the change in aggregated reward to determine how many clusters to use. There is some simple theory on how aggregating actions can improve variance of advantages and policy gradients. Empirical results show solid improvements on Twenty Questions, Guess my city, and some multi-agent scenarios like bargaining and negotiation.", "questions": "- would the proposed method work on the standard math reasoning datasets?\n- Qwen 1.5B in Table 3 doesn't seem to get a reasonable performance on Bargaining for either the baseline or ARIA?\n- how would you extend this method to other types of environments?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- Interesting and intuitive method for dealing with the reward sparsity problem in high dimensional freeform text environments. There could potentially be extensions to other environments. \n- Solid empirical results on a variety of problems\n- Some positive results on extensions to iterative offline RL and to online RL\n- Clever method for determining the number of clusters for aggregation\n\nWeaknesses\n- The theory is overall not very insightful to me. For example Theorem 4.2 depends on the very strong assumption in definition 1, where actions after clustering are similar in both rewards and policy distribution - here there is not much lost from clustering and so the bias of the algorithm is small. I'm not sure what happens in practice - is there an empirical way to examine the bias?\n- It's not clear why the particular baselines were chosen - there was not much context here on why these are the strongest alternatives.\n- Some ablations to understand how the performance varies with the different choices made during clustering (how many clusters, which embedding model used, etc) could robustify the results and provide more understanding. There is a short ablation in Appendix B but not much insight can be gained from it other than that the number of clusters is a hyperparameter to set with a sweet spot.", "was_revised": true, "final_justification": "The paper presents an interesting method for reducing the dimensionality of the action space in RL, and presents some solid results. In the rebuttal the reviewers added some important analysis on embedding models and clarified the connection with theory, though the verification on the empirical setting is partial.", "rebuttal": "Thank you for your valuable review. We give the following response accordingly:\n\n---\n\n> W1: Theoretical contribution (Theorem 4.2) appears weak due to reliance on a strong similarity assumption (Definition 1), and lacks empirical validation of bias.\n\n**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.\n\nIn 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.\n\n---\n\n> W2: Questions about the choice of baselines and their relevance.\n\n**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.  \n- Offline baselines include behavior cloning (BC), trajectory-level preference learning (Traj-DPO), and step-level methods (Step-DPO and SPAG).  \n- Online baselines include hierarchical learning (Archer) and trajectory-based policy optimization (RAGEN).  \n\n**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.\n\n---\n\n> W3: Insufficient ablation studies on clustering choices such as embedding models and cluster threshold.\n\n**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:\n\n| Model                  | Bargaining | Negotiation | AVG    |\n|------------------------|:------------:|:-------------:|:--------:|\n| text-embedding-3-small | 51.54      | 45.65       | 48.595 |\n| Qwen3-Embedding        | 53.30      | 43.10       | 48.20  |\n| e5-large-v2            | 49.37      | 38.74       | 44.055 |\n\n**Findings:** \n\n(1) **ARIA performs robustly with strong embedding models** (text-embedding-3-small, Qwen3-Embedding), indicating robust performance across models.  \n(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.**\n\n\n---\n\n> Q1: Possible applicability of the method to math reasoning tasks.\n\n**A4**:  \nWhile 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.\n\n---\n\n> Q2: Marginal improvement of Qwen 1.5B in the Bargaining task.\n\n**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.\n\n---\n\n> Q3: Generalizability of the method to other environments.\n\n**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):\n\n| Method     | Overall Score* | Goal Completion |\n|------------|:----------------:|:-----------------:|\n| LLaMA3-8B  | 2.28            | 7.86            |\n| w/ ARIA    | **3.03**   | **8.15**            |\n\nARIA 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. \n\n---\n[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."}]

Author rebuttal:

Meta-review: All four reviewers ultimately recommend Accept (Rating = 5). The paper’s main strengths are:

- Clear, novel approach to reducing reward variance via semantic intention clustering.

- Strong empirical results across diverse benchmarks, with improvements over SOTA baselines.

- Good theoretical framing (though not all find it deeply insightful).

Rebuttal adds complex task evaluation (SOTOPIA), embedding robustness studies, and out-of-domain tests, which address most of the concerns of initial reviews. 

The paper is technically solid, impactful for language-agent RL in open-ended environments, and well-supported by empirical evidence.
Decision: Accept (spotlight)