Introducing Feedback Delays to Non-Delayed Adversarial MDPs: Optimal $\sqrt S$ and $\sqrt K$ Dependencies in Tabular and Linear AMDPs

AI 摘要

研究者针对带有未知状态转移和bandit反馈的对抗性马尔可夫决策过程（AMDP），提出一种名为“引入反馈延迟”的技术：主动把当前策略的Q函数估计推迟到未来回合进行，并配合带拒绝的几何重采样（GRR）处理延迟期间策略变化，同时对访问概率设阈值以避免稀有状态-动作对造成过长延迟。基于该技术，表格型AMDP的遗憾上界达到约O(poly(H)√(SAK))，解决了与下界之间长期存在的√S差距；线性AMDP首次获得在K上最优的高效算法，遗憾约为O(poly(d,H)√K)，并可推广到总延迟为D的延迟AMDP。