On Connections between Constrained Optimization and Reinforcement
  Learning
  Dynamic Programming (DP) provides standard algorithms to solve Markov
Decision Processes. However, these algorithms generally do not optimize a
scalar objective function. In this paper, we draw connections between DP and
(constrained) convex optimization. Specifically, we show clear links in the
algorithmic structure between three DP schemes and optimization algorithms. We
link Conservative Policy Iteration to Frank-Wolfe, Mirror-Descent Modified
Policy Iteration to Mirror Descent, and Politex (Policy Iteration Using Expert
Prediction) to Dual Averaging. These abstract DP schemes are representative of
a number of (deep) Reinforcement Learning (RL) algorithms. By highlighting
these connections (most of which have been noticed earlier, but in a scattered
way), we would like to encourage further studies linking RL and convex
optimization, that could lead to the design of new, more efficient, and better
understood RL algorithms.
