Towards Optimal Regret In Adversarial Linear Mdps With Bandit Feedback

Abstract

We study online reinforcement learning in linear Markov decision processes with adversarial losses and bandit feedback, without prior knowledge on transitions or access to simulators. We introduce two algorithms that achieve improved regret performance compared to existing approaches. The first algorithm, although computationally inefficient, ensures a regret of \(\widetilde\{\mathcal\{O\}\}\left(\sqrt\{K\}\right)\), where \(K\) is the number of episodes. This is the first result with the optimal \(K\) dependence in the considered setting. The second algorithm, which is based on the policy optimization framework, guarantees a regret of \(\widetilde\{\mathcal\{O\}\}\left(K^\{\frac\{3\}\{4\}\} \right)\) and is computationally efficient. Both our results significantly improve over the state-of-the-art: a computationally inefficient algorithm by Kong et al. [2023] with \(\widetilde\{\mathcal\{O\}\}\left(K^\{\frac\{4\}\{5\}\}+poly\left(\frac\{1\}\{\lambda_\{\min\}\}\right) \right)\) regret,

Stats

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

Related papers

• Near-optimal Regret Using Policy Optimization In Online Mdps With Aggregate Bandit Feedback (2025)0.00
• Near-optimal Regret For Adversarial MDP With Delayed Bandit Feedback (2022)0.00
• Refined Regret For Adversarial Mdps With Linear Function Approximation (2023)0.00
• Rate-optimal Policy Optimization For Linear Markov Decision Processes (2023)0.00
• Online Markov Decision Processes With Aggregate Bandit Feedback (2021)0.00
• Improved Algorithm For Adversarial Linear Mixture Mdps With Bandit Feedback And Unknown Transition (2024)0.00
• Learning Adversarial Markov Decision Processes With Delayed Feedback (2020)0.00
• Improved Regret For Efficient Online Reinforcement Learning With Linear Function Approximation (2023)0.00