Targeted Data Acquisition for Evolving Negotiation Agents

Motivation

• Negotiation is crucial in mixed-incentive interactions because agents must pursue self-interest while compromising to reach equitable outcomes.Blind reward maximization can produce coercive or unfair deals, making both objectives difficult to optimize explicitly.Source: §1 · p. 1

Limitations of existing data

• Static negotiation datasets are difficult to scale and can be biased by short, anonymous, or non-repeated interactions.Supervised agents may overfit these biases and become exploitable by human partners.Source: §1 · pp. 1–2

Proposed approach

• Targeted data acquisition uses uncertainty-based active learning to identify novel, out-of-distribution negotiations for expert annotation and retraining.The framework updates the partner agent alongside the learning agent and uses coarse dialogue acts to isolate negotiation strategy from language generation.Source: §1 · p. 2, Figure 1 · p. 2

Results

• Targeted acquisition best optimizes self-interest and Pareto-optimality across simulated and human evaluation without hand-engineered rewards.The agents can also learn negotiation from random initialization without pre-existing data.Source: §1 · p. 2

Negotiation

• Negotiation research commonly trains language-based agents for two-player bargaining over objects with private payoff matrices.DEALORNODEAL provides a natural-language negotiation dataset and an end-to-end architecture, while later work explores hierarchical approaches.Source: §2 · p. 2

Adaptive Data Collection

• Active learning selects uncertain or informative examples for labeling, while expert-oracle annotation resembles imitation-learning approaches such as DAgger.These components motivate acquiring new negotiation examples and supervising the agent on them.Source: §2 · pp. 2–3

Multi-Agent Coordination

• Related multi-agent work addresses cooperation, zero-sum games, partner conventions, trustworthy human-robot systems, and emergent communication.Source: §2 · p. 3

Task

• DEALORNODEAL gives each agent object counts and private utilities, then requires agreement on an allocation of books, hats, and balls.Contexts specify the shared inventory and each agent’s preferences.Source: §3 · p. 3

Interaction

• Agents negotiate for T time steps by exchanging five coarse dialogue acts: propose, insist, agree, disagree, and end.Proposal and insistence acts include explicit allocations for both agents.Source: §3 · p. 3

Rewards

• Agreement awards each agent utility-based points, whereas failed agreement yields zero points.If the final allocation sums to the available inventory, rewards are r_A = u_A·o_A and r_B = u_B·o_B.Source: §3 · p. 3

Baseline paradigms

• Standard baselines include supervised learning, reinforcement learning, and interleaved reinforcement-plus-supervised learning.The paper formalizes these approaches and examines how low-quality datasets affect them.Source: §4 · p. 3

Supervised Learning

• Supervised learning trains a sequence-to-sequence model to predict dialogue acts and final selections from negotiation history and agent context.The objective combines dialogue-act and final-selection likelihoods, weighted by α.Source: §4 · p. 3

Reinforcement Learning

• Reinforcement learning fine-tunes Alice against a fixed Bob to maximize Alice’s negotiation utility using REINFORCE.The reward uses the final score, a running-average baseline, and discounting that gives greater weight to later dialogue acts.Source: §4 · p. 4
• Because Bob is supervised-trained, reinforcement learning can explore strategies that are novel and out-of-distribution for the partner while still inheriting dataset biases.Source: §4 · p. 4

Mixed Reinforcement & Supervised Learning

• Interleaving supervised updates regularizes Alice but retains original-data biases, including excessive compromise when disagreement examples are scarce.Source: §4 · p. 4

• Updating Bob with expert-annotated negotiations lets Alice learn novel strategies while Bob adapts alongside her.Newly annotated negotiations are added to the training set, and Bob is retrained before Alice continues reinforcement learning.Source: §5 · pp. 4–5
• The framework scores negotiations by how novel Alice’s dialogue acts are to Bob, then annotates the most novel cases.Novelty is based on the minimum log-likelihood assigned by Bob to Alice’s dialogue acts; an expert oracle supplies responses.Source: §5 · p. 4
• Over training, Bob becomes more novel, while his Pareto optimality tracks the proportion of expert annotations and influences Alice’s outcomes.The figure tracks training epochs from pre-training initialization; richer early supervision is associated with stronger Pareto-optimality.Source: Figure 3 · p. 5
• Expert feedback discourages undesirable behaviors such as badgering while rewarding Alice’s Pareto-optimal proposals through improved responses from Bob.Bob can end conversations or disagree with coercive proposals, but agree when Alice discovers an effective Pareto-optimal strategy.Source: §5 · p. 5

6.1. Simulated Active Learning

• RL attains the highest advantage but the lowest Pareto-optimality and agreement, producing aggressive and uncompromising negotiations.Its increasing novelty over time is associated with aggressive utterances rather than equitable outcomes.Source: §6.1 · p. 6
• RL+SL shows the opposite trade-off—low advantage but high Pareto-optimality and agreement—because supervised updates reinforce static-dataset biases.Interleaved supervised learning also keeps the agent closest to its initialization and hurts advantage.Source: §6.1 · p. 6
• Targeted acquisition achieves high advantage while maintaining higher Pareto-optimality and agreement than RL, balancing the two negotiation desiderata.It is also the most novel approach, suggesting expert annotations help Alice learn better dialogue-act distributions.Source: §6 · p. 5, §6.1 · p. 6
• Starting from random initialization, targeted acquisition learns negotiation behavior whereas RL remains near its random policy and makes disadvantageous proposals.The RL behavior boosts Pareto-optimality and agreement by having Bob accept disadvantageous proposals, rather than by learning meaningful negotiation.Source: Figure 5 · p. 7
• Alternative joint-score and same-score metrics confirm that targeted acquisition outperforms RL but not RL+SL or SL on these measures.The reported percentages are 4% ± 0.2 versus 3% ± 0.2 for joint maximal score, and 5% ± 0.2 versus 4% ± 0.2 for same score.Source: §6.1 · p. 7

6.2. Human Evaluation

• With human partners, targeted acquisition obtains higher advantage than RL+SL while being more Pareto-optimal than RL, matching the simulated desiderata.Participants also rated the approach among the fairest and most effective, and wanted it to represent them in similar negotiations.Source: Figure 4 · p. 6, §6.2 · pp. 7–8

Alice Learns to Negotiate Starting from Scratch

• Targeted acquisition learns meaningful negotiation from random initialization, whereas RL barely changes from its initialization and produces disadvantageous proposals.The targeted agent also generates longer dialogues, averaging 12 turns versus 5.9 for RL.Source: §7 · p. 8

Novelty Maintains High Advantage and Moderate Pareto-Optimality

• RL+SL variants that achieve higher Pareto-optimality than targeted acquisition perform poorly on advantage, while targeted acquisition is the most novel.The results support acquiring new data as important for maintaining high advantage while remaining Pareto-optimal.Source: §7 · pp. 8–9

Directly Optimizing for Our Desiderata Fails

• Directly adding Pareto-optimality to the RL reward improves agreement but worsens Pareto-optimality, making reward engineering a difficult alternative.The paper attributes this difficulty partly to Pareto-optimality being a binary, sparse reward.Source: §7 · p. 9

Investigating First-Order Effects

• First-order expert training yields lower advantage but higher Pareto-optimality than second-order training, while both outperform RL+SL on advantage and RL on Pareto-optimality.Direct expert training makes Alice more compromising because the annotations contain more Pareto-optimal behavior.Source: §7 · p. 9

Discussion

• Targeted exploration enables agents to learn novel strategies that balance advantage and Pareto-optimality with simulated and real human partners.The framework is intended to help agents cooperate with people toward fair and mutually beneficial outcomes.Source: §8 · p. 9

Limitations

• Data acquisition lengthens training time, and indirect expert influence makes it difficult to explain precisely how annotations affect Alice.The expert influences Alice through Bob, although the paper explores directly training both agents as a first-order alternative.Source: §8 · p. 9

Scaling Our Work with Human Experts

• Using human experts could reduce or eliminate the need for large, high-quality datasets used to train synthetic experts, but the scalability of expert querying remains important.The authors report that an annotation task takes less than one minute on average and estimate continual human-expert learning is feasible, leaving it for future work.Source: §8 · p. 9

Human-in-the-Loop Learning as an Alternative to Reward Engineering

• Human-in-the-loop learning balances self-interest and Pareto-optimality as an emergent property and may be more efficient than reward engineering.The comparison is presented as support for developing human-compatible agents that learn through interactive learning.Source: §8 · p. 9

Partner-Aware Negotiation Agents

• Future work will examine adaptation during repeated interactions with the same partner and across diverse partner populations.The authors also plan to study conditions where continued advantageous negotiation depends more strongly on cooperation.Source: §8 · p. 9

Survey Questions and Results

• Participants rated our approach and RL+SL as the most fair and effective, and wanted to be represented by these models in similar negotiations.Source: §B.1 · p. 12, Figure 9 · p. 13
• Our approach was judged most compromising, with the highest “Pushover” and lowest “Difficulty” scores, while RL+SL was rated highest as an expert negotiator.Source: §B.1 · p. 12
• Subjective ratings found our approach least novel despite objective measures identifying it as most novel, and responses across subjective metrics were inconsistent.Source: §B.1 · p. 12

Choosing an Acquisition Function

• Likelihood scores each dialogue act by its log-likelihood under Bob’s model and summarizes a negotiation using the minimum, selecting the 500 lowest-likelihood negotiations for annotation.Source: §C.1 · pp. 12–13
• Compared with entropy, margin of confidence, and random acquisition, Likelihood outperformed the alternatives on advantage and novelty in evaluations using random initialization.Source: §C.1 · p. 13

C.2. Varying DL

• The datasets DL 0.65 and DL 0.78 are more diverse than DL 0.5, with DL 0.78 the most diverse, and supervised models trained on them are expected to be closer to the expert trained on DH.Source: §C.2 · p. 14
• With DL 0.65 and DL 0.78, Random acquisition performs better than Likelihood as Alice becomes more similar to the expert.Source: §C.2 · p. 14
• The expert’s average advantage for dialogues annotated during the first epoch was -2.24 for DL 0.5, -1.12 for DL 0.65, and -0.94 for DL 0.78, indicating less Pareto-optimal dialogues were increasingly flagged for higher-quality datasets.Source: §C.2 · p. 14

D. Dataset Statistics

• As dataset quality increases, Alice produces more unique utterances because the low-quality datasets were designed to contain fewer unique utterances.Source: D. Dataset Statistics · p. 14
• Dialogue length and Pareto-optimality are similar across the compared low-quality and high-quality datasets.Source: D. Dataset Statistics · p. 14

E. Example Dialogues

• RL Alice displays “badgering” behavior by repeatedly suggesting the same unfair proposal, contrasting with the examples involving our approach and RL+SL.Source: E. Example Dialogues · p. 15
• Against human partners, our approach produces more compromising proposals than RL and RL+SL.Source: Figure 15 · p. 16
• Against human partners, our approach reaches equitable and advantageous agreements, whereas RL produces unfair allocations and RL+SL can result in disagreement.Source: Figure 16 · p. 16