論文の概要: Learning Adversarial Markov Decision Processes with Delayed Feedback
- arxiv url: http://arxiv.org/abs/2012.14843v2
- Date: Fri, 29 Jan 2021 13:10:46 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-18 20:33:25.459208
- Title: Learning Adversarial Markov Decision Processes with Delayed Feedback
- Title（参考訳）: 遅延フィードバックによる逆マルコフ決定過程の学習
- Authors: Tal Lancewicki and Aviv Rosenberg and Yishay Mansour
- Abstract要約: 私たちは、未知の移行、逆転的なコストの変動、制限のない遅延フィードバックを備えた典型的マルコフ決定プロセス(MDP)におけるオンライン学習を検討します。
本論文では,$widetilde O ( sqrtK + sqrtD )$ のほぼ最適高確率後悔を実現するアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 45.86354980347581
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Reinforcement learning typically assumes that the agent observes feedback
from the environment immediately, but in many real-world applications (like
recommendation systems) the feedback is observed in delay. Thus, we consider
online learning in episodic Markov decision processes (MDPs) with unknown
transitions, adversarially changing costs and unrestricted delayed feedback.
That is, the costs and trajectory of episode $k$ are only available at the end
of episode $k + d^k$, where the delays $d^k$ are neither identical nor bounded,
and are chosen by an adversary. We present novel algorithms based on policy
optimization that achieve near-optimal high-probability regret of $\widetilde O
( \sqrt{K} + \sqrt{D} )$ under full-information feedback, where $K$ is the
number of episodes and $D = \sum_{k} d^k$ is the total delay. Under bandit
feedback, we prove similar $\widetilde O ( \sqrt{K} + \sqrt{D} )$ regret
assuming that the costs are stochastic, and $\widetilde O ( K^{2/3} + D^{2/3}
)$ regret in the general case. To our knowledge, we are the first to consider
the important setting of delayed feedback in adversarial MDPs.
- Abstract（参考訳）: 強化学習は通常、エージェントが環境からすぐにフィードバックを観察すると仮定するが、多くの現実世界のアプリケーション(レコメンデーションシステムなど)では、フィードバックは遅延して観察される。
そこで本研究では,未知の遷移を伴うマルコフ決定過程 (mdps) におけるオンライン学習について考察する。
つまり、エピソード $k$ の費用と軌道は、エピソード $k + d^k$ の終わりにのみ利用可能であり、遅延 $d^k$ は同一でも有界でもないし、敵によって選択される。
我々は,全情報フィードバック下での$\widetilde o ( \sqrt{k} + \sqrt{d} )$ ($k$ はエピソード数,$d = \sum_{k} d^k$ は総遅延である) の最適化に基づく新しいアルゴリズムを提案する。
バンドイットフィードバックの下では、コストが確率的であると仮定して、同様の$\widetilde O ( \sqrt{K} + \sqrt{D} )$ regret を、一般の場合$\widetilde O ( K^{2/3} + D^{2/3} )$ regret を証明している。
我々の知る限り、我々は敵のMDPにおける遅延フィードバックの重要な設定を最初に検討する。
関連論文リスト
- Delay as Payoff in MAB [40.65658965074464]
エージェントが受信した支払いが遅延し、直接遅延の大きさに対応する古典的マルチアーム帯域幅問題(MAB)の変種について検討する。
当社の主なコントリビューションは、コストと報酬の設定の両方に関して、上と下の境界の厳格さです。
私たちの後悔は、コストシナリオと報酬シナリオの違いを強調し、コストシナリオの改善が報酬よりも重要であることを示すことです。
論文 参考訳（メタデータ） (2024-08-27T15:52:52Z) - Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedback [67.63049551992816]
エピソードマルコフ決定過程(MDP)におけるオンライン学習について検討した。
ほぼ最適の$sqrtK + D$ regret, where $K$ is the number of episodes, $D = sum_k=1K dk$ is the total delay。
論文 参考訳（メタデータ） (2022-01-31T12:34:26Z) - 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) - Minimax Regret for Stochastic Shortest Path [63.45407095296692]
我々は、エージェントが最小の総予想コストで目標状態に達する必要がある最短パス(SSP)問題を研究します。
この設定に対するminimaxの後悔は、$widetilde O(B_star sqrt|S| |A|K)$であり、$B_star$は任意の状態から最適なポリシーの予想コストに拘束されることを示しています。
本アルゴリズムは, 有限水平MDPにおける強化学習の新たな削減を基礎として, エピソードごとのインタイム動作を行う。
論文 参考訳（メタデータ） (2021-03-24T10:11:49Z) - 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) - 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) - Stochastic Shortest Path with Adversarially Changing Costs [57.90236104782219]
最短経路 (SSP) は計画と制御においてよく知られた問題である。
また, 時間とともにコストの逆変化を考慮に入れた逆SSPモデルを提案する。
我々は、この自然な逆SSPの設定を最初に検討し、それに対するサブ線形後悔を得る。
論文 参考訳（メタデータ） (2020-06-20T12:10:35Z) - Simultaneously Learning Stochastic and Adversarial Episodic MDPs with
Known Transition [38.28925339231888]
我々は,世界最良保証付きの最初のアルゴリズムを開発した。
損失が逆ならば、$mathcalO(log T)$ regretを達成します。
より一般的には、中間設定で $tildemathcalO(sqrtC)$ regret を達成する。
論文 参考訳（メタデータ） (2020-06-10T01:59:34Z) - Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。
任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
論文 参考訳（メタデータ） (2020-02-23T09:10:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。