The STAR automaton: expediency and optimality properties

We present the STack ARchitecture (STAR) automaton. It is a fixed structure, multiaction, reward-penalty learning automaton, characterized by a star-shaped state transition diagram. Each branch of the star contains D states associated with a particular action. The branches are connected to a central "neutral" state. The most general version of STAR involves probabilistic state transitions in response to reward and/or penalty, but deterministic transitions can also be used. The learning behavior of STAR results from the stack-like operation of the branches; the learning parameter is D. By mathematical analysis, it is shown that STAR with deterministic reward/probabilistic penalty and a sufficiently large D can be rendered ε-optimal in every stationary environment. By numerical simulation it is shown that in nonstationary, switching environments, STAR usually outperforms classical variable structure automata such as L_R-P, L_R-I, and L_R-εP.