Learning Adversarial Markov Decision Processes With Delayed Feedback

Abstract

Reinforcement learning typically assumes that agents observe feedback for their actions immediately, but in many real-world applications (like recommendation systems) feedback is observed in delay. This paper studies online learning in episodic Markov decision processes (MDPs) with unknown transitions, adversarially changing costs and unrestricted delayed feedback. That is, the costs and trajectory of episode \(k\) are revealed to the learner only in the end of episode \(k + d^k\), where the delays \(d^k\) are neither identical nor bounded, and are chosen by an oblivious adversary. We present novel algorithms based on policy optimization that achieve near-optimal high-probability regret of \(\sqrt\{K + D\}\) under full-information feedback, where \(K\) is the number of episodes and \(D = \sum_\{k\} d^k\) is the total delay. Under bandit feedback, we prove similar \(\sqrt\{K + D\}\) regret assuming the costs are stochastic, and \((K + D)^\{2/3\}\) regret in the general case. We are the

Stats

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

Related papers

• Near-optimal Regret For Adversarial MDP With Delayed Bandit Feedback (2022)0.00
• Online Markov Decision Processes With Aggregate Bandit Feedback (2021)0.00
• Towards Optimal Regret In Adversarial Linear Mdps With Bandit Feedback (2023)0.00
• Dynamic Regret Of Online Markov Decision Processes (2022)0.00
• Online Reinforcement Learning In Markov Decision Process Using Linear Programming (2023)3.58
• Reinforcement Learning With Delayed, Composite, And Partially Anonymous Reward (2023)0.00
• Online Convex Optimization In Adversarial Markov Decision Processes (2019)0.00
• Efficient Policy Learning For Non-stationary Mdps Under Adversarial Manipulation (2019)0.00