A Reduction from Reinforcement Learning to No-Regret Online Learning

Understand

We present a reduction from reinforcement learning (RL) to no-regret online learning based on the saddle-point formulation of RL, by which "any" online algorithm with sublinear regret can generate policies with provable performance guarantees.

• This new perspective decouples the RL problem into two parts: regret minimization and function approximation.
• The first part admits a standard online-learning analysis, and the second part can be quantified independently of the learning algorithm.
• Therefore, the proposed reduction can be used as a tool to systematically design new RL algorithms.