Research map / Bandits and online learning / Contextual bandits and Thompson sampling
A Contextual Combinatorial Bandit Approach to Negotiation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes NegUCB, a contextual combinatorial bandit with hidden states and kernel regression for full-bandit feedback to learn negotiation strategies, with sub-linear regret and experiments on ANAC, resource allocation, and CivRealm trading.
Problem
Learning negotiation strategies faces the exploration-exploitation dilemma, very large combinatorial bid action spaces, partially observed counterpart profiles, and complicated acceptance functions.
Approach
Formulates negotiation as contextual combinatorial bandits with full-bandit (aggregate acceptance) feedback; items are arms and bids are super arms. NegUCB adds latent hidden states per negotiator pair and kernel regression, alternating between estimating hidden states and parameters, with UCB exploration bonus.
Key results
- On CivRealm trading, NegUCB's tuned exploration rate 0.1 and SE kernel with sigma=1 are chosen; NegUCB shows clear acceptance-rate advantages over baselines LinUCB and KernelUCB.
- In the resource allocation simulation, NegUCB shows lower cumulative regret and higher acceptance rate than LinUCB, FactorUCB, KernelUCB and an RL baseline, which stays below 0.6 acceptance after 20000 steps.
- Theory: regret bound is sub-linear in the number of steps and independent of bid cardinality under full-bandit feedback.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use NegUCB instead of the representative baselines | Negotiation strategies · ANAC domain 00–49 (remaining 44 domains) | negotiation steps to reach a deal | Helped |
| Use NegUCB instead of the compared algorithms | Resource allocation · Resource allocation task | acceptance rate | Helped |
| Use NegUCB instead of the compared algorithms | CivRealm technology trading · CivRealm | acceptance rate | Helped |
| Increase exploration | NegUCB and the compared algorithms · Resource allocation task | cumulative theoretical regret | Mixed |
| Train the reinforcement-learning negotiation method | Reinforcement-learning negotiation method · Resource allocation task | acceptance rate | Hurt |
| Use exploration in the other baselines | FactorUCB, KernelUCB, and the other baselines excluding LinUCB and NegUCB · CivRealm | acceptance rate | No clear effect |
| Use the SE kernel with σ=1 | NegUCB · CivRealm | acceptance rate | Helped |
Surprising findings
- In the CivRealm case study, Portugal accepted a bid with net negative income (-27), which the authors attribute to unobserved hidden states.
- Apart from LinUCB, KernelUCB and NegUCB, the other baselines did not improve with increased exploration on the CivRealm trading task.
Limitations
- Assumes the negotiation target is known at each step; may not apply to planning-heavy tasks where negotiation is only a sub-action.
- Relies on linear-in-features assumption for the bid extraction function psi and mild assumptions for the regret bound.
- Benefit function is simplified to a binary constraint set, so handcrafted benefit functions are not studied.
Experimental setup
Datasets: ANAC negotiation domains (50 domains) simulated resource allocation data CivRealm technology trading
Benchmarks: ANAC domains 00-49 resource allocation simulation CivRealm trading
Metrics: negotiation steps to deal cumulative theoretical regret acceptance regret acceptance rate
Baselines: ANAC agent LinUCB FactorUCB KernelUCB reinforcement learning-based negotiation method
Builds on: LinUCB KernelUCB FactorUCB CUCB
Closest papers by meaning
- Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation (NeurIPS 2026 · similarity 0.87)
- Active Context Selection Improves Simple Regret in Contextual Bandits (NeurIPS 2026 · similarity 0.86)
- Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure (NeurIPS 2025 · similarity 0.86)
- Stochastic contextual bandits with graph feedback: from independence number to MAS number (NeurIPS 2024 · similarity 0.85)
- Neural Dueling Bandits: Preference-Based Optimization with Human Feedback (ICLR 2025 · similarity 0.85)
- Bandits with Preference Feedback: A Stackelberg Game Perspective (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.