論文の概要: From Optimization to Control: Quasi Policy Iteration
- arxiv url: http://arxiv.org/abs/2311.11166v1
- Date: Sat, 18 Nov 2023 21:00:14 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-23 17:48:18.604983
- Title: From Optimization to Control: Quasi Policy Iteration
- Title(参考訳): 最適化から制御へ:準政策反復
- Authors: Mohammad Amin Sharifi Kolarijani and Peyman Mohajerin Esfahani
- Abstract要約: マルコフ決定過程(MDP)の最近の制御アルゴリズムは、よく確立された最適化アルゴリズムと暗黙の類似性を用いて設計されている。
本稿では, この類似性を, 統一された解特徴量を持つ4つの問題クラスで明示する。
我々は既存の文献で指摘されている同等の最適化と制御アルゴリズムを同定するが、そのほとんどは散在している。
- 参考スコア(独自算出の注目度): 4.061135251278187
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent control algorithms for Markov decision processes (MDPs) have been
designed using an implicit analogy with well-established optimization
algorithms. In this paper, we make this analogy explicit across four problem
classes with a unified solution characterization. This novel framework, in
turn, allows for a systematic transformation of algorithms from one domain to
the other. In particular, we identify equivalent optimization and control
algorithms that have already been pointed out in the existing literature, but
mostly in a scattered way. With this unifying framework in mind, we then
exploit two linear structural constraints specific to MDPs for approximating
the Hessian in a second-order-type algorithm from optimization, namely,
Anderson mixing. This leads to a novel first-order control algorithm that
modifies the standard value iteration (VI) algorithm by incorporating two new
directions and adaptive step sizes. While the proposed algorithm, coined as
quasi-policy iteration, has the same computational complexity as VI, it
interestingly exhibits an empirical convergence behavior similar to policy
iteration with a very low sensitivity to the discount factor.
- Abstract(参考訳): マルコフ決定過程(MDP)の最近の制御アルゴリズムは、よく確立された最適化アルゴリズムと暗黙の類似性を用いて設計されている。
本稿では, この類似性を, 統一解法により4つの問題クラスで明示する。
この新しいフレームワークは、一方のドメインから他方へのアルゴリズムの体系的な変換を可能にする。
特に,既存の文献では指摘されているが,ほとんどが散在的であった同等の最適化と制御アルゴリズムを同定する。
この統一フレームワークを念頭に置いて、二階型アルゴリズムにおけるヘッシアンを近似するためにmdp特有の2つの線形構造制約、すなわちアンダーソン混合を利用する。
これは、2つの新しい方向と適応的なステップサイズを組み込むことで、標準値反復(VI)アルゴリズムを変更する新しい一階制御アルゴリズムをもたらす。
提案手法は準ポリシー反復と呼ばれるが,viと同じ計算複雑性を持つが,割引係数に対する感度が極めて低く,ポリシー反復と類似した経験的収束挙動を示すことが興味深い。
関連論文リスト
- Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳(メタデータ) (2023-07-17T20:11:56Z) - Stochastic Ratios Tracking Algorithm for Large Scale Machine Learning
Problems [0.7614628596146599]
古典的なSGDフレームワークにおける適応的なステップ長選択のための新しいアルゴリズムを提案する。
妥当な条件下では、アルゴリズムは十分に確立された理論的な要件に従ってステップ長を生成する。
このアルゴリズムは,手動チューニングから得られる最良ステップ長に匹敵するステップ長を生成することができることを示す。
論文 参考訳(メタデータ) (2023-05-17T06:22:11Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳(メタデータ) (2023-02-01T08:50:48Z) - Adaptive First- and Second-Order Algorithms for Large-Scale Machine
Learning [3.0204520109309843]
機械学習における連続最適化問題に対処する一階法と二階法を考察する。
一階述語の場合、半決定論的から二次正規化への遷移の枠組みを提案する。
本稿では,適応的なサンプリングと適応的なステップサイズを持つ新しい1次アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-11-29T18:10:00Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳(メタデータ) (2021-06-08T21:05:30Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳(メタデータ) (2021-06-08T15:54:44Z) - Adaptive and Universal Algorithms for Variational Inequalities with
Optimal Convergence [29.189409618561964]
我々は単調演算子を用いた変分不等式の新しい適応アルゴリズムを開発した。
我々のアルゴリズムは未知の問題パラメータに自動的に適応する。
我々のアルゴリズムは普遍的であり、同時に最適な収束率を達成することを示す。
論文 参考訳(メタデータ) (2020-10-15T14:44:26Z) - Optimal and Practical Algorithms for Smooth and Strongly Convex
Decentralized Optimization [21.555331273873175]
ネットワークのノードにまたがるスムーズな凸関数の和を分散化最小化する作業について検討する。
本稿では,この分散最適化問題に対する2つの新しいアルゴリズムを提案し,複雑性を保証する。
論文 参考訳(メタデータ) (2020-06-21T11:23:20Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳(メタデータ) (2020-06-11T17:43:19Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳(メタデータ) (2020-01-29T09:40:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。