割引のあるセミ・マルコフ決定過程における非最適政策の除去法を併用するアルゴリズムについて

概要

論文の詳細を見る
割引のある有限状態マルコフ決定過程の計算アルゴリズムとしては、逐次近似法、政策反復法、線形計画法がよく知られている。特に政策反復法は、有限回の反復で最適定常政策f*、最小費用v*を求めることができ、従来の数値実験においても線形計画法に比して相当優れている。しかしながら、その値・決定ルーチンでは、状態数Nの次元の連立一次方程式を解かねばならず、N=1000以上の名状態システムにたいしては実用的ではない。近年多状態システムにたいする実用的なアルゴリズムとして、非最適政策の除去法を併用した逐次近似法が多くの研究者によって開発されてきた。本論文では、マルコフ決定過程を含むより一般的なセミ・マルコフ決定過程を取り扱い、非最適政策の除去法を併用した修正政策反復法を統一的に論ずる。ここで、修正政策反復法とは、値・決定ルーチンを有限回の逐次近似でおきかえた政策反復法であり、特別な場合として政策反復法を含み、従来の逐次近似法をも含んでいる。まず、最小費用v*の上、下限を修正政策反復法によって生成される系列を用いて導く。この上、下限は従来知られている上、下限よりも精確であり、特別な場合には逐次近似法による上、下限と一致している。この上、下限を用いて非最適政策の除去法を導き、アルゴリズムとして非最適政策の除去法を併用する修正政策反復法を提案する。さらに、本アルゴリズムが有限回の繰り返しで唯一の最適政策あるいはεn最適政策を定めることを示す。この基本アルゴリズムの概略を示せば、n=1、2、‥‥にたいして、ステップ1:費用v^<n-1>にもとずいた政策改良ルーチンにより、改良された政策f^nおよび費用w^nを計算し、同時に非最適政策を除去する。f^nが唯一の残された政策となれば、f^nは最適政策f*である。ステップ2:w^nを初期値とし、m回の逐次近似によりf^nのもとでの費用の近似値v^nを計算する。ステップ3:w^n、v^nを用いてv*の上、下限を計算する。上、下限の差が与えられた値ε以下となればv*のε/2似値がえられ、f^nはε^n最適政策である。ここでε^nはε等を用いてえられた正数である。次いで、最適政策、最小費用を保存するセミ・マルコフ決定過程間の新しい同値関係を導入する。ヤコビ法、ガウス・ザイデル法、SOR法等を含む連立一次方程式の種々の反復解法が同値なセミ・マルコフ決定過程を誘導することを示す。したがって、基本アルゴリズムをこれら同値なセミ・マルコフ決定過程に適用することにより、非最適政策の除去法を併用する種々の変換された修正政策反復法がえられる。さらに、これら変換されたアルゴリズム間の諸関係について論ずる。最後に、ハワードの自動車取替問題にたいする数値例は、N=41という小規模な問題にもかかわらず、基本アルゴリズムが、政策反復法、線線型計画法、従来の非最適政策の除去法を併用したアルゴリズムより優れ、種々の変換アルゴリズムのなかで最も速いことを示している。
社団法人日本オペレーションズ・リサーチ学会の論文

著者

大野勝久
京都大学

割引のあるセミ・マルコフ決定過程における非最適政策の除去法を併用するアルゴリズムについて

スポンサーリンク

概要

著者

関連論文

スポンサーリンク