This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Nascimento, J. M. Articles by Powell, W. B. Search for Related Content

An Optimal Approximate Dynamic Programming Algorithm for the Lagged Asset Acquisition Problem

Department of Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08544
Department of Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08544
jnascime{at}alumni.princeton.edu
powell{at}princeton.edu

We consider a multistage asset acquisition problem where assets are purchased now, at a price that varies randomly over time, to be used to satisfy a random demand at a particular point in time in the future. We provide a rare proof of convergence for an approximate dynamic programming algorithm using pure exploitation, where the states we visit depend on the decisions produced by solving the approximate problem. The resulting algorithm does not require knowing the probability distribution of prices or demands, nor does it require any assumptions about its functional form. The algorithm and its proof rely on the fact that the true value function is a family of piecewise linear concave functions.

Key Words: stochastic learning and adaptive control; stochastic approximation; approximate dynamic programming
History: Received: August 21, 2006; revision received: June 19, 2008;