A discrete on-line monotone estimation algorithm

In the paper Papadaki & Powell (2002) we introduced an adaptive dynamic programming algorithm to estimate the monotone value functions for the problem of batch service of homogeneous customers at a service station. The algorithm uses an updating scheme that takes advantage of the monotone structure of the function by imposing a monotonicity-preserving step. In this paper we introduce an algorithm (DOME) that uses this monotonicity-preserving step to approximate discrete monotone functions. Our algorithm requires sampling a discrete function and using Monte Carlo estimates to update the function. It is a known result that sampling a discrete function on each point of its domain infinitely often converges to the correct function as long as standard requirements on the stepsize are maintained. Imposing a monotonicity-preserving step raises anew the question of convergence. We prove convergence of such an algorithm.