  We consider an online learning problem where the learner interacts with a
Markov decision process in a sequence of episodes, where the reward function is
allowed to change between episodes in an adversarial manner and the learner
only gets to observe the rewards associated with its actions. We allow the
state space to be arbitrarily large, but we assume that all action-value
functions can be represented as linear functions in terms of a known
low-dimensional feature map, and that the learner has access to a simulator of
the environment that allows generating trajectories from the true MDP dynamics.
Our main contribution is developing a computationally efficient algorithm that
we call MDP-LinExp3, and prove that its regret is bounded by
$\widetilde{\mathcal{O}}\big(H^2 T^{2/3} (dK)^{1/3}\big)$, where $T$ is the
number of episodes, $H$ is the number of steps in each episode, $K$ is the
number of actions, and $d$ is the dimension of the feature map. We also show
that the regret can be improved to $\widetilde{\mathcal{O}}\big(H^2
\sqrt{TdK}\big)$ under much stronger assumptions on the MDP dynamics. To our
knowledge, MDP-LinExp3 is the first provably efficient algorithm for this
problem setting.
