Theory for automatic learning under partially observed Markov-dependent noise

Abstract

A vigorous branch of automatic learning is directed at the task of locating a global minimum of an unknown multimodal function f( theta ) on the basis of noisy observations L( theta (i))=f( theta (i))+W( theta (i)) taken at sequentially-chosen control points ( theta (i)). In all preceding convergence deviations known to the authors, the noise is postulated to depend on the past only through control selection. Here they allow the observation noise sequence to be stochastically dependent, in particular, a function of an unknown underlying Markov decision process, the observations being the stagewise losses. In a sense, in order to be made precise, the algorithm offered is shown to attain asymptotically optimal performance, and rates are assured. A motivating example from queueing theory is offered, and connections with classical problems of Markov control theory and other disciplines are mentioned.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>