論文の概要: Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedback
- arxiv url: http://arxiv.org/abs/2201.13172v1
- Date: Mon, 31 Jan 2022 12:34:26 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-01 17:31:41.604826
- Title: Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedback
- Title(参考訳): 遅延帯域フィードバックを持つ逆MDPのほぼ最適レグレット
- Authors: Tiancheng Jin and Tal Lancewicki and Haipeng Luo and Yishay Mansour
and Aviv Rosenberg
- Abstract要約: エピソードマルコフ決定過程(MDP)におけるオンライン学習について検討した。
ほぼ最適の$sqrtK + D$ regret, where $K$ is the number of episodes, $D = sum_k=1K dk$ is the total delay。
- 参考スコア(独自算出の注目度): 67.63049551992816
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The standard assumption in reinforcement learning (RL) is that agents observe
feedback for their actions immediately. However, in practice feedback is often
observed in delay. This paper studies online learning in episodic Markov
decision process (MDP) with unknown transitions, adversarially changing costs,
and unrestricted delayed bandit feedback. More precisely, the feedback for the
agent in episode $k$ is revealed only in the end of episode $k + d^k$, where
the delay $d^k$ can be changing over episodes and chosen by an oblivious
adversary. We present the first algorithms that achieve near-optimal $\sqrt{K +
D}$ regret, where $K$ is the number of episodes and $D = \sum_{k=1}^K d^k$ is
the total delay, significantly improving upon the best known regret bound of
$(K + D)^{2/3}$.
- Abstract(参考訳): 強化学習(RL)における標準的な前提は、エージェントが直ちに行動に対するフィードバックを観察することである。
しかし、実際には、フィードバックはしばしば遅延して観察される。
本稿では,未知の遷移を伴うマルコフ決定過程(mdp)におけるオンライン学習,非制限的バンディットフィードバックについて検討する。
より正確には、エピソード$k$のエージェントに対するフィードバックは、エピソード$k + d^k$の最後にのみ明らかにされる。
ここで、$k$ はエピソード数であり、$d = \sum_{k=1}^k d^k$ は総遅延であり、最もよく知られた後悔値 $(k + d)^{2/3}$ によって大幅に改善される。
関連論文リスト
- Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback [49.84060509296641]
オンライン有限水平マルコフ決定過程を逆向きに変化した損失と総括的帯域幅フィードバック(フルバンド幅)を用いて研究する。
この種のフィードバックの下では、エージェントは、軌跡内の各中間段階における個々の損失よりも、軌跡全体に生じる総損失のみを観察する。
この設定のための最初のポリシー最適化アルゴリズムを紹介します。
論文 参考訳(メタデータ) (2025-02-06T12:03:24Z) - Reinforcement Learning with Segment Feedback [56.54271464134885]
状態ごとの反応フィードバックと軌道フィードバックのギャップを埋める一般的なパラダイムを提供するRLというモデルを考える。
バイナリフィードバックの下では、$m$のセグメント数の増加は指数率で後悔を減少させるが、驚くべきことに、和フィードバックの下では、$m$の増加は後悔を著しく減少させるものではない。
論文 参考訳(メタデータ) (2025-02-03T23:08:42Z) - Delay as Payoff in MAB [40.65658965074464]
エージェントが受信した支払いが遅延し、直接遅延の大きさに対応する古典的マルチアーム帯域幅問題(MAB)の変種について検討する。
当社の主なコントリビューションは、コストと報酬の設定の両方に関して、上と下の境界の厳格さです。
私たちの後悔は、コストシナリオと報酬シナリオの違いを強調し、コストシナリオの改善が報酬よりも重要であることを示すことです。
論文 参考訳(メタデータ) (2024-08-27T15:52:52Z) - Adversarial Bandits with Multi-User Delayed Feedback: Theory and
Application [17.64363983613468]
我々は,マルチユーザ遅延フィードバックを用いた逆MAB問題を定式化し,修正されたEXP3アルゴリズム MUD-EXP3 を設計する。
本稿では,複数のユーザからの遅延フィードバック結果について考察し,内部分布に制限を加えることなく検討する。
論文 参考訳(メタデータ) (2023-10-17T12:08:15Z) - 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) - Learning Adversarial Markov Decision Processes with Delayed Feedback [45.86354980347581]
私たちは、未知の移行、逆転的なコストの変動、制限のない遅延フィードバックを備えた典型的マルコフ決定プロセス(MDP)におけるオンライン学習を検討します。
本論文では,$widetilde O ( sqrtK + sqrtD )$ のほぼ最適高確率後悔を実現するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-12-29T16:47:42Z) - 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) - Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。
任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
論文 参考訳(メタデータ) (2020-02-23T09:10:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。