論文の概要: Efficiently Solving Discounted MDPs with Predictions on Transition Matrices

• arxiv url: http://arxiv.org/abs/2502.15345v1
• Date: Fri, 21 Feb 2025 09:59:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-24 19:42:14.941097
• Title: Efficiently Solving Discounted MDPs with Predictions on Transition Matrices
• Title（参考訳）: 遷移行列の予測による分散MDPの効率的な解法
• Authors: Lixing Lyu, Jiashuo Jiang, Wang Chi Cheung,
• Abstract要約: 生成モデルに基づくDMDP(Discounted Markov Decision Processs)について検討した。 DMDPの解法において,遷移行列上での予測がサンプル効率をいかに向上させるかを検討するための新しい枠組みを提案する。
• 参考スコア（独自算出の注目度）: 6.199300239433395
• License:
• Abstract: We study infinite-horizon Discounted Markov Decision Processes (DMDPs) under a generative model. Motivated by the Algorithm with Advice framework Mitzenmacher and Vassilvitskii 2022, we propose a novel framework to investigate how a prediction on the transition matrix can enhance the sample efficiency in solving DMDPs and improve sample complexity bounds. We focus on the DMDPs with $N$ state-action pairs and discounted factor $\gamma$. Firstly, we provide an impossibility result that, without prior knowledge of the prediction accuracy, no sampling policy can compute an $\epsilon$-optimal policy with a sample complexity bound better than $\tilde{O}((1-\gamma)^{-3} N\epsilon^{-2})$, which matches the state-of-the-art minimax sample complexity bound with no prediction. In complement, we propose an algorithm based on minimax optimization techniques that leverages the prediction on the transition matrix. Our algorithm achieves a sample complexity bound depending on the prediction error, and the bound is uniformly better than $\tilde{O}((1-\gamma)^{-4} N \epsilon^{-2})$, the previous best result derived from convex optimization methods. These theoretical findings are further supported by our numerical experiments.
• Abstract（参考訳）: 生成モデルを用いて,無限水平非カウントマルコフ決定過程(DMDP)について検討する。 The Algorithm with Advice framework Mitzenmacher and Vassilvitskii 2022, we propose a novel framework to investigated how a prediction on the transition matrix can enhance the sample efficiency in solve DMDPs and improve sample complexity bounds。 DMDPは$N$のステートアクションペアと割引係数$\gamma$で焦点を合わせます。 まず, 予測精度の事前知識がなければ, サンプリングポリシが$\epsilon$-optimal Policyを, $\tilde{O}((1-\gamma)^{-3} N\epsilon^{-2})$より大きい値で計算することは不可能である。 本稿では,遷移行列の予測を利用するミニマックス最適化手法に基づくアルゴリズムを提案する。 提案アルゴリズムは, 予測誤差に依存したサンプルの複雑性を達成し, 境界値が, 凸最適化法から導いた前の最良の結果である$\tilde{O}((1-\gamma)^{-4} N \epsilon^{-2})$よりも一様であることを示す。 これらの理論的知見は、我々の数値実験によってさらに裏付けられている。

関連論文リスト

• The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysis [6.996002801232415]
  平均回帰マルコフ決定過程において,$varepsilon$-optimal Policyを学習するためのプラグインアプローチのサンプル複雑性について検討した。 この問題の最も単純なアルゴリズムであるにもかかわらず、プラグインのアプローチは理論上は分析されていない。
  論文  参考訳（メタデータ） (2024-10-10T05:08:14Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Stochastic regularized majorization-minimization with weakly convex and multi-convex surrogates [0.0]
  提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。 非テンション依存データ設定の下で, 各種手法の収束点を求める。
  論文  参考訳（メタデータ） (2022-01-05T15:17:35Z)
• A stochastic linearized proximal method of multipliers for convex stochastic optimization with expectation constraints [8.133190610747974]
  計算可能近似型アルゴリズム,すなわち乗算器の線形化近近凸法を提案する。 予備的な数値計算の結果は,提案アルゴリズムの性能を示すものである。
  論文  参考訳（メタデータ） (2021-06-22T07:24:17Z)
• Towards Tight Bounds on the Sample Complexity of Average-reward MDPs [39.01663172393174]
  生成モデルにアクセス可能な無限水平平均回帰マルコフ決定過程の最適方針を求める。 状態-作用対あたりのサンプルを$widetildeO(t_mathrmmix epsilon-3)$ (oblivious) で解決するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-13T17:18:11Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)

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

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