論文の概要: Achieving Tractable Minimax Optimal Regret in Average Reward MDPs

• arxiv url: http://arxiv.org/abs/2406.01234v1
• Date: Mon, 3 Jun 2024 11:53:44 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-06 01:18:57.160484
• Title: Achieving Tractable Minimax Optimal Regret in Average Reward MDPs
• Title（参考訳）: 平均リワードMDPにおけるトラクタブルミニマックス最適レグレットの実現
• Authors: Victor Boone, Zihan Zhang,
• Abstract要約: 我々は,$widetildemathrmO(sqrtmathrmsp(h*) S A T)$のミニマックス最適後悔を伴う最初の抽出可能なアルゴリズムを提案する。 注目すべきは、我々のアルゴリズムは$mathrmsp(h*)$に関する事前情報を必要としないことである。
• 参考スコア（独自算出の注目度）: 19.663336027878408
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In recent years, significant attention has been directed towards learning average-reward Markov Decision Processes (MDPs). However, existing algorithms either suffer from sub-optimal regret guarantees or computational inefficiencies. In this paper, we present the first tractable algorithm with minimax optimal regret of $\widetilde{\mathrm{O}}(\sqrt{\mathrm{sp}(h^*) S A T})$, where $\mathrm{sp}(h^*)$ is the span of the optimal bias function $h^*$, $S \times A$ is the size of the state-action space and $T$ the number of learning steps. Remarkably, our algorithm does not require prior information on $\mathrm{sp}(h^*)$. Our algorithm relies on a novel subroutine, Projected Mitigated Extended Value Iteration (PMEVI), to compute bias-constrained optimal policies efficiently. This subroutine can be applied to various previous algorithms to improve regret bounds.
• Abstract（参考訳）: 近年, 平均回帰マルコフ決定過程(MDP)の学習に注目が集まっている。 しかし、既存のアルゴリズムは、過度な後悔の保証や計算の非効率に悩まされている。 本稿では、最小限の極小残差が$\widetilde{\mathrm{O}}(\sqrt{\mathrm{sp}(h^*) S A T})$, ここで、$\mathrm{sp}(h^*)$は最適バイアス関数$h^*$, $S \times A$は状態-作用空間のサイズであり、学習ステップの回数は$T$である。 注目すべきは、我々のアルゴリズムは$\mathrm{sp}(h^*)$に関する事前情報を必要としないことである。 我々のアルゴリズムは、バイアス制約された最適ポリシーを効率的に計算するために、新しいサブルーチンであるPMEVI(Projected Mitigated Extended Value Iteration)に依存している。 このサブルーチンは、様々な過去のアルゴリズムに適用して、後悔の限界を改善することができる。

関連論文リスト

• Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation [1.8416014644193066]
  ベルマン最適条件下で線形マルコフ決定過程(MDP)と線形混合MDPを学習するアルゴリズムを提案する。 線形MDPに対する我々のアルゴリズムは、$widetildemathcalO(d3/2mathrmsp(v*)sqrtT)$ over $T$タイムステップの最もよく知られた後悔の上限を達成する。 線形混合 MDP に対して、我々のアルゴリズムは、$widetildemathcalO(dcdotmathrm) の後悔境界に達する。
  論文  参考訳（メタデータ） (2024-09-16T23:13:42Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• 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)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。 本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
  論文  参考訳（メタデータ） (2023-02-22T20:21:25Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints [39.715977181666766]
  本研究では,無限水平平均回帰マルコフ決定過程(MDP)のコスト制約による後悔について検討する。 我々のアルゴリズムはエルゴディックMDPに対して$widetildeO(sqrtT)$ regret and constant constraint violationを保証します。 これらは、MDPをコスト制約で弱い通信を行うための最初の証明可能なアルゴリズムである。
  論文  参考訳（メタデータ） (2022-01-31T23:52:34Z)
• Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
  citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
  論文  参考訳（メタデータ） (2021-12-21T01:54:17Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)

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

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