A Reduction from Reinforcement Learning to No-Regret Online Learning

2019/11/14 by Cheng, Ching-An, Combes, Remi Tachet des, Boots, Byron +1
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1911.05873

Abstract

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. We demonstrate this idea by devising a simple RL algorithm based on mirror descent and the generative-model oracle. For any γ-discounted tabular RL problem, with probability at least 1-δ, it learns an ε-optimal policy using at most O(\frac|S||A|log(\frac1δ)(1-γ)⁴ε²) samples. Furthermore, this algorithm admits a direct extension to linearly parameterized function approximators for large-scale applications, with computation and sample complexities independent of |S|,|A|, though at the cost of potential approximation bias.

Related

• Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation
• What can online reinforcement learning with function approximation benefit from general coverage conditions?
• Settling the Sample Complexity of Online Reinforcement Learning
• Online Model Selection for Reinforcement Learning with Function Approximation
• Value Function Approximations via Kernel Embeddings for No-Regret Reinforcement Learning