Warm-up Free Policy Optimization: Improved Regret In Linear Markov Decision Processes

Abstract

Policy Optimization (PO) methods are among the most popular Reinforcement Learning (RL) algorithms in practice. Recently, Sherman et al. [2023a] proposed a PO-based algorithm with rate-optimal regret guarantees under the linear Markov Decision Process (MDP) model. However, their algorithm relies on a costly pure exploration warm-up phase that is hard to implement in practice. This paper eliminates this undesired warm-up phase, replacing it with a simple and efficient contraction mechanism. Our PO algorithm achieves rate-optimal regret with improved dependence on the other parameters of the problem (horizon and function approximation dimension) in two fundamental settings: adversarial losses with full-information feedback and stochastic losses with bandit feedback.

Stats

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

Related papers

• Delay-adapted Policy Optimization And Improved Regret For Adversarial MDP With Delayed Bandit Feedback (2023)0.00
• Policy Optimization As Online Learning With Mediator Feedback (2020)0.00
• A Theoretical Analysis Of Optimistic Proximal Policy Optimization In Linear Markov Decision Processes (2023)0.00
• Provably Efficient Exploration In Policy Optimization (2019)0.00
• Cautiously Optimistic Policy Optimization And Exploration With Linear Function Approximation (2021)0.00
• Simple Policy Optimization (2024)0.00
• Optimistic Policy Optimization Is Provably Efficient In Non-stationary Mdps (2021)0.00
• Policy Optimization With Model-based Explorations (2018)5.84