Negotiation serves as a cornerstone for fostering cooperation among agents with diverse interests. 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 framework to tackle a wide range of negotiation problems. Our approach leverages contextual combinatorial multi-arm bandits, with bandits resolving the exploration-exploitation dilemma and the combinatorial characteristic handles large action spaces. Building upon this framework, we introduce NegUCB, a novel method that also handles common issues such as partial observations and complex reward functions in negotiation. Notably, NegUCB is contextual and tailored for full-bandit feedback without constraints on the reward functions. Under mild assumptions, NegUCB ensures a sub-linear regret upper bound that remains independent of the negotiation bid cardinality. Experiments conducted on three representative negotiation tasks also demonstrate the superiority of our approach in learning negotiation strategies.