Blackwell Online Learning for Markov Decision Processes
  This work provides a novel interpretation of Markov Decision Processes (MDP)
from the online optimization viewpoint. In such an online optimization context,
the policy of the MDP is viewed as the decision variable while the
corresponding value function is treated as payoff feedback from the
environment. Based on this interpretation, we construct a Blackwell game
induced by MDP, which bridges the gap among regret minimization, Blackwell
approachability theory, and learning theory for MDP. Specifically, from the
approachability theory, we propose 1) Blackwell value iteration for offline
planning and 2) Blackwell $Q-$learning for online learning in MDP, both of
which are shown to converge to the optimal solution. Our theoretical guarantees
are corroborated by numerical experiments.
