論文の概要: Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation

• arxiv url: http://arxiv.org/abs/2404.12648v1
• Date: Fri, 19 Apr 2024 06:24:22 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-22 16:05:28.719470
• Title: Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation
• Title（参考訳）: 一般関数近似を用いた無限水平平均回帰MDPのサンプル効率学習
• Authors: Jianliang He, Han Zhong, Zhuoran Yang,
• Abstract要約: 一般関数近似の文脈において,無限水平平均逆マルコフ決定過程(AMDP)について検討する。 最適化最適化(LOOP)と呼ばれる新しいアルゴリズムフレームワークを提案する。 我々は LOOP がサブ線形 $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret を達成することを示す。
• 参考スコア（独自算出の注目度）: 53.17668583030862
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study infinite-horizon average-reward Markov decision processes (AMDPs) in the context of general function approximation. Specifically, we propose a novel algorithmic framework named Local-fitted Optimization with OPtimism (LOOP), which incorporates both model-based and value-based incarnations. In particular, LOOP features a novel construction of confidence sets and a low-switching policy updating scheme, which are tailored to the average-reward and function approximation setting. Moreover, for AMDPs, we propose a novel complexity measure -- average-reward generalized eluder coefficient (AGEC) -- which captures the challenge of exploration in AMDPs with general function approximation. Such a complexity measure encompasses almost all previously known tractable AMDP models, such as linear AMDPs and linear mixture AMDPs, and also includes newly identified cases such as kernel AMDPs and AMDPs with Bellman eluder dimensions. Using AGEC, we prove that LOOP achieves a sublinear $\tilde{\mathcal{O}}(\mathrm{poly}(d, \mathrm{sp}(V^*)) \sqrt{T\beta} )$ regret, where $d$ and $\beta$ correspond to AGEC and log-covering number of the hypothesis class respectively, $\mathrm{sp}(V^*)$ is the span of the optimal state bias function, $T$ denotes the number of steps, and $\tilde{\mathcal{O}} (\cdot) $ omits logarithmic factors. When specialized to concrete AMDP models, our regret bounds are comparable to those established by the existing algorithms designed specifically for these special cases. To the best of our knowledge, this paper presents the first comprehensive theoretical framework capable of handling nearly all AMDPs.
• Abstract（参考訳）: 一般関数近似の文脈において,無限水平平均逆マルコフ決定過程(AMDP)について検討する。 具体的には、モデルベースと値ベースの両方を組み込んだLocal-fitted Optimization with OP(Local-fitted Optimization with Optimism)という新しいアルゴリズムフレームワークを提案する。 特に、LOOPは、信頼セットの新規な構築と、平均回帰および関数近似設定に合わせて調整された低スイッチングポリシー更新スキームを特徴としている。 さらに, AMDPに対して, 一般関数近似を用いたAMDPにおける探索の課題を捉えた, 平均逆一般化ユーダー係数 (AGEC) を新たに提案する。 このような複雑性尺度は、線形AMDPや線形混合AMDPなど、これまで知られていたほぼすべてのAMDPモデルを含み、さらにベルマンエリューダー次元を持つカーネルAMDPやAMDPといった新たなケースも含む。 AGEC を用いて LOOP がサブリニア $\tilde{\mathcal{O}}(\mathrm{poly}(d, \mathrm{sp}(V^*)) \sqrt{T\beta} )$ regret, ここで $d$ と $\beta$ はそれぞれ AGEC に対応し、仮説クラスのログ化数を $\mathrm{sp}(V^*)$ は最適状態バイアス関数のスパンであり、$T$ はステップ数を表し、$\tilde{\mathcal{O}} (\cdot) $ omits logarithmic factor である。 具体的なAMDPモデルに特化する場合は、これらの特別なケースに特化して設計された既存のアルゴリズムが確立したものに匹敵する。 そこで本研究では,ほぼすべてのAMDPを扱える最初の包括的な理論的枠組みについて述べる。

関連論文リスト

• Efficient Learning of POMDPs with Known Observation Model in Average-Reward Setting [56.92178753201331]
  我々は,POMDPパラメータを信念に基づくポリシを用いて収集したサンプルから学習することのできる観測・認識スペクトル(OAS)推定手法を提案する。 提案するOAS-UCRLアルゴリズムに対して,OASプロシージャの整合性を示し,$mathcalO(sqrtT log(T)$の残差保証を証明した。
  論文  参考訳（メタデータ） (2024-10-02T08:46:34Z)
• Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Exploration [87.53543137162488]
  我々はtextttMEX というオンライン強化学習(オンラインRL)フレームワークを提案する。 textttMEXは、自動的に探索エクスプロイトのバランスをとりながら、見積もりと計画コンポーネントを統合する。 様々な MuJoCo 環境では,ベースラインを安定的なマージンで上回り,十分な報酬を得られる。
  論文  参考訳（メタデータ） (2023-05-29T17:25:26Z)
• Sharper Analysis for Minibatch Stochastic Proximal Point Methods: Stability, Smoothness, and Deviation [41.082982732100696]
  我々は,凸複合リスク最小化問題の解法として,近位点法(M-SPP)のミニバッチ変種について検討した。 ミニバッチサイズが$n$で二次数が$T$のM-SPPは、予想外収束の速さを楽しむことを示す。 小さい$n$-large-$T$設定では、この結果はSPP型アプローチの最もよく知られた結果を大幅に改善する。
  論文  参考訳（メタデータ） (2023-01-09T00:13:34Z)
• Efficient semidefinite bounds for multi-label discrete graphical models [6.226454551201676]
  このようなモデルにおける主要なクエリの1つは、Posteri(MAP)ネットワークのコストに関するSDPWCSP関数を特定することである。 従来の二重化制約手法と,行ごとの更新に基づく専用SDP/Monteiroスタイルの手法を検討する。
  論文  参考訳（メタデータ） (2021-11-24T13:38:34Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。 リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。 このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
  論文  参考訳（メタデータ） (2021-02-27T19:28:39Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。 一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
  論文  参考訳（メタデータ） (2020-12-04T15:36:29Z)
• Estimation in Tensor Ising Models [5.161531917413708]
  N$ノード上の分布から1つのサンプルを与えられた$p$-tensor Isingモデルの自然パラメータを推定する問題を考える。 特に、$sqrt N$-consistency of the MPL estimate in the $p$-spin Sherrington-Kirkpatrick (SK) model。 我々は、$p$-tensor Curie-Weiss モデルの特別な場合における MPL 推定の正確なゆらぎを導出する。
  論文  参考訳（メタデータ） (2020-08-29T00:06:58Z)
• A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regret [44.374427255708135]
  無限水平平均逆マルコフ決定過程(MDP)のモデルフリーアルゴリズムである探索強化Q-ラーニング(EE-QL)を提案する。 EE-QLは、最適平均報酬のオンライン集中近似が利用可能であると仮定する。 これは、エルゴード的な仮定なしに$O(sqrt T)$後悔を達成する最初のモデル自由学習アルゴリズムであり、対数的因子を除いて、下位境界の$T$と一致する。
  論文  参考訳（メタデータ） (2020-06-08T05:09:32Z)
• Theoretical Convergence of Multi-Step Model-Agnostic Meta-Learning [63.64636047748605]
  一般的なマルチステップMAMLアルゴリズムに対して収束保証を提供するための新しい理論フレームワークを開発する。 特に,本研究の結果は,収束を保証するためには,内部段階のステップを逆比例して$N$の内段ステップを選択する必要があることを示唆している。
  論文  参考訳（メタデータ） (2020-02-18T19:17:54Z)

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

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