Epsilon-optimal stubborn learning mechanisms

The learning machine presented is an automaton whose structure changes with time and is assumed to be interacting with a random environment. The machine is essentially a stubborn machine, i.e. once the machine has chosen a particular action it increases the probability of choosing the action irrespective of whether the response from the environment was favorable or unfavorable. However, this increase in the action probability takes place in a systematic and methodical way, so that the machine ultimately learns the best action that the environment offers. It is shown that the learning mechanism is ε-optimal and that the probability that it will choose the optimal action converges uniformly to unity. The mathematical tools used in the proof are quite novel to the field of learning. Various simulation results that demonstrate the properties of stubbornly learning mechanisms are also presented. Such mechanisms are shown to be inferior to learning machines that merely ignore the penalty responses of the environment. Some open problems are also presented