A Reduction From Reinforcement Learning To No-regret Online Learning

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 \(\gamma\)-discounted tabular RL problem, with probability at least \(1-\delta\), it learns an \(\epsilon\)-optimal policy using at most \(\tilde\{O\}\left(\frac\{|\mathcal\{S\}||\mathcal\{A\}|log(\frac\{1\}\{\delta\})\}\{(1-\gamma)^4\epsilon^2\}\right)\) samples. Furthermore, this a

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keycheng2019a

Related papers

• Improved Regret For Efficient Online Reinforcement Learning With Linear Function Approximation (2023)0.00
• Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-regret Learning In Markov Games (2022)0.00
• Near-optimal Offline Reinforcement Learning Via Double Variance Reduction (2021)0.00
• Fast Rates For The Regret Of Offline Reinforcement Learning (2021)2.26
• Model-based Reinforcement Learning With Double Oracle Efficiency In Policy Optimization And Offline Estimation (2026)0.00
• The Best Of Both Worlds: Reinforcement Learning With Logarithmic Regret And Policy Switches (2022)0.00
• Sharper Model-free Reinforcement Learning For Average-reward Markov Decision Processes (2023)0.00
• Pessimistic Nonlinear Least-squares Value Iteration For Offline Reinforcement Learning (2023)0.00