論文の概要: Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions

• arxiv url: http://arxiv.org/abs/2010.01374v2
• Date: Mon, 15 Feb 2021 22:44:00 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-11 08:35:12.159877
• Title: Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions
• Title（参考訳）: 線形実現可能な最適動作値関数を用いたmdp計画のための指数下限
• Authors: Gell\'ert Weisz, Philip Amortila, Csaba Szepesv\'ari
• Abstract要約: 固定水平および割引マルコフ決定過程における地域計画の問題点を考察する。 我々は、任意のサウンドプランナーが少なくとも$min(exp(Omega(d)), Omega(2H))$サンプルをfized-horizon設定で、$exp(Omega(d))$サンプルを割引設定でクエリする必要があることを示す。
• 参考スコア（独自算出の注目度）: 3.2980012891975754
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of local planning in fixed-horizon and discounted Markov Decision Processes (MDPs) with linear function approximation and a generative model under the assumption that the optimal action-value function lies in the span of a feature map that is available to the planner. Previous work has left open the question of whether there exist sound planners that need only poly(H,d) queries regardless of the MDP, where H is the horizon and d is the dimensionality of the features. We answer this question in the negative: we show that any sound planner must query at least $\min(\exp({\Omega}(d)), {\Omega}(2^H))$ samples in the fized-horizon setting and $\exp({\Omega}(d))$ samples in the discounted setting. We also show that for any ${\delta}>0$, the least-squares value iteration algorithm with $O(H^5d^{H+1}/{\delta}^2)$ queries can compute a ${\delta}$-optimal policy in the fixed-horizon setting. We discuss implications and remaining open questions.
• Abstract（参考訳）: 本稿では,固定ホリゾンおよび割引マルコフ決定過程(mdps)における局所計画の問題と,最適動作値関数がプランナーが利用可能な特徴マップの範囲内にあることを前提に,線形関数近似と生成モデルを提案する。 従来の研究は、ポリ(H,d) クエリのみを必要とする音響プランナーが存在するかどうかという疑問を、MDP によらず、H は地平線、d は特徴の次元性である。 我々は、任意のサウンドプランナーが少なくとも$\min(\exp({\omega}(d)), {\omega}(2^h))$のサンプルをfized-horizon設定で、$\exp({\omega}(d))$のサンプルをディスカウント設定で問い合わせなければならないことを示した。 また、任意の${\delta}>0$に対して、$o(h^5d^{h+1}/{\delta}^2)$クエリを持つ最小二乗値反復アルゴリズムは、固定ホリゾン設定で${\delta}$-optimalポリシーを計算することができる。 含意とオープンな質問について論じる。

関連論文リスト

• Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation [3.2703356989962518]
  非線型関数近似を用いたモデルに基づく強化学習について検討する。 本研究では,無限水平平均逆法と割引逆法の両方に有効である確率効率のよい値反復型アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-06-19T15:29:14Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討 我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
  論文  参考訳（メタデータ） (2022-10-05T22:52:00Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• TensorPlan and the Few Actions Lower Bound for Planning in MDPs under Linear Realizability of Optimal Value Functions [0.0]
  我々は,オンラインプランニングにおけるミニマックスクエリの複雑さを,固定水平決定プロセスにおける生成モデルを用いて検討する。 A=Omega(min(d1/4,H1/2)) が指数的に大きい下界を持つことを示す。
  論文  参考訳（メタデータ） (2021-10-05T17:42:46Z)
• Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally [58.463668865380946]
  状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。 rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。 Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
  論文  参考訳（メタデータ） (2021-02-25T15:50:19Z)
• Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function Approximation [92.3161051419884]
  我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。 我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。 また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
  論文  参考訳（メタデータ） (2021-02-17T18:54:08Z)
• On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function [14.205660708980988]
  固定水平マルコフ決定過程(MDP)における局所的計画の問題点を生成モデルを用いて考察する。 最近の下界は、最適ポリシーの作用値関数が線形に実現可能である場合の関連する問題は指数的なクエリ数を必要とすることを証明している。 本研究では,アクションセットが小さい場合,ポリ$(H, d)$学習が(状態値関数の実現可能性を持つ)可能であることを確かめる。
  論文  参考訳（メタデータ） (2021-02-03T13:23:15Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes [91.38793800392108]
  本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。 上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。 我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
  論文  参考訳（メタデータ） (2020-12-15T18:56:46Z)
• Nearly Minimax Optimal Reward-free Reinforcement Learning [88.75843804630772]
  本稿では、特にバッチ強化学習に適した報酬不要強化学習フレームワークと、複数の報酬関数に対するポリシーを必要とするシナリオについて検討する。 textbfStaged textbfSampling + textbfTruncated textbfPlanning (algoname) という新しい効率的なアルゴリズムを提供しています。
  論文  参考訳（メタデータ） (2020-10-12T17:51:19Z)
• A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraints [8.849815837266977]
  制約付きマルコフ決定プロセス(CMDP)は、シーケンシャルな意思決定問題を定式化する。 本稿では, 有限水平CMDPの線形計画法を利用して, 繰り返し楽観的な計画を立てるオンラインアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-23T19:30:46Z)

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

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