確率制御問題のアルゴリズムと計算量に関する研究

随机控制问题的算法和计算复杂度研究

• 批准号: 08740157
• 负责人: 田中 輝雄
• 金额: $ 0.64万
• 依托单位: Hiroshima City University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1996
• 资助国家: 日本
• 起止时间: 1996 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-08740157/
• 关键词: 確率制御問題; マルコフ決定過程; ベルマン方程式; 計算量

確率制御問題のうち、確率空間、状態空間等が複数個の確率空間、状態空間等の直積で定義される確率過程に対するマルコフ決定過程を取り上げた。定常、離散時間、割引型、無限期間、一般の状態空間、政策をマルコフ政策に制限した場合についての問題に対する最適値関数の計算量についての研究を行った。マルコフ決定過程の一般理論より、ある仮定の下では、最適値関数はベルマン方程式を満たし、又、逐次近似法により構成されることはよく知られたことである。本研究では、推移確率、利得関数、割引率、精度の4項目の組をインスタンス、インスタンスのクラスを問題、現時刻の確率過程の状態、次の時刻の確率過程の状態、アクションの3項目の組を質問とする計算モデルを設定した。そして、逐次近似法と関連させ、精度を決めたときsupノルムでの評価で最適値関数との誤差がその精度以下となる区分的に定数となる関数が存在するとき、そのアルゴリズムは正しいと定義し、オラクルとそのアルゴリズムによって実行される演算数の和でアルゴリズムの計算量を定義した。そこで、いくつかの数学的仮定の下で1 推移確率と利得関数がリプシッツ条件を満たし、消失状態を持たない場合2 1の条件の他に、マルコフ決定過程でよく知られているmixing条件を満たす場合3 推移確率と利得関数がリプシッツ条件を満たし、2でのmixing条件を満たし、消失状態をもつ場合の3通りの場合について考察した。評価の対象となるのは、それぞれ、各場合の条件を満たす設定の下で、その問題に対する正しいすべてのアルゴリズムに対して質問の最小値のオーダー評価(上界と下界)の考察を行った。

The definition of the direct product of the probability control problem, the probability space, the state space, etc. Research on the calculation quantity of optimal relationship in steady state, discrete time, cut-off type, infinite period, general state space, policy, policy, restriction and situation The general theory of the decision process, the optimal value of the equation, and the successive approximation method This study sets the parameters for the group of four items, namely, the accuracy rate, the profit relation, the cutting rate, the accuracy rate, the status of the accuracy rate process at the present time, the status of the accuracy rate process at the next time, and the calculation of the group of three items. For example, successive approximation method, correlation, accuracy determination, optimal correlation number, error determination, differential determination, correlation number, existence, correction, definition, calculation, sum of calculation, etc. 1. The accuracy of the process and the gain of the process are determined by the condition of the process and the mixing condition. 2. The mixing condition of the process is determined by the condition of the process. 3. The accuracy of the process and the gain of the process are determined by the condition of the process. The evaluation of the minimum value of the problem is based on the condition that the problem is set.

项目成果

Teruo Tanaka: "A matrix representation of fields and filtrations and its application to stochastic control problems" Journal of Information & Optimization Sciences. (1997)

Teruo Tanaka：“场和过滤的矩阵表示及其在随机控制问题中的应用”信息杂志