Resource title

A discrete on-line monotone estimation algorithm

Resource image

image for OpenScout resource :: A discrete on-line monotone estimation algorithm

Resource description

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.

Resource author

Resource publisher

Resource publish date

Resource language


Resource content type


Resource resource URL

Resource license