Reward-Based Negotiating Agent Strategies

Ryota Higa, Katsuhide Fujita, Toki Takahashi, Takumu Shimizu, Shinji NakadaiAAAI 2023 · DOI

TL;DR

This paper introduces a novel reward-based deep reinforcement learning (RL) agent strategy for bilateral multi-issue negotiations. By employing an issue-based representation and a policy network, their approach achieves comparable or superior negotiation outcomes (utility, agreement rates) compared to existing RL and heuristic methods, especially in complex, large-sized negotiation domains. This work advances automated negotiation by enabling agents to learn effective strategies without explicit utility functions, improving scalability and efficiency.

What Problem Does This Paper Address?

Automated negotiation is crucial for enabling cooperation in multi-agent systems, with applications ranging from e-markets to supply chain management. While reinforcement learning (RL) has shown promise in developing adaptive negotiation agents, existing RL approaches often rely on rich utility functions that provide detailed information about agent preferences. This can be a limitation when utility information is uncertain or ordinal. Furthermore, many current RL negotiation strategies struggle with scalability in complex, multi-issue negotiation domains, where the number of possible outcomes can be vast. The paper addresses these limitations by proposing a reward-based RL strategy that learns negotiation policies without explicit utility functions and is designed to scale effectively to larger negotiation problems.

Methods

The core contribution is a novel reward-based negotiating agent strategy built upon a multi-issue policy network trained using Proximal Policy Optimization (PPO), a stable policy gradient RL algorithm.

Key methodological aspects include:

  • End-to-End Deep RL: The agent learns directly from raw bid data and time, outputting negotiation actions (offer or accept) without requiring pre-defined utility functions or explicit opponent modeling.
  • Issue-Based State and Action Representation: To handle multi-issue negotiations and improve scalability, the state representation (including opponent's bid, self's bid, and time) and action representation (selecting offers and acceptance) are structured around individual issues. This is achieved through vectorized one-hot encodings for categorical issues and normalization for ordinal/continuous ones.
  • Multi-Issue Policy Network: A deep neural network architecture is employed, where the hidden layers form an end-to-end learning model. The output layer is designed to handle multi-issue offers, acceptance, and value predictions. This architecture is inspired by action branching techniques, allowing for more efficient learning in complex action spaces.
  • Reward-Based Learning: Unlike utility-based agents, this approach uses RL rewards (primarily the final utility upon agreement, with a penalty for no agreement) to guide learning. This makes it suitable for scenarios where utility functions are not precisely known or are difficult to define.

Datasets

The paper does not introduce new datasets. Instead, it utilizes existing negotiation environments and benchmarks, specifically mentioning the NegMAS platform and RL-baselines for evaluation. The experiments were conducted across seven domains with varying sizes (from 10 to 10⁴ outcomes) and nine different opponent types, including champions from previous Automated Negotiating Agents Competition (ANAC) events.

Key Insights and Ideas

  • Scalability without Explicit Utility: The most significant insight is that effective negotiation strategies can be learned through RL using only reward signals, without needing to explicitly model or know the agent's own utility function. This broadens the applicability of RL in negotiation.
  • Issue-Based Representation is Key: Structuring the state and action representations around individual issues is crucial for achieving scalability in multi-issue negotiation domains. This allows the agent to decompose complex problems into manageable parts.
  • Policy-Based RL Outperforms: Policy-based RL methods, particularly the proposed multi-issue policy network (MiPN), demonstrate superior performance in terms of individual utility, agreement rates, and step efficiency compared to other RL approaches and heuristic strategies, especially in large and complex domains.
  • Adaptability Through Learning: The proposed agent learns to adapt its strategy based on observed opponent behavior, effectively estimating opponent preferences and making concessions on issues critical to both parties. This adaptive behavior is a hallmark of successful RL agents.

Key Results

  • Superior Utility: The proposed MiPN agent achieved comparable or higher individual utility scores than state-of-the-art RL agents (PPO-VeNAS, VeNAS(DQN)) and heuristic approaches across various domains and opponents. Notably, MiPN outperformed others in regions with larger domain sizes.
  • High Agreement Rates: MiPN and PPO-VeNAS achieved very high agreement rates (99.9% and 99.3%, respectively), significantly higher than VeNAS(DQN) (84.0%), indicating better robustness and scalability.
  • Improved Step Efficiency: MiPN and PPO-VeNAS demonstrated higher step efficiencies, meaning they reached agreements in fewer steps, leading to faster negotiations. MiPN, in particular, balanced step efficiency with individual utility effectively.
  • Social Welfare: While not explicitly optimized for, MiPN and PPO-VeNAS achieved high social welfare, suggesting that their learned strategies indirectly promote cooperative outcomes.

Limitations and Future Work

  • Domain and Opponent Specificity: The current study focuses on essential repeated encounters with the same domains and opponents used for training. The authors acknowledge that improving negotiation settings for entirely new domains and opponents (e.g., through transfer learning or meta-learning) requires further research.
  • Reward Function Design: While the reward-based approach is a strength, the authors suggest that elaborating the reward function to explicitly consider opponent characteristics or social welfare could further enhance performance.
  • Generalization: Further investigation into machine learning techniques like transfer learning and meta-learning is needed to enable agents to generalize effectively to unseen negotiation scenarios.

Summary updated

BibTeX
@inproceedings{higa2023reward,
  author = {Ryota Higa and Katsuhide Fujita and Toki Takahashi and Takumu Shimizu and Shinji Nakadai},
  title = {{Reward-Based Negotiating Agent Strategies}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i10.26367},
}
Figure