Learning Adversarial Linear Mixture Markov Decision Processes with Bandit Feedback and Unknown Transition

Reinforcement learning typically assumes that the agent observes feedback for its actions immediately, but in many real-world applications (like recommendation systems) the feedback is observed in delay. In this paper, we study 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 √ K + D under fullinformation feedback, where K is the number of episodes and D = k d k is the total delay. Under bandit feedback, we prove similar √ K + D regret assuming the costs are stochastic, and (K + D) 2/3 regret in the general case. We are the first to consider regret minimization in the important setting of MDPs with delayed feedback.