Improved Regret For Efficient Online Reinforcement Learning With Linear Function Approximation

Abstract

We study reinforcement learning with linear function approximation and adversarially changing cost functions, a setup that has mostly been considered under simplifying assumptions such as full information feedback or exploratory conditions.We present a computationally efficient policy optimization algorithm for the challenging general setting of unknown dynamics and bandit feedback, featuring a combination of mirror-descent and least squares policy evaluation in an auxiliary MDP used to compute exploration bonuses.Our algorithm obtains an \(\widetilde O(K^\{6/7\})\) regret bound, improving significantly over previous state-of-the-art of \(\widetilde O (K^\{14/15\})\) in this setting. In addition, we present a version of the same algorithm under the assumption a simulator of the environment is available to the learner (but otherwise no exploratory assumptions are made), and prove it obtains state-of-the-art regret of \(\widetilde O (K^\{2/3\})\).

Stats

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

Related papers

• Towards Optimal Regret In Adversarial Linear Mdps With Bandit Feedback (2023)0.00
• Refined Regret For Adversarial Mdps With Linear Function Approximation (2023)0.00
• First-order Regret In Reinforcement Learning With Linear Function Approximation: A Robust Estimation Approach (2021)0.00
• Distributionally Robust Offline Reinforcement Learning With Linear Function Approximation (2022)0.00
• Provably Efficient Reinforcement Learning With Linear Function Approximation (2019)11.76
• Nearly Minimax Optimal Offline Reinforcement Learning With Linear Function Approximation: Single-agent MDP And Markov Game (2022)0.00
• Nonstationary Reinforcement Learning With Linear Function Approximation (2020)0.00
• Online Sub-sampling For Reinforcement Learning With General Function Approximation (2021)0.00