Learning Adversarial Markov Decision Processes with Delayed Feedback
Learning Adversarial Markov Decision Processes with Delayed Feedback
复制标题
DOI：
10.1609/aaai.v36i7.20690
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Tal Lancewicki;Aviv A. Rosenberg;Y. Mansour
中科院分区：
文献类型：
--
作者：
Tal Lancewicki;Aviv A. Rosenberg;Y. Mansour
强化学习通常假设代理立即观察到他们行动的反馈，但在许多真实世界的应用(如推荐系统)中，反馈是延迟观察的。研究了转移未知、代价对抗性变化且反馈无约束的情景马尔可夫决策过程(MDP)的在线学习问题。也就是说，只有在k+dᵏ集的结尾才能向学习者揭示k集的成本和轨迹，其中延迟dᵏ既不相等也不有界，并且是由不经意的对手选择的。我们提出了一种基于策略优化的新算法，在全信息反馈下获得接近最优的(K+D)≈ᐟ？的高概率后悔，其中K是剧集数，D=∑ₖdᵏ是总时延。在强盗反馈下，我们证明了类似的(K+D)？ᐟ？后悔假设成本是随机的，并且在一般情况下证明了(K+D)？ᐟ？后悔。我们首先考虑了具有延迟反馈的MDP的重要设置下的后悔最小化问题。
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.