論文の概要: Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition

• arxiv url: http://arxiv.org/abs/2006.05606v2
• Date: Mon, 2 Nov 2020 07:21:00 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-23 04:21:27.605560
• Title: Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition
• Title（参考訳）: 確率的および逆進的エピソードMDPの知識遷移による同時学習
• Authors: Tiancheng Jin, Haipeng Luo
• Abstract要約: 我々は,世界最良保証付きの最初のアルゴリズムを開発した。 損失が逆ならば、$mathcalO(log T)$ regretを達成します。 より一般的には、中間設定で $tildemathcalO(sqrtC)$ regret を達成する。
• 参考スコア（独自算出の注目度）: 38.28925339231888
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work studies the problem of learning episodic Markov Decision Processes with known transition and bandit feedback. We develop the first algorithm with a ``best-of-both-worlds'' guarantee: it achieves $\mathcal{O}(log T)$ regret when the losses are stochastic, and simultaneously enjoys worst-case robustness with $\tilde{\mathcal{O}}(\sqrt{T})$ regret even when the losses are adversarial, where $T$ is the number of episodes. More generally, it achieves $\tilde{\mathcal{O}}(\sqrt{C})$ regret in an intermediate setting where the losses are corrupted by a total amount of $C$. Our algorithm is based on the Follow-the-Regularized-Leader method from Zimin and Neu (2013), with a novel hybrid regularizer inspired by recent works of Zimmert et al. (2019a, 2019b) for the special case of multi-armed bandits. Crucially, our regularizer admits a non-diagonal Hessian with a highly complicated inverse. Analyzing such a regularizer and deriving a particular self-bounding regret guarantee is our key technical contribution and might be of independent interest.
• Abstract（参考訳）: 本研究は、既知の遷移とバンディットフィードバックを用いたエピソディックマルコフ決定過程の学習の問題を研究する。 損失が確率的であれば$\mathcal{O}(log T)$後悔を達成し、損失が逆数であっても$\tilde{\mathcal{O}}(\sqrt{T})$後悔を享受する。 より一般的には、損失が合計$C$によって破損する中間設定で$\tilde{\mathcal{O}}(\sqrt{C})$ regretを達成する。 このアルゴリズムは Zimin と Neu (2013) の Follow-the-Regularized-Leader 法に基づいており、Zimmert et al. (2019a, 2019b) の最近の研究から着想を得た新しいハイブリッド正規化器を用いている。 重要なことに、我々の正則化器は、非常に複雑な逆数を持つ非対角ヘッセンを許容する。 このような正規化剤を分析して、特定の自発的な後悔の保証を導出することは、私たちの重要な技術的貢献であり、独立した関心を持つかもしれない。

関連論文リスト

• No-Regret Online Reinforcement Learning with Adversarial Losses and Transitions [39.864174754882754]
  対戦型マルコフ決定プロセスのための既存のオンライン学習アルゴリズムは、T$ラウンドのインタラクションの後、後悔して$O(sqrtT)を達成します。 これは、対向遷移関数が非回帰学習を不可能にすることが示されているためである。 我々は、$widetildeO(sqrtT + CtextsfP)$ regretというアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-05-27T06:10:17Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
  論文  参考訳（メタデータ） (2023-05-15T05:37:32Z)
• Weighted Tallying Bandits: Overcoming Intractability via Repeated Exposure Optimality [46.445321251991096]
  推薦システムやクラウドソーシングアプリケーションでは、人間の好みや能力はアルゴリズムの最近の行動の関数であることが多い。 我々は、この設定を一般化するWeighted Tallying Bandit (WTB)を導入し、アクションの損失が、前回の$m$のタイムステップで腕が演奏された回数のエンフ和関数であることを要求して、この設定を一般化する。 我々は、$K$アクションと水平線$T$の問題に対して、逐次除去アルゴリズムの簡単な変更は、$O left( sqrtKT + m+)を持つことを示した。
  論文  参考訳（メタデータ） (2023-05-04T15:59:43Z)
• On Submodular Contextual Bandits [92.45432756301231]
  作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。 Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
  論文  参考訳（メタデータ） (2021-12-03T21:42:33Z)
• The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition [49.78053380710322]
  我々は,エピソードT$でマルコフ決定過程を学習する上で,両世界の最良の問題を考える。 最近の[Jin and Luo, 2020]による研究は、固定遷移が分かっているときにこの目標を達成する。 本研究では,同じFollow-the-Regularized-Leader(textFTRL$)フレームワークを新しいテクニックのセットと組み合わせることで,この問題を解決する。
  論文  参考訳（メタデータ） (2021-06-08T05:46:35Z)
• Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case [29.99619764839178]
  敵の費用と未知の遷移を伴う最短経路問題に対して,大きな進展をみせている。 具体的には、全情報設定を後悔する$widetildeO(sqrtS3A2DT_star K)を実現するアルゴリズムを開発する。 私たちはまた、最も難しい組み合わせとして、敵のコストによる盗聴フィードバックと未知の移行を最初に検討しています。
  論文  参考訳（メタデータ） (2021-02-10T06:33:04Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。 各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。 我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
  論文  参考訳（メタデータ） (2021-01-31T16:49:07Z)
• Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition [37.6975819766632]
  我々は、敵対コストと既知の移行で最短経路問題を研究します。 ミニマックスの後悔は,全情報設定と盗聴フィードバック設定に対して$widetildeO(sqrtDTstar K)$および$widetildeO(sqrtDTstar SA K)$であることを示す。
  論文  参考訳（メタデータ） (2020-12-07T20:55:28Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  マルコフ決定過程(CMDP)に対するオンライン学習の検討 本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。 我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
  論文  参考訳（メタデータ） (2020-03-02T05:02:23Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。