  The problem of online learning and optimization of unknown Markov jump affine
models is considered. An online learning policy, referred to as Markovian
simultaneous perturbations stochastic approximation (MSPSA), is proposed for
two different optimization objectives: (i) the quadratic cost minimization of
the regulation problem and (ii) the revenue (profit) maximization problem. It
is shown that the regret of MSPSA grows at the order of the square root of the
learning horizon. Furthermore, by the use of van Trees inequality, it is shown
that the regret of any policy grows no slower than that of MSPSA, making MSPSA
an order optimal learning policy. In addition, it is also shown that the MSPSA
policy converges to the optimal control input almost surely as well as in the
mean square sense. Simulation results are presented to illustrate the regret
growth rate of MSPSA and to show that MSPSA can offer significant gain over the
greedy certainty equivalent approach.
