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 fullbandit 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.