在部分对抗性环境里，设计了稳定学习算法，能应对少数关键步骤的恶意干扰。
Online Learning in MDPs with Partially Adversarial Transitions and Losses
- 用条件占据度量保证跨回合稳定性，应对部分对抗性转移。
- 首个实现近似 $\tilde{O}(H S^Λ\sqrt{K S A^{Λ+1}})$ 递减的在线学习算法。
- 适用于安全关键系统，如自动驾驶中偶发异常状态场景。
我们研究马尔可夫决策过程（MDP）中的在线强化学习问题，其转移函数在大多数步骤上为随机性，但在每轮中固定若干个步骤 $Λ$ 上可能呈现对抗性。该模型刻画了整体稳定但存在少数脆弱点的环境。本文提出“条件占据度量”，即使在对抗性转移下也能保持跨轮次的稳定性，并基于此设计两种算法。第一种处理任意分布的对抗步骤，达到 $ ilde{O}(H S^Λ oot{2}{K S A^{Λ+1}})$ 的遗憾；第二种假设对抗步骤连续，将 $S$ 的依赖优化至 $ ilde{O}(H\sqrt{K S^{3} A^{Λ+1}})$。此外，我们提出一种 $K^{2/3}$- regret 减少方法，无需事先知道哪些步骤是 $Λ$ 个对抗步骤。还对完全对抗情形（$Λ=H-1$）下的全信息与带状反馈设置进行了遗憾率分析，给出了近乎匹配的上下界，强化了现有下界，并阐明不同反馈结构对学习难度的影响。
原文摘要 · Abstract (English)
We study reinforcement learning in MDPs whose transition function is stochastic at most steps but may behave adversarially at a fixed subset of $Λ$ steps per episode. This model captures environments that are stable except at a few vulnerable points. We introduce \emph{conditioned occupancy measures}, which remain stable across episodes even with adversarial transitions, and use them to design two algorithms. The first handles arbitrary adversarial steps and achieves regret $\tilde{O}(H S^Λ\sqrt{K S A^{Λ+1}})$, where $K$ is the number of episodes, $S$ is the number of state, $A$ is the number of actions and $H$ is the episode's horizon. The second, assuming the adversarial steps are consecutive, improves the dependence on $S$ to $\tilde{O}(H\sqrt{K S^{3} A^{Λ+1}})$. We further give a $K^{2/3}$-regret reduction that removes the need to know which steps are the $Λ$ adversarial steps. We also characterize the regret of adversarial MDPs in the \emph{fully adversarial} setting ($Λ=H-1$) both for full-information and bandit feedback, and provide almost matching upper and lower bounds (slightly strengthen existing lower bounds, and clarify how different feedback structures affect the hardness of learning).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。