Nego-Evol: Evolving Negotiation Strategies through Iterative Search and Policy Optimization

Large Language Model (LLM)-powered agents often struggle to adapt to goal- oriented open-domain scenarios like negotiation because of static datasets or pre- defined strategies. Existing methods suffer from limitations including: (i) they rely on static fine-tuning datasets, preventing continuous enhancement; (ii) they lack effective exploration mechanisms to discover and flexibly apply strategies. We propose Nego-Evol, an evolution framework that combines environment ini- tialization for foundational skills and environment modeling for strategy explo- ration. Crucially, this process emerges novel negotiation strategies along with improving goal achievement. Extensive experiments on CraigslistBargain and PersuasionForGood benchmarks show that Nego-Evol consistently outperforms both prompt-based and training-based baselines, achieving significant gains in success rate and other negotiation quality metrics. Nego-Evol presents a promis- ing paradigm for evolving LLM agents that can learn, adapt, and innovate beyond the boundaries of human-provided demonstrations.