論文の概要: TensorPlan and the Few Actions Lower Bound for Planning in MDPs under Linear Realizability of Optimal Value Functions

• arxiv url: http://arxiv.org/abs/2110.02195v1
• Date: Tue, 5 Oct 2021 17:42:46 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-06 14:28:10.864674
• Title: TensorPlan and the Few Actions Lower Bound for Planning in MDPs under Linear Realizability of Optimal Value Functions
• Title（参考訳）: 最適値関数の線形実現性を考慮したMDP計画のためのTensorPlanとFewアクション
• Authors: Gell\'ert Weisz, Csaba Szepesv\'ari, Andr\'as Gy\"orgy
• Abstract要約: 我々は,オンラインプランニングにおけるミニマックスクエリの複雑さを,固定水平決定プロセスにおける生成モデルを用いて検討する。 A=Omega(min(d1/4,H1/2)) が指数的に大きい下界を持つことを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the minimax query complexity of online planning with a generative model in fixed-horizon Markov decision processes (MDPs) with linear function approximation. Following recent works, we consider broad classes of problems where either (i) the optimal value function $v^\star$ or (ii) the optimal action-value function $q^\star$ lie in the linear span of some features; or (iii) both $v^\star$ and $q^\star$ lie in the linear span when restricted to the states reachable from the starting state. Recently, Weisz et al. (2021b) showed that under (ii) the minimax query complexity of any planning algorithm is at least exponential in the horizon $H$ or in the feature dimension $d$ when the size $A$ of the action set can be chosen to be exponential in $\min(d,H)$. On the other hand, for the setting (i), Weisz et al. (2021a) introduced TensorPlan, a planner whose query cost is polynomial in all relevant quantities when the number of actions is fixed. Among other things, these two works left open the question whether polynomial query complexity is possible when $A$ is subexponential in $min(d,H)$. In this paper we answer this question in the negative: we show that an exponentially large lower bound holds when $A=\Omega(\min(d^{1/4},H^{1/2}))$, under either (i), (ii) or (iii). In particular, this implies a perhaps surprising exponential separation of query complexity compared to the work of Du et al. (2021) who prove a polynomial upper bound when (iii) holds for all states. Furthermore, we show that the upper bound of TensorPlan can be extended to hold under (iii) and, for MDPs with deterministic transitions and stochastic rewards, also under (ii).
• Abstract（参考訳）: 線形関数近似を持つ固定ホライゾンマルコフ決定過程(mdps)における生成モデルを用いて,オンライン計画の最小クエリ複雑性を考える。 最近の研究の後、私たちは、どちらかが問題である幅広いクラスを考える。 i) 最適な値関数 $v^\star$ か (ii) 最適な作用値関数 $q^\star$ は、いくつかの特徴の線形スパンにある。 (iii) $v^\star$ と $q^\star$ は、開始状態から到達可能な状態に限定される場合の線形スパンにある。 最近のweisz et al. (2021b) では (ii)任意の計画アルゴリズムのminimaxクエリの複雑さは、アクションセットのサイズ$a$が$\min(d,h)$で指数関数になるように選択できる場合、水平方向$h$または特徴次元$d$において少なくとも指数関数的である。 一方、設定については (i), weisz et al. (2021a)は,アクション数が固定された場合,クエリコストが関連するすべての量の多項式となるプランナーtensorplanを導入した。 この2つの作業は、$a$が$min(d,h)$でサブ指数である場合、多項式クエリの複雑さが可能かどうかという疑問を投げかけた。 指数関数的に大きい下界は、$A=\Omega(\min(d^{1/4},H^{1/2}))$ がいずれかの下にあるときに成り立つことを示す。 (i) (ii) (iii) 特にこれは、多項式上界を証明した Du et al. (2021) の業績と比較して、おそらく驚くほどの指数関数的なクエリ複雑性の分離を意味する。 (iii)すべての州について。 さらに、テンソルプランの上限をアンダーホールドに拡張できることを示した。 (iii)及び決定論的推移及び確率的報酬を有するmdpについても (ii)

関連論文リスト

• Demystifying Linear MDPs and Novel Dynamics Aggregation Framework [8.087699764574788]
  線型 MDP において、$d$ は遷移確率を適切に表すために$S/U$ で制限される。 動的アグリゲーション(dynamics aggregate, 動的アグリゲーション)と呼ばれる動的に基づく新しい構造アグリゲーションフレームワークを提案する。 提案アルゴリズムは統計的効率を示し,$ tildeO (d_psi3/2 H3/2sqrt T)$, $d_psi$は集約されたサブMDPの特徴次元を表す。
  論文  参考訳（メタデータ） (2024-10-31T16:21:41Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。 本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
  論文  参考訳（メタデータ） (2023-02-22T20:21:25Z)
• 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)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes [91.38793800392108]
  本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。 上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。 我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
  論文  参考訳（メタデータ） (2020-12-15T18:56:46Z)
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation [99.59319332864129]
  最近提案された2つの線形MDP仮定で対数的後悔が達成可能であることを示す。 我々の知る限り、これらは線型関数近似を持つRLに対する最初の対数的後悔境界である。
  論文  参考訳（メタデータ） (2020-11-23T17:25:00Z)
• Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions [3.2980012891975754]
  固定水平および割引マルコフ決定過程における地域計画の問題点を考察する。 我々は、任意のサウンドプランナーが少なくとも$min(exp(Omega(d)), Omega(2H))$サンプルをfized-horizon設定で、$exp(Omega(d))$サンプルを割引設定でクエリする必要があることを示す。
  論文  参考訳（メタデータ） (2020-10-03T15:19:26Z)

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

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