  In this paper we study the problem of tracking the mean of a piecewise
stationary sequence of independent random variables. First we consider the case
where the transition times are known and show that a direct running average
performs the tracking in short time and with high accuracy. We then use a
single valued weighted running average with a tunable parameter for the case
when transition times are unknown and establish deviation bounds for the
tracking accuracy. Our result has applications in choosing the optimal rewards
for the multiarmed bandit scenario.
