Ergodic Learning Algorithms

This chapter presents an analysis of general non-linear reward-penalty ergodic-N _R-P Ealgorithms. The basic property that characterizes this class of algorithms is that all the states under this class of algorithms are non-absorbing. The now classic linear reward-penalty — LE_R−P algorithm is a special case of this algorithm. It is well known [C1] that this LE_R−P algorithm is only expedient. Using the theory of Markov processes that evolve by small steps [N14] a variety of characterizations of the process p(k) k ≥ 0 such as the evolution of the mean and variance and in fact its actual sample path behavior are given. As a by-product, it is proved that there exists a proper choice of parameters and functions such that the NE_R−P algorithm is ε-optimal.