Fugu-MT 論文翻訳(概要): Online Learning in MDPs with Partially Adversarial Transitions and Losses

論文の概要: Online Learning in MDPs with Partially Adversarial Transitions and Losses

arxiv url: http://arxiv.org/abs/2602.09474v1
Date: Tue, 10 Feb 2026 07:13:11 GMT
ステータス: 翻訳完了
システム内更新日: 2026-02-11 20:17:43.422239
Title: Online Learning in MDPs with Partially Adversarial Transitions and Losses
Title（参考訳）: 部分的に相反する遷移と損失を伴うMDPにおけるオンライン学習
Authors: Ofir Schlisselberg, Tal Lancewicki, Yishay Mansour,
Abstract要約: 遷移関数がほとんどのステップであるが,1エピソードあたり$$$の固定サブセットで逆向きに振る舞うことができるMDPの強化学習について検討した。両エピソードの相違が相変わらず安定なエンプレクショナル・コンディショニング・コンディショナー(Emphconditioned occupancy measures)を導入する。我々は,全情報フィードバックと盗賊フィードバックの両面から,敵対的MDPの反抗的設定(=H-1$)の後悔を特徴づける。
参考スコア（独自算出の注目度）: 42.59565593884281
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: 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).
Abstract（参考訳）: 我々は,ほとんどのステップにおいて遷移関数が確率的であるが,1エピソードあたり$$$の固定サブセットで逆向きに振る舞うMDPの強化学習について検討した。このモデルは、いくつかの脆弱な点を除いて安定な環境をキャプチャする。本稿では, 対向的遷移であっても, エピソード間で安定に保たれる「emph{conditioned occupancy measures」を導入し, 2つのアルゴリズムを設計する。ここで$K$はエピソードの数、$S$は状態の数、$A$はアクションの数、$H$はエピソードの水平線である。 2つ目は、逆ステップが連続であると仮定し、$S$ から $\tilde{O}(H\sqrt{K S^{3} A^{n+1}})$ への依存を改善することである。さらに、$K^{2/3}$-regret還元を与え、この還元により、どちらのステップが$=逆ステップであるかを知る必要がなくなる。また,全情報フィードバックと包括的フィードバックの両面において,emph{fully adversarial} 設定における敵対的 MDP の後悔(=H-1$)を特徴付けるとともに,ほぼ一致する上界と下界(既存の下界をわずかに強化し,異なるフィードバック構造が学習の難しさにどのように影響するかを明らかにする。

論文の概要: Online Learning in MDPs with Partially Adversarial Transitions and Losses

関連論文リスト