Learning Adversarial Markov Decision Processes with Delayed Feedback

Authors

  • Tal Lancewicki Tel-Aviv University
  • Aviv Rosenberg Tel Aviv University
  • Yishay Mansour Tel Aviv University Google Research

DOI:

https://doi.org/10.1609/aaai.v36i7.20690

Keywords:

Machine Learning (ML)

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ᵏ, where the delays dᵏ 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 full-information feedback, where K is the number of episodes and D=∑ₖ dᵏ is the total delay. Under bandit feedback, we prove similar (K+D)¹ᐟ² regret assuming the costs are stochastic, and (K+D)²ᐟ³ regret in the general case. We are the first to consider regret minimization in the important setting of MDPs with delayed feedback.

Downloads

Published

2022-06-28

How to Cite

Lancewicki, T., Rosenberg, A., & Mansour, Y. (2022). Learning Adversarial Markov Decision Processes with Delayed Feedback. Proceedings of the AAAI Conference on Artificial Intelligence, 36(7), 7281-7289. https://doi.org/10.1609/aaai.v36i7.20690

Issue

Section

AAAI Technical Track on Machine Learning II