  Many machine learning tasks can be solved by minimizing a convex function of
an occupancy measure over the policies that generate them. These include
reinforcement learning, imitation learning, among others. This more general
paradigm is called the Concave Utility Reinforcement Learning problem (CURL).
Since CURL invalidates classical Bellman equations, it requires new algorithms.
We introduce MD-CURL, a new algorithm for CURL in a finite horizon Markov
decision process. MD-CURL is inspired by mirror descent and uses a non-standard
regularization to achieve convergence guarantees and a simple closed-form
solution, eliminating the need for computationally expensive projection steps
typically found in mirror descent approaches. We then extend CURL to an online
learning scenario and present Greedy MD-CURL, a new method adapting MD-CURL to
an online, episode-based setting with partially unknown dynamics. Like MD-CURL,
the online version Greedy MD-CURL benefits from low computational complexity,
while guaranteeing sub-linear or even logarithmic regret, depending on the
level of information available on the underlying dynamics.
