Delay-adapted Policy Optimization And Improved Regret For Adversarial MDP With Delayed Bandit Feedback

Abstract

Policy Optimization (PO) is one of the most popular methods in Reinforcement Learning (RL). Thus, theoretical guarantees for PO algorithms have become especially important to the RL community. In this paper, we study PO in adversarial MDPs with a challenge that arises in almost every real-world application -- \textit\{delayed bandit feedback\}. We give the first near-optimal regret bounds for PO in tabular MDPs, and may even surpass state-of-the-art (which uses less efficient methods). Our novel Delay-Adapted PO (DAPO) is easy to implement and to generalize, allowing us to extend our algorithm to: (i) infinite state space under the assumption of linear \(Q\)-function, proving the first regret bounds for delayed feedback with function approximation. (ii) deep RL, demonstrating its effectiveness in experiments on MuJoCo domains.

Stats

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

Related papers

• Warm-up Free Policy Optimization: Improved Regret In Linear Markov Decision Processes (2024)0.00
• Near-optimal Regret For Adversarial MDP With Delayed Bandit Feedback (2022)0.00
• Near-optimal Regret Using Policy Optimization In Online Mdps With Aggregate Bandit Feedback (2025)0.00
• A Theoretical Analysis Of Optimistic Proximal Policy Optimization In Linear Markov Decision Processes (2023)0.00
• Towards Optimal Regret In Adversarial Linear Mdps With Bandit Feedback (2023)0.00
• Policy Optimization As Online Learning With Mediator Feedback (2020)0.00
• Learning Adversarial Markov Decision Processes With Delayed Feedback (2020)0.00
• Near-optimal Policy Optimization Algorithms For Learning Adversarial Linear Mixture Mdps (2021)0.00