反馈延迟技术破解 Adversarial MDP 遗留遗憾界难题
Introducing Feedback Delays to Non-Delayed Adversarial MDPs: Optimal $\sqrt S$ and $\sqrt K$ Dependencies in Tabular and Linear AMDPs
做强化学习理论的应该看看这篇：作者在对抗 MDP 里主动引入反馈延迟，反而免费换来了 √S 和 √K 两处最优遗憾界。表格情形填了多年开放问题的缺口，线性情形把五年卡在 K^3/4 的记录推到 K^1/2，GRR 这个技巧以后估计会被反复引用。
一篇 arXiv 论文研究了未知转移和 bandit 反馈下的 Adversarial Markov Decision Processes（AMDP）遗憾最小化问题。表格情形此前最优遗憾为 Õ(HS√(AK))，与下界 Ω(H√(SAK)) 之间的 √S 差距长期悬而未决；线性情形（d 维特征）经过五年改进，无模拟器的高效算法遗憾仍停留在 Õ(K^3/4)。
论文的核心是“引入反馈延迟”技术：不用历史数据直接估计当前策略的 Q 函数，而是像环境施加了延迟那样，用未来 episode 的数据估计 Q 函数、同时继续更新策略，且这一延迟不带来额外开销。配套的 Geometric Resampling with Rejection（GRR）处理延迟期间的策略变化，并对访问概率做截断，避免在稀少 state-action 对上出现超长延迟。
借助这一统一技术，表格 AMDP 达到 Õ(poly(H)√(SAK)) 遗憾，解决了上述开放问题；线性 AMDP 达到 Õ(poly(d,H)√K)，首个对 K 最优的高效算法。结果还自然推广到总延迟为 𝔇 的 delayed AMDP，给出对 S 与 𝔇、以及对 K 与 𝔇 同时最优的首批界。
Introducing Feedback Delays to Non-Delayed Adversarial MDPs: Optimal $\sqrt S$ and $\sqrt K$ Dependencies in Tabular and Linear AMDPs
We study regret minimization in episodic Adversarial Markov Decision Processes (AMDPs) with unknown transitions and bandit feedback. In tabular AMDPs with $S$ states, $A$ actions, and horizon $H$, the best known $K$-episode regret is $\tilde O(HS\sqrt{AK})$, whose $\sqrt S$ gap to the $Ω(H\sqrt{SAK})$ lower bound has long remained open. In linear AMDPs with $d$-dimensional features, after a five-year line of improvements starting from $K^{14/15}$, computationally efficient algorithms without a simulator or exploratory assumptions still only attain $\tilde O(K^{3/4})$ regret. A common challenge in both settings is to estimate the Q-function of a changing policy: past data comes from earlier policies that differ from (and are correlated with) the current one, while freezing the policy for future episodes worsens the dependency on $K$. We instead propose a general technique called introduced feedback delays: we estimate the Q-function of the policy using future episodes while still updating the policy, as if the feedback were delayed. While feedback delays are usually an obstacle imposed by the environment, here they are introduced voluntarily and, perhaps surprisingly, come at no extra cost. We develop Geometric Resampling with Rejection (GRR) to account for policy changes during the delay, and threshold the visitation probabilities to avoid long delays on rarely visited state-action pairs. With this unified technique, our policy optimization algorithms achieve, with high probability, $\tilde O(\text{poly}(H)\sqrt{SAK})$ regret in tabular AMDPs, resolving the open problem; and $\tilde O(\text{poly}(d,H)\sqrt K)$ regret in linear AMDPs, giving the first efficient algorithm optimal in $K$. They also naturally extend to delayed AMDPs with a total feedback delay $\mathfrak D$, yielding the first bounds optimal in $S$ and $\mathfrak D$ (tabular) and in $K$ and $\mathfrak D$ (linear).
本条情报归属 AITOP「论文」核心追踪栏目。在跨区域产业观察坐标中，该动态直接关联「AI 开发者工具链、Coding Agent 与工程化实践」研究主线，反映出当前技术演进与商业落地的最新风向。涉及核心实体与技术议题包括：AMDP、强化学习理论、遗憾最小化、GRR，读者可通过下方标签进入对应专题页查阅历史脉络与关联对比。
信源核验说明：本文原始线索采编自「arXiv cs.AI」（@Aarush Kulkarni, Khang Nguyen, William Chang, Yan Dai），经 AITOP 多维评分管线结构化提炼。