Online Learning In Mdps With Partially Adversarial Transitions And Losses

Abstract

We study reinforcement learning in MDPs whose transition function is stochastic at most steps but may behave adversarially at a fixed subset of \(\Lambda\) steps per episode. This model captures environments that are stable except at a few vulnerable points. We introduce *conditioned occupancy measures*, which remain stable across episodes even with adversarial transitions, and use them to design two algorithms. The first handles arbitrary adversarial steps and achieves regret \(\tilde\{O\}(H S^\{\Lambda\}\sqrt\{K S A^\{\Lambda+1\}\})\), where \(K\) is the number of episodes, \(S\) is the number of state, \(A\) is the number of actions and \(H\) is the episode's horizon. The second, assuming the adversarial steps are consecutive, improves the dependence on \(S\) to \(\tilde\{O\}(H\sqrt\{K S^\{3\} A^\{\Lambda+1\}\})\). We further give a \(K^\{2/3\}\)-regret reduction that removes the need to know which steps are the \(\Lambda\) adversarial steps. We also characterize the regret of adver

Stats

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

Related papers

• Efficient Policy Learning For Non-stationary Mdps Under Adversarial Manipulation (2019)0.00
• Improved Algorithm For Adversarial Linear Mixture Mdps With Bandit Feedback And Unknown Transition (2024)0.00
• Online Convex Optimization In Adversarial Markov Decision Processes (2019)0.00
• Online Reinforcement Learning In Markov Decision Process Using Linear Programming (2023)3.58
• Dynamic Regret Of Online Markov Decision Processes (2022)0.00
• Refined Regret For Adversarial Mdps With Linear Function Approximation (2023)0.00
• Towards Optimal Regret In Adversarial Linear Mdps With Bandit Feedback (2023)0.00
• Learning Adversarial Markov Decision Processes With Delayed Feedback (2020)0.00