JP6532048B2 - 生成装置、選択装置、生成方法、選択方法、およびプログラム - Google Patents

Description

本発明は、生成装置、選択装置、生成方法、選択方法、およびプログラムに関する。

観測可能でない状態を含む不確実な環境における逐次的意思決定は、部分観測マルコフ決定過程（ＰＯＭＤＰ）としてモデル化し、最適化できることが知られている。そしてＰＯＭＤＰは、ロボット制御、対話システム、および認知症患者補助等に応用されている。このような応用例において、状態遷移確率および観測確率等のＰＯＭＤＰのパラメータは、予め定められたスカラー値を用いていた（例えば、特許文献１〜３参照）。
特許文献１ 特開２００５−０８４８３４号公報
特許文献２ 特開２００８−１８６３２６号公報
特許文献３ 特開２０１２−１２３５２９号公報

しかしながら、ＰＯＭＤＰのパラメータの値を予め正確に推定することは困難であった。また、当該パラメータの値が現実の値と乖離している場合、このようなパラメータを用いて最適意志決定戦略をＰＯＭＤＰに基づいて算出しても、最適な結果を得ることが困難であった。したがって、ＰＯＭＤＰのパラメータ値が厳密に推定できなくても、当該パラメータ値が予め定められた範囲内に存在する場合、一定の性能が保証された最適意志決定戦略が算出できることが望まれていた。

本発明の第１の態様においては、アクションに応じて現在の状態から次の状態へと遷移する遷移モデルについて、累積期待利得の算出に用いる利得ベクトルを生成する生成装置であって、対象時点の次の時点以降に得られる累積期待利得の成分を次の時点の状態毎に含む次の時点の利得ベクトルを取得する取得部と、次の時点の利得ベクトルを用いて得られる累積期待利得に応じて、対象時点から次の時点への遷移に用いられる遷移パラメータの値を、遷移パラメータの取り得る範囲の中から決定する第１決定部と、決定された遷移パラメータを用いて、次の時点の利得ベクトルから、対象時点の利得ベクトルを生成する第１生成部と、を備える生成装置、生成方法、およびプログラムを提供する。

本発明の第２の態様においては、アクションに応じて現在の状態から次の状態へと遷移する遷移モデルにおけるアクションを選択する選択装置であって、対象時点以降に得られる累積期待利得の成分を対象時点の状態毎に含む対象時点の利得ベクトルの集合を取得する集合取得部と、対象時点において各状態にある想定確率を取得する確率取得部と、利得ベクトルの集合および想定確率に基づいて、利得ベクトルの集合の中から利得ベクトルを選択する選択部と、選択された利得ベクトルに対応するアクションを、選択すべきアクションとして出力する出力部と、対象時点から次の時点への遷移に用いられる遷移パラメータの値を、遷移パラメータの取り得る範囲の中から決定する第２決定部と、決定された遷移パラメータを用いて、対象時点の次の時点において各状態にある想定確率を生成する第２生成部と、を備える選択装置、選択方法、およびプログラムを提供する。

なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではない。また、これらの特徴群のサブコンビネーションもまた、発明となりうる。

本実施形態に係る生成装置１００の構成例を示す。 本実施形態に係る生成装置１００の動作フローを示す。 図２における動作フローの具体的アルゴリズムの第１の例を示す。 図２における動作フローの具体的アルゴリズムの第２の例を示す。 本実施形態に係る利得ベクトルの集合Λ_ｎと累積期待利得の関係を示す。 本実施形態に係る累積期待利得の最大値を返す利得関数を示す。 本実施形態に係る利得ベクトルの集合Λ_ｎと累積期待利得の関係の変形例を示す。 図７の変形例に対応する累積期待利得の最大値を返す利得関数を示す。 図２における動作フローの具体的アルゴリズムの第３の例を示す。 本実施形態に係る選択装置２００の構成例を示す。 本実施形態に係る選択装置２００の動作フローを示す。 コンピュータ１９００のハードウェア構成の一例を示す。

以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではない。また、実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。

図１は、本実施形態に係る生成装置１００の構成例を示す。生成装置１００は、アクションに応じて現在の状態から次の状態へと遷移する遷移モデルについて、累積期待利得の算出に用いる利得ベクトルを生成する。

ここで、遷移モデルは、例えば「ロボットが移動する」、「音声を認識して、認識した音声に対応する返事および情報を発する」、ならびに「消費者が商品の情報を得つつ、消費活動をする」等の動作を、それぞれの動作に含まれる個別のアクションと、当該アクションによって遷移する複数の状態をモデル化した遷移モデルである。なお、複数の状態のうち、１以上の状態は観測不能な隠れ状態であってよく、この場合、部分観測マルコフ決定過程（ＰＯＭＤＰ）としてモデル化することができる。

生成装置１００は、厳密に遷移パラメータ（一例として、状態遷移確率関数）が決定されていなくても、累積期待利得に応じて意志決定戦略（アクションの実行による状態間の遷移）を算出すべく、利得ベクトルを生成する。生成装置１００は、対象時点よりも時間的に次の時点以降の利得ベクトルに基づき、対象時点の利得ベクトルを生成する。生成装置１００は、一例として、コンピュータ上でソフトウェアを実行することにより実現される。生成装置１００は、取得部１１０と、初期化部１２０と、第１決定部１３０と、第１生成部１４０と、除去部１５０と、を備える。

取得部１１０は、対象時点の次の時点以降に得られる累積期待利得の成分を次の時点の状態毎に含む次の時点の利得ベクトルを取得する。取得部１１０は、次の時点の利得ベクトルを少なくとも１つ含む次の時点における利得ベクトルの集合を取得してよい。取得部１１０は、例えば、外部のデータベース１０００等の記憶装置に接続され、次の時点の利得ベクトルを取得する。また、取得部１１０は、当該生成装置１００の内部の記憶装置等に接続され、次の時点の利得ベクトルを取得してもよい。

初期化部１２０は、将来の時点における利得ベクトルを初期化する。初期化部１２０は、取得部１１０に接続され、遷移モデルが対象とする期間全体において利得ベクトルを算出するのに先立って、予め定められた将来の時点（例えば、期間の最後の時点）における利得ベクトルの集合を初期化する。例えば、初期化部１２０は、将来のある時点における利得ベクトルをゼロベクトルの集合とすることにより初期化する。初期化部１２０は、初期化された利得ベクトルの集合を第１決定部１３０に供給する。

第１決定部１３０は、次の時点の利得ベクトルを用いて得られる累積期待利得に応じて、対象時点から次の時点への遷移に用いられる遷移パラメータの値を、遷移パラメータの取り得る範囲の中から決定する。第１決定部１３０は、取得部１１０に接続され、次の時点の利得ベクトルおよび初期化された利得ベクトルを受け取る。ここで、遷移パラメータの取り得る範囲は、ユーザ等から予め指定された範囲でよく、これに代えて、予め他のアルゴリズム等で算出された範囲でもよい。ユーザは、ネットワーク等を介して、当該範囲の情報をデータベース１０００等の記憶装置に記憶してよく、この場合、第１決定部１３０は、取得部１１０を介して当該範囲の情報を取得する。

第１決定部１３０は、取得部１１０が利得ベクトルの集合を取得する場合、次の時点における利得ベクトルの集合に含まれる利得ベクトルのそれぞれについて遷移パラメータの値を決定する。第１決定部１３０による遷移パラメータ等の詳細な決定方法については追って説明する。第１決定部１３０は、決定した遷移パラメータを、第１生成部１４０に供給する。

第１生成部１４０は、第１決定部１３０に接続され、決定された遷移パラメータを用いて、次の時点の利得ベクトルから、対象時点の利得ベクトルを生成する。第１生成部１４０は、取得部１１０が利得ベクトルの集合を取得する場合、次の時点における利得ベクトルの集合に含まれる利得ベクトルのそれぞれについて、決定された遷移パラメータを用いて対象時点の利得ベクトルを生成して対象時点の利得ベクトルの集合に加える。第１生成部１４０は、生成した利得ベクトルを除去部１５０に供給する。

除去部１５０は、第１生成部１４０に接続され、第１生成部１４０が生成した対象時点の利得ベクトルの集合から、各状態の確率分布の範囲内で最大値を構成しない利得ベクトルを除去する。除去部１５０は、生成した対象時点の利得ベクトルの集合を枝刈りする。ここで、第１生成部１４０が生成する利得ベクトルの集合が、予め定められた数以下の場合等、枝刈りが不要と判断した場合、除去部１５０は、除去動作をしなくてもよい。また、枝刈りが不要と予め判断できる場合、除去部１５０はなくてもよい。除去部１５０は、データベース１０００に接続され、利得ベクトルをデータベース１０００に供給して記憶する。

以上の本実施形態に係る生成装置１００は、次の時点の利得ベクトルに基づき、対象時点の利得ベクトルを生成する。そして、生成装置１００は、生成した対象時点の利得ベクトルを次の時点の利得ベクトルとし、時刻を１つ遡った時点を対象時点として、当該対象時点の利得ベクトルを次に生成する。このように、生成装置１００は、将来の時点から遡って対象時点における利得ベクトルを生成する。これにより、生成装置１００は、遷移モデルが対象とする期間全体における利得ベクトルを、順次生成することができる。生成装置１００による利得ベクトルの生成動作を、図２を用いて説明する。

図２は、本実施形態に係る生成装置１００の動作フローを示す。本実施形態において、生成装置１００は、Ｓ３１０〜Ｓ３６０の処理を実行することにより、アクションに応じて現在の状態から次の状態へと遷移する遷移モデルの、累積期待利得の算出に用いる利得ベクトルの集合を生成する。

まず、取得部１１０は、外部または生成装置１００内部のデータベース１０００から次の時点の利得ベクトルの集合を取得する（Ｓ３１０）。ここで、時点ｎ（ｎは０以上の整数）における利得ベクトルα_ｎの集合をΛ_ｎとする。

取得部１１０は、対象時点をｎとすると、次の時点ｎ＋１の利得ベクトルα_ｎ＋１の集合Λ_ｎ＋１を取得する。ここで、利得ベクトルα_ｎは、各状態に対応する複数の要素を有する。それぞれの要素は、時点ｎにおいて当該状態にあり、α_ｎに対応付けられたアクションを実行した場合に可能な累積期待利得を示す。

また、取得部１１０は、遷移パラメータの取り得る範囲の情報を取得する。ここで、状態ｓ（ｓ∈Ｓ、Ｓは状態の集合）においてアクションａ（ａ∈Ａ、Ａはアクションの集合）を実行した場合に、状態ｓから状態ｔに遷移し、観測値ｚ（ｚ∈Ｚ、Ｚは観測の集合）が観測される確率を、遷移パラメータである状態遷移確率Ｐ（ｔ，ｚ｜ｓ，ａ）とする。即ち、取得部１１０は、各ｓ∈Ｓとａ∈Ａの組について、状態遷移確率関数Ｐ（・，・｜ｓ，ａ）の取り得る範囲Ｐ_ｓ ^ａを取得する。

次に、初期化部１２０は、遷移モデルにおける将来の時点Ｎにおける利得ベクトルα_Ｎの集合Λ_Ｎを初期化する（Ｓ３２０）。例えば、初期化部１２０は、利得ベクトルα_Ｎの集合Λ_Ｎを長さが状態の数（|Ｓ|）と同じ数のゼロベクトルだけからなる集合｛（０，...，０）｝として集合Λ_Ｎを初期化する。

次に、第１決定部１３０は、次の時点ｎ＋１の利得ベクトルα_ｎ＋１の集合Λ_ｎ＋１を用いて得られる累積期待利得に応じて、対象時点ｎから次の時点ｎ＋１への遷移に用いられる遷移パラメータの値を決定する（Ｓ３３０）。第１決定部１３０は、遷移パラメータとして、各ｓ∈Ｓとａ∈Ａの組についての状態遷移確率関数Ｐ（・，・｜ｓ，ａ）を、状態遷移確率の取り得る範囲Ｐ_ｓ ^ａの中から決定する。

ここで、累積期待利得は、アクションを実行して状態が遷移した場合に応じて累積される即時期待利得である。即時期待利得は、状態遷移確率Ｐ（ｔ，ｚ｜ｓ，ａ）と状態ｓでアクションａを実行した場合に得られる即時利得との積に応じて算出されてよい。第１決定部１３０は、利得ベクトルの集合Λ_ｎ＋１に含まれる利得ベクトルα_ｎ＋１のそれぞれについて遷移パラメータの値を決定する。

例えば、第１決定部１３０は、次のｎ＋１の利得ベクトルα_ｎ＋１の集合Λ_ｎ＋１を用いて得られる累積期待利得が、最小となる遷移パラメータの値を決定する。また、第１決定部１３０は、次の時点ｎ＋１の利得ベクトルα_ｎ＋１の集合Λ_ｎ＋１を用いて得られる累積期待利得が、近似的に最小となる遷移パラメータの値を決定してもよい。これに代えて、第１決定部１３０は、当該累積期待利得が、遷移パラメータの取り得る範囲Ｐ_ｓ ^ａのうち予め定められた基準以下、最高値、平均値、または予め定められたパーセンタイル値等となる遷移パラメータの値を決定してもよい。

次に、第１生成部１４０は、決定された遷移パラメータを用いて、対象時点ｎの利得ベクトルα_ｎの集合Λ_ｎを生成する（Ｓ３４０）。第１生成部１４０は、対象時点ｎにおいて行う複数のアクションａのそれぞれに対応して、各状態ｓにおける当該アクションａに応じて第１決定部１３０により決定された遷移パラメータに基づく累積期待利得と、各状態ｓに基づく即時期待利得とに基づいて、対象時点ｎの利得ベクトルα_ｎを生成する。例えば、第１生成部１４０は、複数のアクションａ毎に利得ベクトルα_ｎを生成して集合Λ_ｎに加える。

第１生成部１４０は、時点ｎにおける利得ベクトルα_ｎの集合Λ_ｎを、次の時点ｎ＋１における利得ベクトルα_ｎ＋１の集合Λ_ｎ＋１に基づいて生成する。

次に、除去部１５０は、対象時点の利得ベクトルα_ｎの集合Λ_ｎから、如何なる確率ベクトルπについても当該πとの内積を最大としない利得ベクトルを除去する（Ｓ３５０）。そして、除去部１５０は、利得ベクトルα_ｎの集合Λ_ｎを、データベース１０００に記憶する。除去部１５０の具体的な除去方法は後述する。

次に、生成装置１００は、利得ベクトルα_ｎの集合Λ_ｎの生成を継続するか否かを判断する（Ｓ３６０）。例えば、生成装置１００は、ｎ＝０となるか否かを判断し、ｎ＝０となる場合、処理を終了する（Ｓ３６０：Ｙｅｓ）。また、生成装置１００は、ｎ＝０とならない場合（Ｓ３６０：Ｎｏ）、ｎから１を差し引いて、生成した利得ベクトルα_ｎの集合Λ_ｎを次の時点の利得ベクトルの集合とした（Ｓ３７０）後に、処理をＳ３２０に戻す。これにより、生成装置１００は、ｎがＮから０になるまで利得ベクトルα_ｎの集合Λ_ｎを生成する。

図３は、図２における動作フローの具体的アルゴリズムの第１の例を示す。ここでは、図３を例に生成装置１００の処理のアルゴリズムの概要を説明する。

まず、１行目に示すように、初期化部１２０は、将来の時点Ｎの利得ベクトルα_Ｎの集合Λ_Ｎをゼロベクトルだけからなる集合｛（０，...，０）｝として初期化する。

次に、２行目に示すように、生成装置１００は、２〜４行目で定義する第１ループ処理を実行する。３行目に示すように、生成装置１００は、第１ループ処理内でＲｏｂｕｓｔＤＰｂａｃｋｕｐ関数により利得ベクトルα_ｎの集合Λ_ｎを生成する。即ち、生成装置１００は、第１ループ処理において、対象時点ｎをＮ−１から始めて３行目の処理を実行して利得ベクトルα_ｎの集合Λ_ｎを生成し、当該対象時点ｎが０になるまでＮ回繰り返す。

そして、生成装置１００は、対象時点ｎを０からＮ−１にして順次生成した利得ベクトルα_ｎの集合Λ_ｎを出力する。このように、生成装置１００は、対象時点ｎを将来の時点Ｎ−１から時系列に順次遡って、当該対象時点ｎに対応する利得ベクトルα_ｎの集合Λ_ｎを順次生成する。利得ベクトルα_ｎの集合Λ_ｎを生成するＲｏｂｕｓｔＤＰｂａｃｋｕｐ関数について、図４を用いて説明する。

図４は、図２における動作フローの具体的アルゴリズムの第２の例を示す。ここでは、図４を例に生成装置１００の利得ベクトルα_ｎの集合Λ_ｎを生成する処理のアルゴリズムを説明する。即ち、図４に示すアルゴリズムは、ＲｏｂｕｓｔＤＰｂａｃｋｕｐ関数の例を示す。

まず、１行目に示すように、第１決定部１３０は、時点ｎ＋１における利得ベクトルの集合Λ_ｎ＋１を取得する。

次に、２行目に示すように、第１決定部１３０は、時点ｎの全てのアクションａに対する利得ベクトルの集合Λ^＊ _ｎを空集合として初期化する。

次に、３行目に示すように、第１決定部１３０は、アクションａのそれぞれに対して、３〜１３行目で定義する第１ループ処理を実行する。

４行目に示すように、第１決定部１３０は、第１ループ処理内で、アクションａに対応づけられた利得ベクトルα^ａ _ｎの集合Λ^ａ _ｎを空集合として初期化する。

次に、５行目に示すように、第１決定部１３０は、第１ループ処理内で、利得ベクトルの集合Λ_ｎ＋１に含まれるｚ個の利得ベクトルα_ｚ（ｚ∈Ｚ、Ｚは観測の集合）のうち、重複を許した全ての組み合わせに対して、５〜１０行目で定義する第２ループ処理を実行する。

次に、６行目に示すように、第１決定部１３０は、第２ループ処理内で、状態ｓ（ｓ∈Ｓ）のそれぞれに対して、６〜８行目で定義する第３ループ処理を実行する。

７行目に示すように、第１決定部１３０は、第３ループ処理内で、各ｓ∈Ｓとａ∈Ａの組における状態遷移確率関数の取り得る範囲Ｐ_ｓ ^ａ（：＝Ｐ（・，・｜ｓ，ａ））の中から、予め定められた式が最小となる状態遷移確率関数Ｐ（・，・｜ｓ，ａ）を、遷移パラメータＰ^＊（・，・｜ｓ，ａ）と決定する。ここで、予め定められた式は、一例として、状態遷移確率Ｐ（ｔ，ｚ｜ｓ，ａ）と利得ベクトルの要素α_ｚ（ｔ）との積について、時点ｎ＋１の状態ｔおよび観測値ｚについて総和を取った累積期待利得を示す。即ち、第１決定部１３０は、第３ループ処理を実行することで、各ｓ∈Ｓとａ∈Ａの組における状態遷移確率関数の取り得る範囲Ｐ_ｓ ^ａの中から、最も累積期待利得が低くなる状態遷移確率関数Ｐ（・，・｜ｓ，ａ）を、遷移パラメータＰ^＊（・，・｜ｓ，ａ）と決定する。

次に、９行目に示すように、第１生成部１４０は、第２ループ処理内で第３ループ処理の後に、決定した遷移パラメータＰ^＊（・，・｜ｓ，ａ）を用いて、アクションａに対応する利得ベクトルα^ａ _ｎを生成して集合Λ^ａ _ｎに加える。第１生成部１４０は、一例として、第１決定部１３０により決定された遷移パラメータＰ^＊（・，・｜ｓ，ａ）によって状態遷移をする場合の累積期待利得と、状態ｓにおける即時期待利得との和を成分とする、対象時点ｎの利得ベクトルα^ａ _ｎを生成する。

ここで、９行目の括弧（）内の第１項は、状態ｓにおいてアクションａを実行した場合に得られる即時期待利得を示す。また、第２項は、状態ｓでアクションａを実行して、状態ｔに遷移して観測量ｚが観測されたという条件における累積期待利得を示す。そして、第１生成部１４０は、生成した対象時点ｎの利得ベクトルα^ａ _ｎと集合Λ^ａ _ｎの和集合を、集合Λ^ａ _ｎとして更新する。以上の第２ループ処理は、ｚ個の利得ベクトルα_ｚの組み合わせ毎に、最も累積期待利得が低くなる状態遷移確率関数Ｐ（・，・｜ｓ，ａ）を決定して（即ち、最悪の場合の確率値を決定して）、対象時点ｎの利得ベクトルα^ａ _ｎを生成する。

次に、１１行目に示すように、除去部１５０は、第１ループ処理内で第２ループ処理の後に、Ｐｒｕｎｅ関数に集合Λ^ａ _ｎを入力することにより集合Λ^ａ _ｎを枝刈りしてよい。ここで、Ｐｒｕｎｅ関数は、入力されたベクトル集合に含まれるベクトルのうち、少なくとも一つの確率ベクトルｂについて、ｂとの内積が最大値を構成するベクトル以外のベクトルを入力集合から除去する。

また、１２行目に示すように、除去部１５０は、第１ループ処理内で、Ｐｒｕｎｅ関数に集合Λ_ｎと集合Λ^ａ _ｎの和集合を入力することにより集合Λ^＊ _ｎを更新する。Ｐｒｕｎｅ関数について、図５および図６を用いて説明する。

図５は、本実施形態に係る利得ベクトルの集合Λ_ｎと累積期待利得の関係を示す。ここで利得ベクトルα_１、α_２、α_３、およびα_４を含む利得ベクトルの集合Λ_ｎを想定する。各利得ベクトルは、各状態ｓの確率分布ｂに応じた累積期待利得の値を算出するのに用いることができる。図５は、説明の目的で便宜的に、各利得ベクトルが、確率分布ｂではなく単一の状態ｉである確率値ｂ（ｉ）のみに応じて、累積期待利得の値を返すものとして説明する。ここで、確率値ｂ（ｉ）は、０以上１以下の値である。

例えば、状態ｉである確率値ｂ（ｉ）がｂ_１である場合、利得ベクトルα_１はｂ_１の値に応じた累積期待利得ｒ_１を返し、利得ベクトルα_２はｂ_１の値に応じた累積期待利得ｒ_２を返し、利得ベクトルα_３はｂ_１の値に応じた累積期待利得ｒ_３を返し、利得ベクトルα_４はｂ_１の値に応じた累積期待利得ｒ_４を返す。

図５に示すように、累積期待利得ｒ_１〜ｒ_４のうち最大値を取るのは累積期待利得ｒ_１なので、利得ベクトルα_１〜α_４の集合から確率値ｂ_１に応じて累積期待利得ｒ_１に対応する利得ベクトルα_１を選択することができる。同様に、確率値ｂ_２に応じて累積期待利得の最大値を取る利得ベクトルα_２を選択し、確率値ｂ_３に応じて累積期待利得の最大値を取る利得ベクトルα_３を選択することができる。

ここで、最適な戦略に従って意思決定を実行する場合、後述するが、累積期待利得が最大となる利得ベクトルを選択する。即ち、利得ベクトルα_１〜α_４の集合のうち、どの確率値ｂ（ｉ）においても最大値を構成しない利得ベクトルα_４は、選択されない不要な利得ベクトルであることが判明する。そこで、除去部１５０は、このような不要な利得ベクトルを削除する。即ち、除去部１５０は、確率値ｂ（ｉ）が取り得る範囲内の複数の値をそれぞれ用いて累積期待利得を算出し、最大値を構成しない利得ベクトルを特定して削除する。これにより、除去部１５０は、無意味な利得ベクトルを枝刈りし、計算をより効率化することができる。

図６は、最大値を取る利得ベクトルの部分を連結することにより得られる、本実施形態に係る累積期待利得の最大値を返す利得関数を示す。図６に示すように、複数の利得ベクトルα_１〜α_４のうち累積期待利得が最大値となる区間のみを連結すると、太線で示すように、下に凸方向が向く区分線形凸関数となる利得関数ｖ_ｎ（ｂ）が得られる。利得関数ｖ_ｎ（ｂ）は、ｖ_ｎ（ｂ）＝ｍａｘ［Σ_ｉｂ（ｉ）α（ｉ）］で表される確率分布ｂに依存する関数となる。

図７は、本実施形態に係る利得ベクトルの集合Λ_ｎと累積期待利得の関係の変形例を示す。図７は、図５と同様に、第１生成部１４０が利得ベクトルα_１、α_２、α_３、およびα_４を含む利得ベクトルの集合Λ_ｎを生成する例を説明する。

本変形例において、除去部１５０は、選択用の確率分布ｂ１'およびｂ２'を設定する。なお、図７では説明のため便宜的に、選択用の確率分布ｂ１'およびｂ２'はベクトルではなく、単一の状態ｉに対応した確率値ｂ（ｉ）であるものとして説明する。

例えば、除去部１５０は、選択用の確率分布ｂ１'について、利得ベクトルα_１〜α_４のうち累積期待利得の最大値を与える利得ベクトルα_１を利得ベクトルの集合Λ_ｎに残す。また、除去部１５０は、選択用の確率分布ｂ２'について、利得ベクトルα_１〜α_４のうち累積期待利得の最大値を与える利得ベクトルα_３を利得ベクトルの集合Λ_ｎに残す。このように、除去部１５０は、第１生成部１４０が生成した対象時点の利得ベクトルα_ｎの集合Λ_ｎから、各状態の確率分布の範囲内における予め定められた選択用の確率分布において累積期待利得の最大値を与えない利得ベクトルを除去する。

ここで、予め定められた選択用の確率分布は、ユーザが予め入力してデータベース１０００等の記憶装置に記憶してよい。以上のように、除去部１５０は、選択用の確率分布を用いることで、不要な利得ベクトルを除去することができ、効率的に枝刈りを実行することができる。

図８は、図７の変形例に対応する累積期待利得の最大値を返す利得関数を示す。図８は、図６と同様に、最大値を取る利得ベクトルの部分を連結することにより得られる利得関数を示す。図８に示すように、利得ベクトルの集合Λ_ｎに含まれる利得ベクトルα_１およびα_３のうち累積期待利得が最大値となる区間のみを連結すると、太線で示す下に凸方向が向く区分線形凸関数となる利得関数ｖ_ｎ（ｂ）が得られる。αを利得ベクトルの集合Λ_ｎに含まれる利得ベクトルとした場合、利得関数ｖ_ｎ（ｂ）は、ｖ_ｎ（ｂ）＝ｍａｘ［Σ_ｉｂ（ｉ）α（ｉ）］で表される確率分布ｂに依存する関数となる。

以上のように、本実施形態における生成装置１００は、集合Λ^＊ _ｎを更新し、全てのアクションａに対して第１ループ処理を繰り返す。これにより、生成装置１００は、利得ベクトルα_ｎの集合Λ_ｎを生成することができ、１４行目に示すように、生成した集合Λ^＊ _ｎを返し、当該アルゴリズムを終了させる。

以上の図４に示すアルゴリズムは、利得ベクトルの集合Λ_ｎ＋１に含まれるｚ個の利得ベクトルα_ｚのうち、重複を許した全ての組み合わせに対して、最悪となる場合の状態遷移確率関数を決定して、利得ベクトルα_ｎの集合Λ_ｎを生成する例を説明した。これに代えて、生成装置１００は、各ｓ∈Ｓとａ∈Ａの組における状態遷移確率の取り得る範囲Ｐ_ｓ ^ａ（：＝Ｐ（・，・｜ｓ，ａ））を凸集合とした凸最適化問題を解くことで、利得ベクトルα_ｎの集合Λ_ｎを生成してもよい。凸最適化問題を解いて利得ベクトルα_ｎの集合Λ_ｎを生成する関数について、図９を用いて説明する。

図９は、図２における動作フローの具体的アルゴリズムの第３の例を示す。即ち、図９に示すアルゴリズムは、ＲｏｂｕｓｔＤＰｂａｃｋｕｐ関数に代えて用いられるＰｏｉｎｔ−ｂａｓｅｄ ＲｏｂｕｓｔＤＰｂａｃｋｕｐ関数の例を示す。

まず、１行目に示すように、第１決定部１３０は、時点ｎ＋１における利得ベクトルの集合Λ_ｎ＋１および想定確率ベクトルπの集合Πを取得する。ここで、想定確率ベクトルπは、想定確率π（ｓ）を要素として含むベクトルであり、想定確率π（ｓ）は、図５から図８で説明した選択用の確率分布である。また、想定確率π（ｓ）は、状態がｓであるとユーザが想定する（信じる）確率であってよい。想定確率ベクトルπの集合Πは、ユーザ等によって予めデータベース等に記憶されてよく、第１決定部１３０は、取得部１１０を介して当該想定確率ベクトルπの集合Πを取得してよい。

次に、２行目に示すように、第１決定部１３０は、利得ベクトルの集合Λ_ｎを空集合として初期化する。

次に、３行目に示すように、第１決定部１３０は、想定確率ベクトルπ（π∈Π）のそれぞれに対して、３〜１９行目で定義する第１ループ処理を実行する。

４行目に示すように、第１決定部１３０は、第１ループ処理内で、想定確率ベクトルπに対応づけられた利得ベクトルα_ｎの集合Λ_ｎ，πを空集合として初期化する。

次に、５行目に示すように、第１決定部１３０は、第１ループ処理内で、アクションａ（ａ∈Ａ）のそれぞれに対して、５〜１７行目で定義する第２ループ処理を実行する。

６行目に示すように、第１決定部１３０は、（数１）式で示す目的関数Ｕ（ｚ）の総和を最小化させる凸最適化問題を解く。なお、６行目の（１）は、（数１）式を示す。

第１決定部１３０は、各ｓおよびａについて、状態遷移確率関数Ｐ（・，・｜ｓ，ａ）の想定範囲を凸集合Ｐ_ｓ ^ａとした凸最適化問題にすることで、既知の手法で当該凸最適化問題を効率的に解くことができる。

次に、７行目に示すように、第１決定部１３０は、第２ループ処理内で、観測値ｚ（ｚ∈Ｚ）のそれぞれに対して、７〜９行目で定義する第３ループ処理を実行する。

８行目に示すように、第１決定部１３０は、（数１）式を解いて得られる利得ベクトルα_ｚのうち、目的関数Ｕ（ｚ）を最大にする利得ベクトルをα^＊ _ｚとする。即ち、利得ベクトルα^＊ _ｚは、（数１）式の不等式（≧）を等号（＝）とする利得ベクトルである。第１決定部１３０は、（数１）式を解く過程において、このような利得ベクトルを記憶しておくことが望ましい。

次に、１０行目に示すように、第１決定部１３０は、第２ループ処理内で第３ループ処理の後に、状態ｓ（ｓ∈Ｓ）のそれぞれに対して、１０〜１２行目で定義する第４ループ処理を実行する。

１１行目に示すように、第１決定部１３０は、（数１）式を解いて得られる状態遷移確率関数Ｐ（・，・｜ｓ，ａ）のうち、目的関数Ｕ（ｚ）を最大にする状態遷移確率関数をＰ^＊（・，・｜ｓ，ａ）とする。即ち、状態遷移確率関数Ｐ^＊（・，・｜ｓ，ａ）は、（数１）式の最適解である。即ち、第１決定部１３０は、対象時点ｎから次の時点ｎ＋１への遷移に用いられる遷移パラメータを、当該状態遷移確率関数Ｐ^＊（・，・｜ｓ，ａ）とする。第１決定部１３０は、（数１）式を解く過程において、このような状態遷移確率関数を記憶しておくことが望ましい。

次に、１３行目に示すように、第１生成部１４０は、第２ループ処理内で第４ループ処理の後に、状態ｓ（ｓ∈Ｓ）のそれぞれに対して、１３〜１５行目で定義する第５ループ処理を実行する。

１４行目に示すように、第１生成部１４０は、遷移パラメータＰ^＊（・，・｜ｓ，ａ）を用いて、利得ベクトルα^＊ _ｎを生成する。第１生成部１４０は、一例として、遷移パラメータＰ^＊（・，・｜ｓ，ａ）によって算出される累積期待利得と、状態ｓに基づく即時期待利得との和を成分とする、対象時点ｎの利得ベクトルα^＊ _ｎを生成する。

１４行目の第１項は、状態ｓにおいてアクションａを実行した場合に得られる即時期待利得を示す。また、第２項は、状態ｓでアクションａを実行して、状態ｔに遷移して観測量ｚが観測されたという条件において、可能な累積期待利得を示す。ここで、第２項の累積期待利得には、係数γを乗じた例を示す。係数γは、０から１の間の値を有する割引率（０＜γ≦１）であり、将来得られる利得をどれだけ軽視するかを示す係数である。

割引率γは、例えば、１時点先をγだけ割り引くと、２時点先はγの２乗だけ割り引かれ、ｎ時点先はγのｎ乗だけ割り引かれるように設定される。このような割引率γは、図９に示すアルゴリズムに適用することだけには限定されず、図４に示すアルゴリズム（例えば、９行目の第２項等）に適用してもよい。

次に、１６行目に示すように、第１生成部１４０は、第２ループ処理内で第５ループ処理の後に、生成した対象時点ｎの利得ベクトルα^＊ _ｎと集合Λ_ｎ，πの和集合を、集合Λ_ｎ，πとして更新する。このように、第２ループ処理は、それぞれのπ毎に順次実行され、全てのアクションａについて凸計画問題を解き、集合Λ_ｎ，πとして更新するので、１つのπに対して複数の利得ベクトルα^＊ _ｎが更新される場合がある。

次に、１８行目に示すように、第１生成部１４０は、第２ループ処理の後に、１つのπに対して１つの利得ベクトルα_ｎを選択して、利得ベクトルα_ｎの集合Λ_ｎを更新する。即ち、第２ループ処理で生成された利得ベクトルα^＊ _ｎ（α^＊ _ｎ∈Λ_ｎ，π）のうち、状態ｓ（ｓ∈Ｓ）についてπ（ｓ）とα（ｓ）の積の和が最大となる利得ベクトルα_ｎを選択して、集合Λ_ｎに加える。

このように、第１ループ処理は、１つのπ毎に１つの利得ベクトルα_ｎを選択して集合Λ_ｎに加え、πの数だけ繰り返し実行する。これによって、生成装置１００は、集合Λ_ｎに含まれる利得ベクトルα_ｎの数をπの数以下に抑えることができる。以上のように、図９に示すアルゴリズムは、第１ループ処理を繰り返して集合Λ_ｎを更新し、利得ベクトルα_ｎの集合Λ_ｎを生成する。そして、２０行目に示すように、生成した集合Λ_ｎを返し、当該アルゴリズムを終了させる。

以上の図９に示すアルゴリズムは、状態遷移確率関数Ｐ（・，・｜ｓ，ａ）の想定範囲Ｐ_ｓ ^ａを（数１）式に示す凸集合で表すことにより、状態遷移確率Ｐ（ｔ，ｚ｜ｓ，ａ）を決定し、対象時点ｎの利得ベクトルα_ｎを生成することを説明した。この場合において、状態遷移確率Ｐ（ｔ，ｚ｜ｓ，ａ）の基準値を予め定められた値Ｐ^０（ｔ，ｚ｜ｓ，ａ）とし、状態遷移確率Ｐ（ｔ，ｚ｜ｓ，ａ）の想定範囲を基準値の１／κ倍（０＜κ＜１）までとすることにより、（数１）式の凸計画問題を、次式で示す線形計画問題とすることができる。

なお、（数２）式において、状態遷移確率Ｐ（ｔ，ｚ｜ｓ，ａ）の想定範囲を基準値の１／κ倍としたが、これに代えて、基準値の中心値または分散値等を用いてもよい。このように、第１決定部１３０は、状態遷移確率Ｐ（ｔ，ｚ｜ｓ，ａ）の取り得る範囲として、状態遷移確率の基準値Ｐ^０（ｔ，ｚ｜ｓ，ａ）の定数倍までの範囲の中から当該状態遷移確率を決定してよい。この場合、第１決定部１３０は、図９に示すアルゴリズムの６行目において、（数１）式に代えて、（数２）式を解いてよい。

以上のように、本実施形態の生成装置１００は、遷移パラメータの取り得る範囲の中から、次の時点の利得ベクトルを用いて得られる累積期待利得が最小となるように、最悪の場合における遷移パラメータの値を決定して、対象時点の利得ベクトルを生成することができる。このようにして生成した利得ベクトルを用いることで、一定の性能が保証された最適意思決定戦略を算出することができる。最適意思決定戦略として実行すべき適切なアクションを選択する選択装置について、図１０を用いて説明する。

図１０は、本実施形態に係る選択装置２００の構成例を示す。選択装置２００は、アクションａに応じて現在の状態から次の状態へと遷移する遷移モデルにおいて、利得ベクトルの集合に基づいてアクションａを選択する。選択装置２００は、集合取得部２１０と、確率取得部２２０と、選択部２３０と、出力部２４０と、第２決定部２５０と、第２生成部２６０と、を備える。

集合取得部２１０は、対象時点ｎ以降に得られる累積期待利得の成分を対象時点ｎの状態毎に含む対象時点ｎの利得ベクトルα_ｎの集合Λ_ｎを取得する。集合取得部２１０は、例えば、外部のデータベース１０００等の記憶装置に接続され、対象時点ｎの利得ベクトルα_ｎの集合Λ_ｎを取得する。また、集合取得部２１０は、当該生成装置１００の内部の記憶装置等に接続され、対象時点ｎの利得ベクトルα_ｎの集合Λ_ｎを取得してもよい。本実施形態の集合取得部２１０は、生成装置１００が生成した対象時点ｎの利得ベクトルα_ｎの集合Λ_ｎを取得する例を説明する。

確率取得部２２０は、対象時点ｎにおいて各状態ｓにある想定確率ベクトルπを取得する。確率取得部２２０は、集合取得部２１０と同様に、外部のデータベース１０００等の記憶装置に接続され、想定確率ベクトルπを取得してよい。

選択部２３０は、利得ベクトルα_ｎの集合Λ_ｎおよび想定確率ベクトルπに基づいて、利得ベクトルα_ｎの集合Λ_ｎの中から利得ベクトルα^＊ _ｎを選択する。選択部２３０は、集合取得部２１０および確率取得部２２０に接続され、利得ベクトルα_ｎの集合Λ_ｎおよび想定確率ベクトルπを受けとる。

出力部２４０は、選択された利得ベクトルα^＊ _ｎに対応するアクションａを、選択すべきアクションａとして出力する。出力部２４０は、選択部２３０に接続され、選択された利得ベクトルα^＊ _ｎを受けとる。出力部２４０は、生成装置１００が選択された利得ベクトルα^＊ _ｎを生成する場合に用いたアクションａを、対応するアクションａとして選択部２３０を介して集合取得部２１０から受けとってよい。この場合、集合取得部２１０は、それぞれの利得ベクトルα_ｎに対応するアクションａを更に取得する。出力部２４０は、出力するアクションａを実行させてよい。

第２決定部２５０は、対象時点ｎから次の時点ｎ＋１への遷移に用いられる遷移パラメータの値を、遷移パラメータの取り得る範囲の中から決定する。第２決定部２５０は、出力部２４０に接続され、選択された利得ベクトルα^＊ _ｎを用いて得られる累積期待利得が予め定められた基準以下となる遷移パラメータの値を決定してよい。また、第２決定部２５０は、選択された利得ベクトルα^＊ _ｎを用いて得られる累積期待利得が最小となる遷移パラメータの値を決定する。

第２生成部２６０は、決定された遷移パラメータを用いて、対象時点ｎの次の時点ｎ＋１において各状態ｔにある想定確率π（ｔ）を生成する。第２生成部２６０は、第２決定部２５０に接続され、受けとった遷移パラメータの値と次の時点における利得ベクトルα_ｎ＋１の集合Λ_ｎ＋１の情報を用いて、次の時点ｎ＋１の想定確率ベクトルπを生成する。第２生成部２６０は、外部のデータベース１０００等の記憶装置に接続され、生成した想定確率ベクトルπを記憶する。

以上の本実施形態に係る選択装置２００は、例えば時点ｎ＝０から将来の時点Ｎ（Ｎ＞ｎ）に向けて時系列に順次アクションａを実行して想定確率ベクトルπを更新し、意思決定戦略を実行する。選択装置２００の意思決定戦略の実行について、図１１を用いて説明する。

図１１は、本実施形態に係る選択装置２００の動作フローを示す。選択装置２００は、Ｓ４１０〜Ｓ４７０の処理を実行することにより、利得ベクトルα_ｎの集合Λ_ｎに基づいて実行すべきアクションａを選択する。

まず、集合取得部２１０は、利得ベクトルα_ｎの集合Λ_ｎを取得する（Ｓ４１０）。集合取得部２１０は、集合Λ_ｎに含まれる利得ベクトルα_ｎのそれぞれに対応するそれぞれのアクションａと共に、集合Λ_ｎを取得してよい。集合取得部２１０は、意思決定戦略を実行する期間における最初の時点を対象時点ｎとして、当該対象時点ｎの利得ベクトルα_ｎの集合Λ_ｎを取得する。本実施形態に係る集合取得部２１０は、ｎ＝０を対象時点とする例を説明する。また、集合取得部２１０は、次の時点ｎ＋１の利得ベクトルα_ｎ＋１の集合Λ_ｎ＋１を取得してよい。これに代えて、集合取得部２１０は、意思決定戦略を実行する期間における利得ベクトルの集合を取得してもよい。

また、確率取得部２２０は、想定確率ベクトルπを取得する。初期の時点ｎ（＝０）の想定確率ベクトルは、ユーザ等によって予め定められた値であってよい。

次に、選択部２３０は、対象時点ｎの利得ベクトルα_ｎの集合Λ_ｎから、一の利得ベクトルα^＊ _ｎを選択する（Ｓ４２０）。選択部２３０は、次式で示すように、利得ベクトルα_ｎ（α_ｎ∈Λ_ｎ）の中から、想定確率ベクトルπ_ｎとの内積が最大となる利得ベクトルα^＊ _ｎを選択する。

次に、出力部２４０は、選択された利得ベクトルα^＊ _ｎに対応するアクションａを出力する（Ｓ４３０）。出力部２４０は、対応するアクションａを出力して、当該アクションａを実行させてよい。出力部２４０は、アクションａの実行により、観測値ｚを得る。

第２決定部２５０は、対象時点ｎから次の時点ｎ＋１への遷移に用いられる遷移パラメータの値を決定する（Ｓ４４０）。第２決定部２５０は、想定確率ベクトルπ、対応するアクションａ、観測値ｚ、および次の時点ｎ＋１の利得ベクトルα_ｎ＋１の集合Λ_ｎ＋１を用いて、遷移パラメータの値を決定する。第２決定部２５０は、一例として、次式を用いて、遷移パラメータの値を決定する。

第２決定部２５０は、ｐ（・，・｜・，ａ）の想定される範囲Ｐ^ａにおいて、対象時点ｎから次の時点ｎ＋１に遷移する場合に（累積期待利得が最小となる）最悪の場合であって、かつ、当該累積期待利得と想定確率ベクトルπとの内積が最大となる状態遷移確率関数を算出する。ここで、Ｐ（・，・｜・，ａ）が、Ｐ^ａの範囲内にあるということは、全てのｓについて、状態遷移確率関数Ｐ（・，・｜ｓ，ａ）がＰ_ｓ ^ａの範囲内にあることを意味する。このように、第２決定部２５０は、生成装置１００が生成した対象時点ｎおよび次の時点ｎ＋１の利得ベクトルの集合を取得することができるので、当該利得ベクトルの集合を用いて、対象時点ｎから次の時点ｎ＋１に遷移する場合の最悪の場合となる確率を算出することができる。

第２生成部２６０は、（数４）式で算出した確率を次式に代入して、次の時点ｎ＋１の想定確率π_ｎ＋１（ｔ）を各ｔについて算出する（Ｓ４５０）。第２生成部２６０は、算出した想定確率ベクトルπ_ｎ＋１を記憶装置等に記憶して更新する。

次に、第２生成部２６０は、アクションａの選択を終了するか否かを判断する（Ｓ４６０）。第２生成部２６０は、例えば、対象時点ｎが遷移モデルの対象期間の最後の時点Ｎになるまで、アクションａの選択を継続する（Ｓ４６０：Ｎｏ）。この場合、第２生成部２６０は、次の時点を対象時点ｎとし（Ｓ４７０）、ステップＳ４１０に戻ってアクションａの選択を継続させる。なお、ステップＳ４１０において、確率取得部２２０は、第２生成部２６０が更新した次の時点ｎ＋１の想定確率ベクトルπ_ｎ＋１を取得する。

選択装置２００は、対象時点が将来の時点Ｎ（Ｎ＞ｎ）になるまで、時系列に順次アクションａの選択と想定確率ベクトルの更新を継続し、意思決定戦略を算出する。第２生成部２６０は、対象時点が将来の時点Ｎになった場合に、アクションａの選択を終了する（Ｓ４６０：Ｙｅｓ）。

以上のように、本実施形態に係る選択装置２００は、生成装置１００が生成した利得ベクトルの集合と、想定確率ベクトルπに基づき、実行するアクションａおよび次の時点の想定確率ベクトルπ_ｎ＋１を算出する。そして、選択装置２００は、生成装置１００が生成した利得ベクトルの集合と、算出した想定確率ベクトルπ_ｎ＋１に基づき、次に実行するアクションａの選択および次の時点の想定確率ベクトルの更新を繰り返し、遷移モデルの対象期間における意思決定戦略を時系列に順次算出することができる。

本実施形態に係る生成装置１００は、状態遷移確率関数の取り得る範囲の中から、最悪の場合の状態遷移確率関数を決定して、利得ベクトルの集合を生成する。そして、選択装置２００は、生成した利得ベクトルの集合に基づき、最悪の場合において累積期待利得が最大となるように意思決定戦略を算出する。すなわち、本実施形態に係る生成装置１００および選択装置２００は、遷移モデルの遷移パラメータが予め定められた範囲内に存在する場合に、当該範囲内において最悪の場合に得られる累積期待利得を示すことができる。したがって、生成装置１００および選択装置２００は、遷移モデルの遷移パラメータを正確に推定できない場合であっても、現実的な最適意志決定戦略を算出できる遷移パラメータの範囲を推定することができる。

なお、本実施形態において、生成装置１００および選択装置２００は、別個独立に機能する装置である例を説明した。これに代えて、生成装置１００および選択装置２００は、１つの装置に備わってもよい。例えば、選択装置２００は、生成装置１００を備え、集合取得部２１０は、生成装置１００により生成された利得ベクトルの集合を取得する。

図１２は、本実施形態に係る生成装置１００および選択装置２００として機能するコンピュータ１９００のハードウェア構成の一例を示す。本実施形態に係るコンピュータ１９００は、ホスト・コントローラ２０８２により相互に接続されるＣＰＵ２０００、ＲＡＭ２０２０、グラフィック・コントローラ２０７５、および表示装置２０８０を有するＣＰＵ周辺部と、入出力コントローラ２０８４によりホスト・コントローラ２０８２に接続される通信インターフェイス２０３０、ハードディスクドライブ２０４０、およびＤＶＤドライブ２０６０を有する入出力部と、入出力コントローラ２０８４に接続されるＲＯＭ２０１０、フレキシブルディスク・ドライブ２０５０、および入出力チップ２０７０を有するレガシー入出力部と、を備える。

ホスト・コントローラ２０８２は、ＲＡＭ２０２０と、高い転送レートでＲＡＭ２０２０をアクセスするＣＰＵ２０００およびグラフィック・コントローラ２０７５とを接続する。ＣＰＵ２０００は、ＲＯＭ２０１０およびＲＡＭ２０２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィック・コントローラ２０７５は、ＣＰＵ２０００等がＲＡＭ２０２０内に設けたフレーム・バッファ上に生成する画像データを取得し、表示装置２０８０上に表示させる。これに代えて、グラフィック・コントローラ２０７５は、ＣＰＵ２０００等が生成する画像データを格納するフレーム・バッファを、内部に含んでもよい。

入出力コントローラ２０８４は、ホスト・コントローラ２０８２と、比較的高速な入出力装置である通信インターフェイス２０３０、ハードディスクドライブ２０４０、ＤＶＤドライブ２０６０を接続する。通信インターフェイス２０３０は、ネットワークを介して他の装置と通信する。ハードディスクドライブ２０４０は、コンピュータ１９００内のＣＰＵ２０００が使用するプログラムおよびデータを格納する。ＤＶＤドライブ２０６０は、ＤＶＤ−ＲＯＭ２０９５からプログラムまたはデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。

また、入出力コントローラ２０８４には、ＲＯＭ２０１０と、フレキシブルディスク・ドライブ２０５０、および入出力チップ２０７０の比較的低速な入出力装置とが接続される。ＲＯＭ２０１０は、コンピュータ１９００が起動時に実行するブート・プログラム、および／または、コンピュータ１９００のハードウェアに依存するプログラム等を格納する。フレキシブルディスク・ドライブ２０５０は、フレキシブルディスク２０９０からプログラムまたはデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。入出力チップ２０７０は、フレキシブルディスク・ドライブ２０５０を入出力コントローラ２０８４へと接続すると共に、例えばパラレル・ポート、シリアル・ポート、キーボード・ポート、マウス・ポート等を介して各種の入出力装置を入出力コントローラ２０８４へと接続する。

ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供されるプログラムは、フレキシブルディスク２０９０、ＤＶＤ−ＲＯＭ２０９５、またはＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、記録媒体から読み出され、ＲＡＭ２０２０を介してコンピュータ１９００内のハードディスクドライブ２０４０にインストールされ、ＣＰＵ２０００において実行される。

プログラムは、コンピュータ１９００にインストールされ、コンピュータ１９００を取得部１１０、初期化部１２０、第１決定部１３０、第１生成部１４０、除去部１５０、集合取得部２１０、確率取得部２２０、選択部２３０、出力部２４０、第２決定部２５０、および第２生成部２６０として機能させる。

プログラムに記述された情報処理は、コンピュータ１９００に読込まれることにより、ソフトウェアと上述した各種のハードウェア資源とが協働した具体的手段である取得部１１０、初期化部１２０、第１決定部１３０、第１生成部１４０、除去部１５０、集合取得部２１０、確率取得部２２０、選択部２３０、出力部２４０、第２決定部２５０、および第２生成部２６０として機能する。そして、この具体的手段によって、本実施形態におけるコンピュータ１９００の使用目的に応じた情報の演算または加工を実現することにより、使用目的に応じた特有の生成装置１００および選択装置２００が構築される。

一例として、コンピュータ１９００と外部の装置等との間で通信を行う場合には、ＣＰＵ２０００は、ＲＡＭ２０２０上にロードされた通信プログラムを実行し、通信プログラムに記述された処理内容に基づいて、通信インターフェイス２０３０に対して通信処理を指示する。通信インターフェイス２０３０は、ＣＰＵ２０００の制御を受けて、ＲＡＭ２０２０、ハードディスクドライブ２０４０、フレキシブルディスク２０９０、またはＤＶＤ−ＲＯＭ２０９５等の記憶装置上に設けた送信バッファ領域等に記憶された送信データを読み出してネットワークへと送信し、もしくは、ネットワークから受信した受信データを記憶装置上に設けた受信バッファ領域等へと書き込む。このように、通信インターフェイス２０３０は、ＤＭＡ（ダイレクト・メモリ・アクセス）方式により記憶装置との間で送受信データを転送してもよく、これに代えて、ＣＰＵ２０００が転送元の記憶装置または通信インターフェイス２０３０からデータを読み出し、転送先の通信インターフェイス２０３０または記憶装置へとデータを書き込むことにより送受信データを転送してもよい。

また、ＣＰＵ２０００は、ハードディスクドライブ２０４０、ＤＶＤドライブ２０６０（ＤＶＤ−ＲＯＭ２０９５）、フレキシブルディスク・ドライブ２０５０（フレキシブルディスク２０９０）等の外部記憶装置に格納されたファイルまたはデータベース等の中から、全部または必要な部分をＤＭＡ転送等によりＲＡＭ２０２０へと読み込ませ、ＲＡＭ２０２０上のデータに対して各種の処理を行う。そして、ＣＰＵ２０００は、処理を終えたデータを、ＤＭＡ転送等により外部記憶装置へと書き戻す。このような処理において、ＲＡＭ２０２０は、外部記憶装置の内容を一時的に保持するものとみなせるから、本実施形態においてはＲＡＭ２０２０および外部記憶装置等をメモリ、記憶部、または記憶装置等と総称する。本実施形態における各種のプログラム、データ、テーブル、データベース等の各種の情報は、このような記憶装置上に格納されて、情報処理の対象となる。なお、ＣＰＵ２０００は、ＲＡＭ２０２０の一部をキャッシュメモリに保持し、キャッシュメモリ上で読み書きを行うこともできる。このような形態においても、キャッシュメモリはＲＡＭ２０２０の機能の一部を担うから、本実施形態においては、区別して示す場合を除き、キャッシュメモリもＲＡＭ２０２０、メモリ、および／または記憶装置に含まれるものとする。

また、ＣＰＵ２０００は、ＲＡＭ２０２０から読み出したデータに対して、プログラムの命令列により指定された、本実施形態中に記載した各種の演算、情報の加工、条件判断、情報の検索・置換等を含む各種の処理を行い、ＲＡＭ２０２０へと書き戻す。例えば、ＣＰＵ２０００は、条件判断を行う場合においては、本実施形態において示した各種の変数が、他の変数または定数と比較して、大きい、小さい、以上、以下、等しい等の条件を満たすかどうかを判断し、条件が成立した場合（または不成立であった場合）に、異なる命令列へと分岐し、またはサブルーチンを呼び出す。

また、ＣＰＵ２０００は、記憶装置内のファイルまたはデータベース等に格納された情報を検索することができる。例えば、第１属性の属性値に対し第２属性の属性値がそれぞれ対応付けられた複数のエントリが記憶装置に格納されている場合において、ＣＰＵ２０００は、記憶装置に格納されている複数のエントリの中から第１属性の属性値が指定された条件と一致するエントリを検索し、そのエントリに格納されている第２属性の属性値を読み出すことにより、所定の条件を満たす第１属性に対応付けられた第２属性の属性値を得ることができる。

以上に示したプログラムまたはモジュールは、外部の記録媒体に格納されてもよい。記録媒体としては、フレキシブルディスク２０９０、ＤＶＤ−ＲＯＭ２０９５の他に、ＤＶＤ、Ｂｌｕ−ｒａｙ（登録商標）、またはＣＤ等の光学記録媒体、ＭＯ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークまたはインターネットに接続されたサーバシステムに設けたハードディスクまたはＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムをコンピュータ１９００に提供してもよい。

以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。

特許請求の範囲、明細書、および図面中において示した装置、システム、プログラム、および方法における動作、手順、ステップ、および段階等の各処理の実行順序は、特段「より前に」、「先立って」等と明示しておらず、また、前の処理の出力を後の処理で用いるのでない限り、任意の順序で実現しうることに留意すべきである。特許請求の範囲、明細書、および図面中の動作フローに関して、便宜上「まず、」、「次に、」等を用いて説明したとしても、この順で実施することが必須であることを意味するものではない。

１００ 生成装置、１１０ 取得部、１２０ 初期化部、１３０ 第１決定部、１４０ 第１生成部、１５０ 除去部、２００ 選択装置、２１０ 集合取得部、２２０ 確率取得部、２３０ 選択部、２４０ 出力部、２５０ 第２決定部、２６０ 第２生成部、１０００ データベース、１９００ コンピュータ、２０００ ＣＰＵ、２０１０ ＲＯＭ、２０２０ ＲＡＭ、２０３０ 通信インターフェイス、２０４０ ハードディスクドライブ、２０５０ フレキシブルディスク・ドライブ、２０６０ ＤＶＤドライブ、２０７０ 入出力チップ、２０７５ グラフィック・コントローラ、２０８０ 表示装置、２０８２ ホスト・コントローラ、２０８４ 入出力コントローラ、２０９０ フレキシブルディスク、２０９５ ＤＶＤ−ＲＯＭ

Claims (19)

1. アクションに応じて現在の状態から次の状態へと遷移する遷移モデルについて、累積期待利得の算出に用いる利得ベクトルを生成する生成装置であって、
   対象時点の次の時点以降に得られる累積期待利得の成分を前記次の時点の状態毎に含む前記次の時点の利得ベクトルを取得する取得部と、
   前記次の時点の利得ベクトルを用いて得られる累積期待利得に応じて、前記対象時点から前記次の時点への遷移に用いられる遷移パラメータの値を、前記遷移パラメータの取り得る範囲の中から決定する第１決定部と、
   決定された前記遷移パラメータを用いて、前記次の時点の利得ベクトルから、前記対象時点の利得ベクトルを生成する第１生成部と、
   を備える生成装置。
2. 前記第１決定部は、前記次の時点の利得ベクトルを用いて得られる累積期待利得が予め定められた基準以下となる前記遷移パラメータの値を決定する請求項１に記載の生成装置。
3. 前記第１決定部は、前記次の時点の利得ベクトルを用いて得られる累積期待利得が最小となる前記遷移パラメータの値を決定する請求項１または２に記載の生成装置。
4. 将来の時点における利得ベクトルを初期化する初期化部を備え、
   当該生成装置は、前記将来の時点から遡って前記対象時点における利得ベクトルを生成する
   請求項１から３のいずれか一項に記載の生成装置。
5. 前記取得部は、前記次の時点の利得ベクトルを少なくとも１つ含む前記次の時点における利得ベクトルの集合を取得し、
   前記第１決定部は、前記次の時点における利得ベクトルの集合に含まれる利得ベクトルのそれぞれについて前記遷移パラメータの値を決定し、
   前記第１生成部は、前記次の時点における利得ベクトルの集合に含まれる利得ベクトルのそれぞれについて、決定された前記遷移パラメータを用いて前記対象時点の利得ベクトルを生成して前記対象時点の利得ベクトルの集合に加える
   請求項１から４のいずれか一項に記載の生成装置。
6. 前記第１決定部は、前記対象時点における各状態から前記次の時点の各状態への遷移確率を、前記遷移確率の取り得る範囲の中から決定する請求項１から５のいずれか一項に記載の生成装置。
7. 前記第１決定部は、前記遷移確率の線形不等式によって表される前記遷移確率の取り得る範囲の中から、線形計画法により前記遷移確率を決定する請求項６に記載の生成装置。
8. 前記第１決定部は、前記遷移確率の取り得る範囲として、前記遷移確率の基準値の定数倍までの範囲の中から前記遷移確率を決定する請求項６または７に記載の生成装置。
9. 前記第１生成部が生成した前記対象時点の利得ベクトルの集合から、各状態の確率分布の範囲内で最大値を構成しない利得ベクトルを除去する除去部を更に備える請求項５に記載の生成装置。
10. 前記除去部は、前記第１生成部が生成した前記対象時点の利得ベクトルの集合から、各状態の確率分布の範囲内における予め定められた選択用の確率分布において前記累積期待利得の最大値を与えない利得ベクトルを除去する請求項９に記載の生成装置。
11. 前記第１生成部は、前記対象時点において行う複数のアクションのそれぞれに対応して、各状態における当該アクションに応じて前記第１決定部により決定された前記遷移パラメータによって状態遷移をする場合の即時期待利得と前記次の時点の利得ベクトルにおける遷移先の状態の累積期待利得とに基づいて、前記対象時点の利得ベクトルを生成する請求項１から１０のいずれか一項に記載の生成装置。
12. アクションに応じて現在の状態から次の状態へと遷移する遷移モデルにおけるアクションを選択する選択装置であって、
    対象時点以降に得られる累積期待利得の成分を前記対象時点の状態毎に含む前記対象時点の利得ベクトルの集合を取得する集合取得部と、
    前記対象時点において各状態にある想定確率を取得する確率取得部と、
    前記利得ベクトルの集合および前記想定確率に基づいて、前記利得ベクトルの集合の中から利得ベクトルを選択する選択部と、
    選択された前記利得ベクトルに対応するアクションを、選択すべきアクションとして出力する出力部と、
    前記対象時点から前記次の時点への遷移に用いられる遷移パラメータの値を、前記遷移パラメータの取り得る範囲の中から決定する第２決定部と、
    決定された前記遷移パラメータを用いて、前記対象時点の次の時点において各状態にある想定確率を生成する第２生成部と、
    を備える選択装置。
13. 前記第２決定部は、選択された利得ベクトルを用いて得られる累積期待利得が予め定められた基準以下となる前記遷移パラメータの値を決定する請求項１２に記載の選択装置。
14. 前記第２決定部は、選択された利得ベクトルを用いて得られる累積期待利得が最小となる前記遷移パラメータの値を決定する請求項１２または１３に記載の選択装置。
15. 請求項１から１１のいずれか一項に記載の生成装置を備え、
    前記集合取得部は、前記生成装置により生成された利得ベクトルの集合を取得する請求項１２から１４のいずれか一項に記載の選択装置。
16. 生成装置が、アクションに応じて現在の状態から次の状態へと遷移する遷移モデルについて、累積期待利得の算出に用いる利得ベクトルを生成する生成方法であって、
    前記生成装置の取得部が、対象時点の次の時点以降に得られる累積期待利得の成分を前記次の時点の状態毎に含む前記次の時点の利得ベクトルを取得する取得段階と、
    前記生成装置の第１決定部が、前記次の時点の利得ベクトルを用いて得られる累積期待利得に応じて、前記対象時点から前記次の時点への遷移に用いられる遷移パラメータの値を、前記遷移パラメータの取り得る範囲の中から決定する決定段階と、
    前記生成装置の第１生成部が、決定された前記遷移パラメータを用いて、前記次の時点の利得ベクトルから、前記対象時点の利得ベクトルを生成する生成段階と、
    を備える生成方法。
17. 選択装置が、アクションに応じて現在の状態から次の状態へと遷移する遷移モデルにおけるアクションを選択する選択方法であって、
    前記選択装置の集合取得部が、対象時点以降に得られる累積期待利得の成分を前記対象時点の状態毎に含む前記対象時点の利得ベクトルの集合を取得する集合取得段階と、
    前記選択装置の確率取得部が、前記対象時点において各状態にある想定確率を取得する確率取得段階と、
    前記選択装置の選択部が、前記利得ベクトルの集合および前記想定確率に基づいて、前記利得ベクトルの集合の中から利得ベクトルを選択する選択段階と、
    前記選択装置の出力部が、選択された前記利得ベクトルに対応するアクションを、選択すべきアクションとして出力する出力段階と、
    前記選択装置の第２決定部が、前記対象時点から前記次の時点への遷移に用いられる遷移パラメータの値を、前記遷移パラメータの取り得る範囲の中から決定する決定段階と、
    前記選択装置の第２生成部が、決定された前記遷移パラメータを用いて、前記対象時点の次の時点において各状態にある想定確率を生成する生成段階と、
    を備える選択方法。
18. コンピュータを、請求項１から１１のいずれか一項に記載の生成装置として機能させるプログラム。
19. コンピュータを、請求項１２から１５のいずれか一項に記載の選択装置として機能させるプログラム。

Images