We are interested in developing autonomous agents capable of reasoning based on experience and improving their negotiation behavior incrementally. Learning in negotiation is closely coupled with the issue of how to model the overall negotiation process, i.e., what negotiation protocols are adopted. Standard gametheoretic models (Osborne and Rubinstein 1994) tend to focus on outcomes of negotiation in contrast to the negotiation process itself. DAI research (Rosenschein and Zlotkin 1994) emphasizes special protocols articulating compromises while trying to minimize the potential interactions or communications of the involved agents. Since we are motivated by a different set of research issues, such as including effective learning mechanisms in the negotiation process, we adopt a different modeling framework, i.e., a sequential decision making paradigm (Bertsekas 1995; Cyert and DeGroot 1987).