This paper studies adaptive bilateral negotiation between software agents in e-commerce environments. Specifically, we assume that the agents are self-interested, the environment is dynamic, and both agents have deadlines. Such dynamism means that the agents? negotiation parameters(such as deadlines and reservation prices) are functions of both the state of the encounter and the environment. Given this, we develop an algorithm that the negotiating agents can use to adapt their strategies to changes in the environment in order to reach an agreement within their specific deadlines and before the resources available for negotiation are exhausted. In more detail, we formally define an adaptive negotiation model and cast it as a Markov Decision Process. Using a value iteration algorithm, we then indicate a novel solution technique for determining optimal policies for the negotiation problem without explicit knowledge of the dynamics of the system. We also solve a representative negotiation decision problem using this technique and show that it is a promising approach for analyzing negotiations in dynamic settings. Finally, through empirical evaluation, we show that the agents using our algorithm learn a negotiation strategy that adapts to the environment and enables them to reach agreements in a timely manner.