A Contextual Combinatorial Bandit Approach to Negotiation
This work addresses the problem of learning effective negotiation strategies for AI agents, presenting a novel method that is incremental in combining existing bandit techniques for a specific domain.
The paper tackles the challenges of exploration-exploitation and large action spaces in negotiation by introducing a contextual combinatorial bandit formulation, resulting in the NegUCB method that achieves a sub-linear regret upper bound and demonstrates superiority in experiments on three negotiation tasks.
Learning effective negotiation strategies poses two key challenges: the exploration-exploitation dilemma and dealing with large action spaces. However, there is an absence of learning-based approaches that effectively address these challenges in negotiation. This paper introduces a comprehensive formulation to tackle various negotiation problems. Our approach leverages contextual combinatorial multi-armed bandits, with the bandits resolving the exploration-exploitation dilemma, and the combinatorial nature handles large action spaces. Building upon this formulation, we introduce NegUCB, a novel method that also handles common issues such as partial observations and complex reward functions in negotiation. NegUCB is contextual and tailored for full-bandit feedback without constraints on the reward functions. Under mild assumptions, it ensures a sub-linear regret upper bound. Experiments conducted on three negotiation tasks demonstrate the superiority of our approach.