論文の概要: 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}$ によって大幅に改善される。
関連論文リスト
- Delay as Payoff in MAB [40.65658965074464]
エージェントが受信した支払いが遅延し、直接遅延の大きさに対応する古典的マルチアーム帯域幅問題(MAB)の変種について検討する。
当社の主なコントリビューションは、コストと報酬の設定の両方に関して、上と下の境界の厳格さです。
私たちの後悔は、コストシナリオと報酬シナリオの違いを強調し、コストシナリオの改善が報酬よりも重要であることを示すことです。
論文 参考訳（メタデータ） (2024-08-27T15:52:52Z) - Improved Regret for Bandit Convex Optimization with Delayed Feedback [50.46856739179311]
遅延フィードバックを伴うバンド凸最適化(BCO)。
我々は,新しいアルゴリズムを開発し,一般にO(sqrtnT3/4+sqrtdT)$の後悔境界を満足していることを証明する。
提案アルゴリズムは,強い凸関数に対して$O((nT)2/3log/3T+dlog T)$に制限された後悔を改善することができることを示す。
論文 参考訳（メタデータ） (2024-02-14T13:08:26Z) - 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) - 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) - 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) - Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage
Decomposition [59.34067736545355]
有限水平型マルコフ決定過程(MDP)における強化学習問題を,S$状態,A$動作,エピソード長$H$を用いて検討した。
モデルフリーアルゴリズム UCB-Advantage を提案し、$T = KH$ および $K$ が再生すべきエピソード数である場合に $tildeO(sqrtH2SAT)$ regret を達成することを証明した。
論文 参考訳（メタデータ） (2020-04-21T14:00:06Z) - Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。
任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
論文 参考訳（メタデータ） (2020-02-23T09:10:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。