論文の概要: Eluder-based Regret for Stochastic Contextual MDPs

• arxiv url: http://arxiv.org/abs/2211.14932v3
• Date: Wed, 29 May 2024 08:57:58 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-31 02:41:05.695220
• Title: Eluder-based Regret for Stochastic Contextual MDPs
• Title（参考訳）: 確率的文脈 MDP のためのエルダーベースレグレット
• Authors: Orin Levy, Asaf Cassel, Alon Cohen, Yishay Mansour,
• Abstract要約: 文脈マルコフ決定過程(CMDP)における後悔最小化のためのE-UC$3$RLアルゴリズムを提案する。 我々のアルゴリズムは効率的であり(効率的なオフライン回帰オラクルを仮定すると)、$ widetildeO(H3 sqrtT |S| |A|d_mathrmE(mathcalP)$の後悔の保証を享受する。
• 参考スコア（独自算出の注目度）: 43.19667415823089
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present the E-UC$^3$RL algorithm for regret minimization in Stochastic Contextual Markov Decision Processes (CMDPs). The algorithm operates under the minimal assumptions of realizable function class and access to \emph{offline} least squares and log loss regression oracles. Our algorithm is efficient (assuming efficient offline regression oracles) and enjoys a regret guarantee of $ \widetilde{O}(H^3 \sqrt{T |S| |A|d_{\mathrm{E}}(\mathcal{P}) \log (|\mathcal{F}| |\mathcal{P}|/ \delta) )}) , $ with $T$ being the number of episodes, $S$ the state space, $A$ the action space, $H$ the horizon, $\mathcal{P}$ and $\mathcal{F}$ are finite function classes used to approximate the context-dependent dynamics and rewards, respectively, and $d_{\mathrm{E}}(\mathcal{P})$ is the Eluder dimension of $\mathcal{P}$ w.r.t the Hellinger distance. To the best of our knowledge, our algorithm is the first efficient and rate-optimal regret minimization algorithm for CMDPs that operates under the general offline function approximation setting. In addition, we extend the Eluder dimension to general bounded metrics which may be of separate interest.
• Abstract（参考訳）: 本稿では,確率的マルコフ決定過程(CMDP)における後悔最小化のためのE-UC$^3$RLアルゴリズムを提案する。 このアルゴリズムは、実現可能な関数クラスと \emph{offline} 最小二乗およびログ損失回帰オラクルへのアクセスという最小の仮定の下で機能する。 我々のアルゴリズムは効率が良く(効率的なオフライン回帰オラクルを仮定すると)、$ \widetilde{O}(H^3 \sqrt{T |S| |A|d_{\mathrm{E}}(\mathcal{P}) \log (|\mathcal{F}||\mathcal{P}|/\delta) )} の後悔を保証する。 我々の知る限り、我々のアルゴリズムは、一般的なオフライン関数近似設定の下で動作しているCMDPに対する、最初の効率的かつレート最適後悔最小化アルゴリズムである。 さらに、エルダー次元を別の興味を持つような一般有界測度に拡張する。

関連論文リスト

• Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation [3.2703356989962518]
  非線型関数近似を用いたモデルに基づく強化学習について検討する。 本研究では,無限水平平均逆法と割引逆法の両方に有効である確率効率のよい値反復型アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-06-19T15:29:14Z)
• Achieving Tractable Minimax Optimal Regret in Average Reward MDPs [19.663336027878408]
  我々は,$widetildemathrmO(sqrtmathrmsp(h*) S A T)$のミニマックス最適後悔を伴う最初の抽出可能なアルゴリズムを提案する。 注目すべきは、我々のアルゴリズムは$mathrmsp(h*)$に関する事前情報を必要としないことである。
  論文  参考訳（メタデータ） (2024-06-03T11:53:44Z)
• A Doubly Robust Approach to Sparse Reinforcement Learning [19.68978899041642]
  エピソードスパークリニアマルコフ決定過程(SMDP)に対する新しい後悔アルゴリズムを提案する。 提案アルゴリズムは$tildeO(sigma-1_min s_star H sqrtN)$である。
  論文  参考訳（メタデータ） (2023-10-23T18:52:17Z)
• Efficient Rate Optimal Regret for Adversarial Contextual MDPs Using Online Function Approximation [47.18926328995424]
  我々は,敵対的文脈 MDP における後悔最小化のためのOMG-CMDP!アルゴリズムを提案する。 我々のアルゴリズムは効率的であり(効率的なオンライン回帰オラクルを仮定する)、近似誤差に対して単純で堅牢である。
  論文  参考訳（メタデータ） (2023-03-02T18:27:00Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Private Isotonic Regression [54.32252900997422]
  部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。 約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。 上記の境界は本質的に最良であることを示す。
  論文  参考訳（メタデータ） (2022-10-27T05:08:07Z)
• Optimism in Face of a Context: Regret Guarantees for Stochastic Contextual MDP [46.86114958340962]
  我々は,最小到達可能性仮定の下での文脈的MDPに対する後悔のアルゴリズムを提案する。 我々のアプローチは、一般関数近似を用いた文脈的MDPに適用された最初の楽観的アプローチである。
  論文  参考訳（メタデータ） (2022-07-22T15:00:15Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)

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

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