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

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

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