arXiv cs.AI· Aarush Kulkarni, Khang Nguyen, William Chang, Yan Dai·· 1 天前AI 评分18
引入反馈延迟解决非延迟对抗性 MDP：表格与线性 AMDP 实现最优 √S 与 √K 依赖
Introducing Feedback Delays to Non-Delayed Adversarial MDPs: Optimal $\sqrt S$ and $\sqrt K$ Dependencies in Tabular and Linear AMDPs
AI 导读
研究者提出“引入反馈延迟”技术，用未来回合估计当前策略的 Q 函数同时继续更新策略，并配合 Geometric Resampling with Rejection（GRR）处理延迟期内的策略变化。
正文 · AI 翻译
摘要：我们研究在转移未知且具有 bandit 反馈的片段式对抗马尔可夫决策过程（AMDPs）中的遗憾最小化问题。在具有 $S$ 个状态、$A$ 个动作和时域 $H$ 的表格型 AMDP 中，已知最佳的 $K$ 片段遗憾为 $\tilde O(HS\sqrt{AK})$，其与 $\Omega(H\sqrt{SAK})$ 下界之间的 $\sqrt S$ 差距长期未解决。在具有 $d$ 维特征的线性 AMDP 中，从 $K^{14/15}$ 开始历经五年的改进，无需模拟器或探索性假设的计算高效算法仍只能达到 $\tilde O(K^{3/4})$ 遗憾。
这两种设置中的一个共同挑战是估计变化策略的 Q 函数：过去的数据来自与当前策略不同（且相关）的早期策略，而为未来片段冻结策略会恶化对 $K$ 的依赖。我们转而提出一种称为引入反馈延迟的通用技术：我们使用未来片段估计策略的 Q 函数，同时仍然更新策略，就像反馈被延迟一样。虽然反馈延迟通常是环境施加的障碍，但在这里它是自愿引入的，而且也许令人惊讶的是，不会带来额外成本。我们开发了带拒绝的几何重采样（GRR）来处理延迟期间策略的变化，并对访问概率设置阈值，以避免在很少访问的状态-动作对上出现长延迟。
借助这一统一技术，我们的策略优化算法以高概率在表格型 AMDP 中实现 $\tilde O(\text{poly}(H)\sqrt{SAK})$ 遗憾，解决了该开放问题；并在线性 AMDP 中实现 $\tilde O(\text{poly}(d,H)\sqrt K)$ 遗憾，给出了第一个在 $K$ 上最优的高效算法。它们还自然扩展到总反馈延迟为 $\mathfrak D$ 的延迟 AMDP，产生了第一个在 $S$ 和 $\mathfrak D$（表格型）以及在 $K$ 和 $\mathfrak D$（线性）上最优的界。
| 学科： | 机器学习（cs.LG）；人工智能（cs.AI）；机器学习（stat.ML） |
| 引用为： | arXiv:2611.17214 [cs.LG] |
| （或 arXiv:2611.17214v1 [cs.LG] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2611.17214 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Yan Dai [查看电子邮件]
[v1]
2026年11月12日星期四 18:10:46 UTC（76 KB）
来源：arXiv cs.AI · arxiv.org