Fugu-MT 論文翻訳(概要): Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor

論文の概要: Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor

arxiv url: http://arxiv.org/abs/2302.00036v1
Date: Tue, 31 Jan 2023 19:11:17 GMT
ステータス: 処理完了
システム内更新日: 2023-02-02 18:38:13.310797
Title: Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor
Title（参考訳）: Blackwell Discount Factorによる非カウントMDPのブラックウェルと平均最適性低減
Authors: Julien Grand-Cl\'ement and Marek Petrik
Abstract要約: 意思決定プロセス(MDP)におけるブラックウェル割引係数について紹介する。割引係数がブラックウェル割引係数$gamma_mathrmbw$より大きい場合、すべての割引された最適ポリシーがブラックウェルおよび平均最適となることを示す。
参考スコア（独自算出の注目度）: 13.544364903649196
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We introduce the Blackwell discount factor for Markov Decision Processes (MDPs). Classical objectives for MDPs include discounted, average, and Blackwell optimality. Many existing approaches to computing average-optimal policies solve for discounted optimal policies with a discount factor close to $1$, but they only work under strong or hard-to-verify assumptions such as ergodicity or weakly communicating MDPs. In this paper, we show that when the discount factor is larger than the Blackwell discount factor $\gamma_{\mathrm{bw}}$, all discounted optimal policies become Blackwell- and average-optimal, and we derive a general upper bound on $\gamma_{\mathrm{bw}}$. The upper bound on $\gamma_{\mathrm{bw}}$ provides the first reduction from average and Blackwell optimality to discounted optimality, without any assumptions, and new polynomial-time algorithms for average- and Blackwell-optimal policies. Our work brings new ideas from the study of polynomials and algebraic numbers to the analysis of MDPs. Our results also apply to robust MDPs, enabling the first algorithms to compute robust Blackwell-optimal policies.
Abstract（参考訳）: 我々は,マルコフ決定過程(mdps)のブラックウェル値引き係数を導入する。 MDPの古典的な目標は、割引、平均、ブラックウェルの最適性である。平均最適ポリシーを計算するための既存の多くのアプローチは、割引係数が1ドルに近い割引された最適ポリシーを解決しているが、エルゴディディティや弱いコミュニケーションのMDPのような強いあるいは検証の難しい仮定の下でのみ機能する。本稿では、割引係数がブラックウェル割引係数$\gamma_{\mathrm{bw}}$より大きい場合、すべての割引された最適ポリシーがブラックウェル最適かつ平均最適となり、$\gamma_{\mathrm{bw}}$の一般上限が導出されることを示す。上の$\gamma_{\mathrm{bw}}$の上限は、平均とブラックウェル最適性から割引された最適性への最初の還元と、平均とブラックウェル最適性に対する新しい多項式時間アルゴリズムを提供する。我々の研究は、多項式と代数数の研究からMDPの分析に新しいアイデアをもたらす。我々の結果はロバストなmdpにも適用でき、最初のアルゴリズムでロバストなブラックウェル最適ポリシーを計算できる。

関連論文リスト

Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization [37.24692425018]
Emphconstrained MDPs(CMDPs)におけるオンライン学習の研究提案アルゴリズムは, 対向型MDPに対して, 最先端のポリシー最適化アプローチを採用するプリミティブ・デュアル・スキームを実装している。
論文参考訳（メタデータ） (2024-10-03T07:54:04Z)
On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes [50.68789924454235]
我々は、平均報酬マルコフ決定過程(MDP)の文脈における政策勾配の最初の有限時間大域収束解析を示す。我々の分析によると、ポリシー勾配は、$Oleft(frac1Tright)$のサブリニアレートで最適ポリシーに収束し、$Oleft(log(T)right)$ regretに変換され、$T$は反復数を表す。
論文参考訳（メタデータ） (2024-03-11T15:25:03Z)
Span-Based Optimal Sample Complexity for Average Reward MDPs [6.996002801232415]
平均回帰マルコフ決定過程(MDP)において,$varepsilon$-optimal Policyを生成モデルで学習する際のサンプル複雑性について検討した。我々は、$widetildeOleft(SAfracH (1-gamma)2varepsilon2 right)$, ここで、$H$は最適ポリシーのバイアス関数のスパンであり、$SA$は状態作用空間の濃度である。
論文参考訳（メタデータ） (2023-11-22T15:34:44Z)
Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs [17.62509045102346]
本稿では,CMDP(Constrained Markov Decision Processs)における最適ポリシー識別問題について考察する。私たちは、モデルフリーで、後悔の少ないアルゴリズムに興味を持ち、確率の高いほぼ最適なポリシーを特定しています。オンラインCMDPのサブ線形後悔と制約違反を伴う既存のモデルフリーアルゴリズムでは、最適ポリシーに対する収束保証は提供されない。
論文参考訳（メタデータ） (2023-09-27T04:33:09Z)
Robust Average-Reward Markov Decision Processes [25.125481838479256]
我々は,不確実なセットに対して最悪の平均報酬を最適化する政策を見出すことを目標とする,堅牢な平均リワードMDPに焦点を当てる。我々は, ディスカウント型MDPを用いて, 平均回帰MDPを近似するアプローチを採っている。我々は、ロバスト平均逆 MDP に対するロバストなベルマン方程式を導出し、最適ポリシーがその解から導出できることを証明し、さらに、その解を確実に見つけ出すロバストな相対値アルゴリズムを設計する。
論文参考訳（メタデータ） (2023-01-02T19:51:55Z)
Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
論文参考訳（メタデータ） (2022-08-17T18:49:53Z)
Efficient Policy Iteration for Robust Markov Decision Processes via Regularization [49.05403412954533]
ロバストな意思決定プロセス(MDP)は、システムのダイナミクスが変化している、あるいは部分的にしか知られていない決定問題をモデル化するためのフレームワークを提供する。最近の研究は、長方形長方形の$L_p$頑健なMDPと正規化されたMDPの等価性を確立し、標準MDPと同じレベルの効率を享受する規則化されたポリシー反復スキームを導出した。本研究では、政策改善のステップに焦点をあて、欲求政策と最適なロバストなベルマン作用素のための具体的な形式を導出する。
論文参考訳（メタデータ） (2022-05-28T04:05:20Z)
Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
最適化手法の優位性は、正確な勾配が用いられるかどうかに大きく依存することを示す。次に,政策最適化におけるコミット率の概念を紹介する。第三に、外部のオラクル情報がない場合には、収束を加速するために幾何を利用することと、最適性をほぼ確実に達成することとの間に本質的にトレードオフがあることが示される。
論文参考訳（メタデータ） (2021-10-29T06:35:44Z)
Softmax Policy Gradient Methods Can Take Exponential Time to Converge [60.98700344526674]
Softmax Policy gradient(PG)メソッドは、現代の強化学習におけるポリシー最適化の事実上の実装の1つです。ソフトマックス PG 法は、$mathcalS|$ および $frac11-gamma$ の観点から指数時間で収束できることを実証する。
論文参考訳（メタデータ） (2021-02-22T18:56:26Z)
RL for Latent MDPs: Regret Guarantees and a Lower Bound [74.41782017817808]
後期マルコフ決定過程(LMDP)における強化学習における後悔問題の検討 LMDPにおいて、M$可能なMDPのセットからMDPをランダムに描画するが、選択したMDPの同一性はエージェントに明らかにしない。鍵となるリンクは、MDPシステムの力学の分離の概念であることを示す。
論文参考訳（メタデータ） (2021-02-09T16:49:58Z)
Blackwell Online Learning for Markov Decision Processes [28.79413432611949]
本研究は,オンライン最適化の観点からのマルコフ決定過程(mdp)の新しい解釈を提供する。 MDPにより誘導されるブラックウェルゲームを構築し、後悔の最小化、ブラックウェルアプローチ可能性理論、MDPの学習理論のギャップを埋める。
論文参考訳（メタデータ） (2020-12-28T00:40:01Z)

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

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