  Online learning algorithms are designed to perform in non-stationary
environments, but generally there is no notion of a dynamic state to model
constraints on current and future actions as a function of past actions.
State-based models are common in stochastic control settings, but commonly used
frameworks such as Markov Decision Processes (MDPs) assume a known stationary
environment. In recent years, there has been a growing interest in combining
the above two frameworks and considering an MDP setting in which the cost
function is allowed to change arbitrarily after each time step. However, most
of the work in this area has been algorithmic: given a problem, one would
develop an algorithm almost from scratch. Moreover, the presence of the state
and the assumption of an arbitrarily varying environment complicate both the
theoretical analysis and the development of computationally efficient methods.
This paper describes a broad extension of the ideas proposed by Rakhlin et al.
to give a general framework for deriving algorithms in an MDP setting with
arbitrarily changing costs. This framework leads to a unifying view of existing
methods and provides a general procedure for constructing new ones. Several new
methods are presented, and one of them is shown to have important advantages
over a similar method developed from scratch via an online version of
approximate dynamic programming.
