# A Contextual Combinatorial Bandit Approach to Negotiation

arXiv: https://arxiv.org/abs/2407.00567 · HTML: https://mlsanity.com/paper/2407.00567/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 39 references that are in the map.
- First posted on arXiv 30 Jun 2024.

## Builds on (most cited first, 15 of 15)

- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Deal or No Deal? End-to-End Learning for Negotiation Dialogues](https://mlsanity.com/paper/1706.05125/) (2017)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Deep Reinforcement Learning in Large Discrete Action Spaces](https://mlsanity.com/paper/1512.07679/) (2015)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Neural Contextual Bandits with Deep Representation and Shallow Exploration](https://mlsanity.com/paper/2012.01780/) (2020)
- [Emergent Communication through Negotiation](https://mlsanity.com/paper/1804.03980/) (2018)
- [CivRealm: A Learning and Reasoning Odyssey in Civilization for Decision-Making Agents](https://mlsanity.com/paper/2401.10568/) (2024)
- [No Press Diplomacy: Modeling Multi-Agent Gameplay](https://mlsanity.com/paper/1909.02128/) (2019)
- [Efficient Learning in Large-Scale Combinatorial Semi-Bandits](https://mlsanity.com/paper/1406.7443/) (2014)
- [Top-k Combinatorial Bandits with Full-Bandit Feedback](https://mlsanity.com/paper/1905.12624/) (2019)
- [Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback](https://mlsanity.com/paper/2302.01324/) (2023)
- [Delayed Feedback in Kernel Bandits](https://mlsanity.com/paper/2302.00392/) (2023)
- [A Deep Reinforcement Learning Approach to Concurrent Bilateral Negotiation](https://mlsanity.com/paper/2001.11785/) (2020)
- [MCTS-based Automated Negotiation Agent](https://mlsanity.com/paper/1909.09461/) (2019)

## Built on by (most cited first, 2 of 2)

- [CAE: Repurposing the Critic as an Explorer in Deep Reinforcement Learning](https://mlsanity.com/paper/2503.18980/) (2025)
- [Adaptive Bandit Algorithms for Contextual Matching Markets](https://mlsanity.com/paper/2605.28290/) (2026)

## Abstract (arXiv)

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.