A Structure-aware Online Learning Algorithm for Markov Decision
  Processes
  To overcome the curse of dimensionality and curse of modeling in Dynamic
Programming (DP) methods for solving classical Markov Decision Process (MDP)
problems, Reinforcement Learning (RL) algorithms are popular. In this paper, we
consider an infinite-horizon average reward MDP problem and prove the
optimality of the threshold policy under certain conditions. Traditional RL
techniques do not exploit the threshold nature of optimal policy while
learning. In this paper, we propose a new RL algorithm which utilizes the known
threshold structure of the optimal policy while learning by reducing the
feasible policy space. We establish that the proposed algorithm converges to
the optimal policy. It provides a significant improvement in convergence speed
and computational and storage complexity over traditional RL algorithms. The
proposed technique can be applied to a wide variety of optimization problems
that include energy efficient data transmission and management of queues. We
exhibit the improvement in convergence speed of the proposed algorithm over
other RL algorithms through simulations.
