論文の概要: Lower Bounds for Policy Iteration on Multi-action MDPs
- arxiv url: http://arxiv.org/abs/2009.07842v1
- Date: Wed, 16 Sep 2020 17:59:25 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-17 23:36:15.681124
- Title: Lower Bounds for Policy Iteration on Multi-action MDPs
- Title（参考訳）: マルチアクションmdpにおけるポリシーイテレーションの下限
- Authors: Kumar Ashutosh, Sarthak Consul, Bhishma Dedhia, Parthasarathi
Khirwadkar, Sahil Shah, Shivaram Kalyanakrishnan
- Abstract要約: ポリシーイテレーション(英: Policy Iteration、PI)は、任意のマルコフ決定問題(MDP)に対して最適なポリシーを計算するアルゴリズムの古典的なファミリーである。
重要な理論的疑問は、特定のPI変種が入力MDPにおける状態数$n$とアクション数$k$の関数として終了するのに要する回数である。
我々の主な成果は、PIの特定の変種が終了するために$Omega(kn/2)$のイテレーションを取ることができることである。
- 参考スコア（独自算出の注目度）: 11.401494294855663
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Policy Iteration (PI) is a classical family of algorithms to compute an
optimal policy for any given Markov Decision Problem (MDP). The basic idea in
PI is to begin with some initial policy and to repeatedly update the policy to
one from an improving set, until an optimal policy is reached. Different
variants of PI result from the (switching) rule used for improvement. An
important theoretical question is how many iterations a specified PI variant
will take to terminate as a function of the number of states $n$ and the number
of actions $k$ in the input MDP. While there has been considerable progress
towards upper-bounding this number, there are fewer results on lower bounds. In
particular, existing lower bounds primarily focus on the special case of $k =
2$ actions. We devise lower bounds for $k \geq 3$. Our main result is that a
particular variant of PI can take $\Omega(k^{n/2})$ iterations to terminate. We
also generalise existing constructions on $2$-action MDPs to scale lower bounds
by a factor of $k$ for some common deterministic variants of PI, and by
$\log(k)$ for corresponding randomised variants.
- Abstract（参考訳）: ポリシー反復 (pi) は、任意のマルコフ決定問題 (mdp) に対して最適なポリシーを計算する古典的なアルゴリズム群である。
PIの基本的な考え方は、いくつかの初期方針から始まり、最適な方針に到達するまで、改善セットから繰り返しポリシーを更新することである。
PIの異なる変種は、改善に使用される(スイッチング)規則から生じる。
重要な理論的疑問は、特定のPI変種が入力MDPにおける状態数$n$とアクション数$k$の関数として終了するのに要する回数である。
この数の上限は相当な進歩があったが、下限では結果が少ない。
特に、既存の下界は主に$k = 2$アクションの特別な場合に焦点を当てている。
我々は、k \geq 3$ で下限を考案する。
主な結果は、piの特定のバリエーションが$\omega(k^{n/2})$イテレーションで終了できるということです。
また、作用 MDP 上の既存の構成を一般化して下界をスケールし、PI のいくつかの共通決定論的変種に対して$k$、対応するランダム化された変種に対して$\log(k)$ で表す。
関連論文リスト
- Confident Natural Policy Gradient for Local Planning in $q_π$-realizable Constrained MDPs [44.69257217086967]
制約付きマルコフ決定プロセス(CMDP)フレームワークは、安全性や他の重要な目的を課すための重要な強化学習アプローチとして出現する。
本稿では,線形関数近似が$q_pi$-realizabilityで与えられる学習問題に対処する。
論文 参考訳（メタデータ） (2024-06-26T17:57:13Z) - Policy Mirror Descent with Lookahead [0.46040036610482665]
Policy Mirror Descent (PMD) はソフトポリシー 正規化された1段階の欲求政策改善を実装するアルゴリズム。
我々は,多段階の欲求政策改善を取り入れた新しいPMDアルゴリズムである$h$-PMDを提案する。
我々は, 次元自由な$gammah$-linearコンバージェンスレートを, 多段階グリーディポリシの計算により, $h$-PMDがより高速な次元自由な$gammah$-linearコンバージェンスレートを享受できることを示す。
論文 参考訳（メタデータ） (2024-03-21T06:10:51Z) - Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs [17.62509045102346]
本稿では,CMDP(Constrained Markov Decision Processs)における最適ポリシー識別問題について考察する。
私たちは、モデルフリーで、後悔の少ないアルゴリズムに興味を持ち、確率の高いほぼ最適なポリシーを特定しています。
オンラインCMDPのサブ線形後悔と制約違反を伴う既存のモデルフリーアルゴリズムでは、最適ポリシーに対する収束保証は提供されない。
論文 参考訳（メタデータ） (2023-09-27T04:33:09Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2022-10-20T21:32:01Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Efficient Policy Iteration for Robust Markov Decision Processes via
Regularization [49.05403412954533]
ロバストな意思決定プロセス(MDP)は、システムのダイナミクスが変化している、あるいは部分的にしか知られていない決定問題をモデル化するためのフレームワークを提供する。
最近の研究は、長方形長方形の$L_p$頑健なMDPと正規化されたMDPの等価性を確立し、標準MDPと同じレベルの効率を享受する規則化されたポリシー反復スキームを導出した。
本研究では、政策改善のステップに焦点をあて、欲求政策と最適なロバストなベルマン作用素のための具体的な形式を導出する。
論文 参考訳（メタデータ） (2022-05-28T04:05:20Z) - Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。
我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。
本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
論文 参考訳（メタデータ） (2022-04-11T15:08:09Z) - Horizon-Free Reinforcement Learning in Polynomial Time: the Power of
Stationary Policies [88.75843804630772]
我々は既存の境界に対して,$Oleft(mathrmpoly(S,A,log K)sqrtKright)を後悔するアルゴリズムを設計する。
この結果は、定常政策の近似力、安定性、および濃度特性を確立する新しい構造補題の列に依存している。
論文 参考訳（メタデータ） (2022-03-24T08:14:12Z) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。
そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文 参考訳（メタデータ） (2020-03-11T23:23:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。