(57)【要約】【課題】本発明は、不必要な混合時間の増加を抑えながら、意思決定モデルを学習する機能を実現することを目的とする。【解決手段】本発明は、マルコフ決定過程システム環境下における方策を規定するパラメータ（方策パラメータ）を更新するための技法であって、当該技法は、第１の状態（s）から第２の状態（s’）に初めて状態遷移するために必要なステップ数（到達時間）の統計量（期待到達時間関数）の第１の状態（s）と第２の状態（s’）についての重み付け和（重み付け期待到達時間和）を減少させる項を有する更新式に従って、上記方策パラメータを更新することを特徴とする上記技法を提供する。【選択図】  図４Ａ
2013242761.tif 000002
【特許請求の範囲】
【請求項１】
マルコフ決定過程システム環境下における方策を規定するパラメータ（以下、「方策パラメータ」という）を更新するための方法であって、制御器が、
第１の状態（s）から第２の状態（s’）に初めて状態遷移するために必要なステップ数（以下、「到達時間」という）の統計量（以下、「期待到達時間」という）の第１の状態（s）と第２の状態（s’）についての重み付け和（以下、「重み付け期待到達時間和」という）を減少させる項を有する更新式に従って、前記制御器の記憶部上に格納された前記方策パラメータを更新するステップ
を実行することを含む、前記方法。
【請求項２】
前記重み付け期待到達時間和を減少させる項が、
引数が第１の状態（s）と第２の状態（s’）であり且つ戻り値が前記第１の状態（s）から前記第２の状態（s’）の前記期待到達時間である関数（以下、「期待到達時間関数」という）と、
引数が第１の状態（s）と第２の状態（s’）であり且つ戻り値が前記第１の状態（s）から前記第２の状態（s’）の前記期待到達時間の前記方策パラメータに関する感度である関数（以下、「期待到達時間感度関数」という）と
を使用して導出される、請求項１に記載の方法。
【請求項３】
前記期待到達時間の前記方策パラメータに関する前記感度が、期待到達時間の前記方策パラメータに関する偏微分、又は当該偏微分の推定値である、請求項２に記載の方法。
【請求項４】
前記重み付け期待到達時間和が、
（１）前記期待到達時間関数の第１の状態（s）と第２の状態（s’）についての重み付け和、
（２）前記期待到達時間関数の第１の状態（s）と第２の状態（s’）についての加算平均、又は、
（３）前記期待到達時間関数の第１の状態（s）と第２の状態（s’）についての最大値
である、請求項２に記載の方法。
【請求項５】
前記期待到達時間が、
（１）第１の状態（s）から第２の状態（s’）の前記到達時間の期待値、若しくは当該期待値の推定値、又は、
（２）第１の状態（s）から第２の状態（s’）の前記到達時間の期待値を定数倍して定数を加えた値、若しくは当該値の推定値
である、請求項１に記載の方法。
【請求項６】
前記制御器が、
（１）前記期待到達時間関数を更新するステップ、
（２）前記期待到達時間関数を用いて前記期待到達時間を算出するステップ、
（３）前記期待到達時間感度関数を更新するステップ、又は、
（４）前記期待到達時間感度関数を用いて前記期待到達時間の前記方策パラメータに関する前記感度を算出するステップ、
のうちの少なくとも１つのステップを実行する、請求項２に記載の方法。
【請求項７】
前記制御器が、
前記（２）前記期待到達時間関数を用いて前記期待到達時間を算出するステップと、
前記（４）前記期待到達時間感度関数を用いて前記期待到達時間の前記方策パラメータに関する前記感度を算出するステップと、
前記（４）で算出された感度を前記（２）で算出された各期待到達時間に基づき重み付けをして和をとることで算出されるベクトルを、前記重み付け期待到達時間和を減少させる項として導出するステップと
を実行することを含む、請求項６に記載の方法。
【請求項８】
前記（１）前記期待到達時間関数を更新するステップが、
2013242761.tif 000064
を含む、請求項６に記載の方法。
【請求項９】
前記制御器が、
時間ステップ０で、前記期待到達時間関数を初期化するステップ
をさらに実行することを含む、請求項８に記載の方法。
【請求項１０】
各時間ステップｔ＋１での前記期待到達時間関数が以下に示す式に従って更新される、請求項９に記載の方法：
【数１】
2013242761.tif 000065
【数２】
2013242761.tif 000066
【請求項１１】
前記（２）前記期待到達時間関数を用いて前記期待到達時間算出するステップが
期待到達時間関数の推定（以下、「期待到達時間関数推定」という）のための統計量から前記期待到達時間を算出するステップ
を含み、
前記（１）各時間ステップｔ＋１での前記期待到達時間関数を更新するステップが、
前記期待到達時間関数推定のための前記統計量を更新するステップ
を含む、
請求項６に記載の方法。
【請求項１２】
前記制御器が、
時間ステップ０で、前記期待到達時間関数推定のための前記統計量を記憶する行列を初期化するステップ
をさらに実行することを含む、請求項１１に記載の方法。
【請求項１３】
前記期待到達時間関数推定のための前記統計量を更新するステップが、
2013242761.tif 000067
を含む、請求項１１に記載の方法：
【数３】
2013242761.tif 000068
【請求項１４】
前記期待到達時間を算出のための前記統計量から前記期待到達時間を算出するステップが以下に示す式を用いて行われる、請求項１１に記載の方法：
【数４】
2013242761.tif 000069
【請求項１５】
前記（３）期待到達時間感度関数を更新するステップが、
2013242761.tif 000070
を含む、請求項６に記載の方法。
【請求項１６】
前記制御器が、
時間ステップ０で、前記期待到達時間感度関数を初期化するステップ
をさらに実行することを含む、請求項１３に記載の方法。
【請求項１７】
各時間ステップｔ＋１での前記期待到達時間感度関数が以下に示す式に従って更新される、請求項１５に記載の方法：
【数５】
2013242761.tif 000071
【数６】
2013242761.tif 000072
【請求項１８】
前記（４）前記期待到達時間感度関数を用いて前記期待到達時間の前記方策パラメータに関する前記感度を算出するステップが、
期待到達時間感度関数の推定（以下、「期待到達時間感度関数推定」という）のための統計量から前記期待到達時間の前記方策パラメータに関する前記感度を算出するステップ
を含み、
前記（３）前記期待到達時間感度関数を更新するステップが、
前記期待到達時間感度関数のための統計量を更新するステップ
を含む、
請求項６に記載の方法。
【請求項１９】
前記制御器が、
時間ステップ０で、前記期待到達時間感度関数推定のための統計量を記憶する行列を初期化するステップ
をさらに実行することを含む、請求項１８に記載の方法。
【請求項２０】
前記制御器が、
2013242761.tif 000073
【数７】
2013242761.tif 000074
【請求項２１】
前記期待到達時間の前記方策パラメータに関する前記感度を算出することが以下に示す式を用いて行われる、請求項１８に記載の方法：
【数８】
2013242761.tif 000075
【請求項２２】
前記方策パラメータを更新するステップが、
前記重み付け期待到達時間和を減少させる項を用いて前記方策パラメータを更新するステップ
を含む、請求項１に記載の方法。
【請求項２３】
前記方策パラメータの更新が、以下式（１）〜（３）のいずれか一つを用いて行われる、請求項２２に記載の方法：
式（１）
【数９】
2013242761.tif 000076
式（２）
【数１０】
2013242761.tif 000077
式（３）
【数１１】
2013242761.tif 000078
【請求項２４】
マルコフ決定過程システム環境下における方策を規定するパラメータ（以下、「方策パラメータ」という）を更新するための制御器であって、
前記方策パラメータを記憶する記憶部と、
第１の状態（s）から第２の状態（s’）に初めて状態遷移するために必要なステップ数（以下、「到達時間」という）の統計量（以下、「期待到達時間」という）の第１の状態（s）と第２の状態（s’）についての重み付け和（以下、「重み付け期待到達時間和」という）を減少させる項を有する更新式に従って、前記方策パラメータを更新する更新部と
を備えている、前記制御器。
【請求項２５】
マルコフ決定過程システム環境下における方策を規定するパラメータ（以下、「方策パラメータ」という）を更新する制御プログラムであって、制御器に、請求項１〜２３のいずれか一項に記載の方法の各ステップを実行させる前記制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的には、意思決定モデルの探索技法に関し、特にはマルコフ決定過程システム環境下における学習に関する。より詳細には、本発明は、マルコフ決定過程システム環境下における方策（policy）を規定するパラメータ（以下、「方策パラメータ」ともいう）を更新するための方法、並びに、その制御器、制御プログラム及び制御プログラム製品に関する。
【背景技術】
【０００２】
従来知られている確率的な意思決定過程として、マルコフ決定過程（ＭＤＰ：Markov Decision Process）がある。マルコフ決定過程として定式化される問題は、ビジネス上の意思決定モデル、ロボット、プラント、移動機械（例えば電車、自動車、船舶及び飛行機など）などの自律的制御問題として幅広い応用領域をもつ。ビジネス上の意思決定モデルは、例えばマーケティング又はＷｅｂサービス等における意思決定支援である。
【０００３】
意思決定モデルの学習は、多種多様な場面で鍵となる重要なデータ解析技術である。例えば、マーケティング若しくはＷｅｂサービス等における意思決定支援システムの最適化、又は、交通シミュレーション等のエージェントの行動モデルの学習においてである。
【０００４】
意思決定モデルの学習において、近視眼的ではなく、大局的に最良な意思決定モデルを発見することが肝要である。そのためには、損して得とれ問題を解く必要がある。
【０００５】
下記特許文献１は、自然状態行動勾配（ＮＳＧ）の推定式において、ＬＳＤ推定値の二次の項をなくし、ＬＳＤ推定値の一次の項のみにする制御器、制御方法及び制御プログラムを記載する（特許請求の範囲、段落００１６）。
【０００６】
下記特許文献２は、学習のプラトーの発生を回避して試行回数（学習時間）を減少させることが可能な自然勾配を用いた強化学習に基づく制御器、制御方法及び制御プログラムを記載する（特許請求の範囲、段落００１８）。
【０００７】
下記特許文献３は、方策パラメータの偏りを減少させると分散が増大するというトレードオフ解決した方策学習方法を用いた制御器、制御方法及び制御プログラム記載する（特許請求の範囲、段落００１２）。
【０００８】
下記特許文献４は、計算量を減少させて、実タスクへ適用可能な自然方策勾配法のアルゴリズムを利用した制御器、制御方法及び制御プログラムを記載する（特許請求の範囲、段落００１２）。
【０００９】
下記特許文献５は、学習パターンが多数ある場合、または、時系列データなどを神経回路網モデルに学習させる課題において、学習時間を短縮する逐次型加速化学習方法、又は学習時の収束の安定性を保証する逐次型加速化学習方法を提供することを記載する（特許請求の範囲、段落００１５〜００１６）。
【００１０】
下記特許文献６は、ニューラルネットワークの学習時の繰り返し回数を減少させることにより、学習時間を短縮することを記載する（特許請求の範囲、段落００１０）。
【００１１】
下記特許文献７は、ハイリスクかつ大規模な投資をともなう研究開発プロジェクトのバリュエーション（経済価値評価）をおこない、様々な不確実性によって変動するプロジェクトの経済価値をシミュレーションし、最適な投資意思決定を支援することが可能な投資意思決定支援装置、方法及びプログラムを記載する（特許請求の範囲、段落０００６）。
【００１２】
下記非特許文献１及び非特許文献２並びに特許文献４は、方策勾配法を記載する。
【００１３】
下記非特許文献３及び非特許文献４は、自然方策勾配法を記載する。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開２０１０−９２２４７号公報
【特許文献２】特開２００９−２８９１９９号公報
【特許文献３】特開２００９−２３０６４５号公報
【特許文献４】特開２００７−６５９２９号公報
【特許文献５】特開平８−７７１３０号公報
【特許文献６】特開平１０−９１６０７号公報
【特許文献７】特開２００３−３６３３９号公報
【特許文献８】特開２００５−２７４３６３号公報
【特許文献９】特開２００２−３０７３３７号公報
【非特許文献】
【００１５】
【非特許文献１】R. J. Williams, “Simple statistical gradient-following algorithms for connectionist reinforcement learning”, Machine Learning, vol. 8, pp. 229〜256, 1992
【非特許文献２】J. Baxter et al., “Infinite-horizon policy-gradient estimation”, Journal of Artificial Intelligence Research, vol. 15, pp. 319〜350, 2001
【非特許文献３】S. Kakade, “A natural policy gradient. In Advances in Neural Information Processing Systems”, Volume 14. MIT Press, 2002
【非特許文献４】T. Morimura et al., “A new natural policy gradient by stationary distribution metric”, In European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2008
【非特許文献５】David A. Levin et al., “Markov Chains and Mixing Times”, American Mathematical Society, Providence, RI, 2008
【非特許文献６】P. L. Bartlett and J. Baxter, “Estimation and Approximation Bounds for Gradient-Based Reinforcement Learning”, Proc. Annual Conference on Computational Learning Theory, pp. 133〜141, 2000
【非特許文献７】S. M. Kakade, “On the Sample Complexity of Reinforcement Learning”, PhD thesis, University College London, March 2003
【非特許文献８】E. Greensmith, et al., “Variance reduction techniques for gradient estimates in reinforcement learning,” Journal of Machine Learning Research, vol. 5, pp. 1471〜1530, 2004
【非特許文献９】J. Andrew Bagnell et al., “Covariant Policy Search”, In Proceedings of the International Joint Conference on Articial Intelligence, pp. 1019〜1024, July 2003
【発明の概要】
【発明が解決しようとする課題】
【００１６】
逐次意思決定が行われ、環境の状態が時間的に進展する環境において、将来の状況は、過去に選択した行動に依存する。上記環境は、一般に、マルコフ決定過程によりモデル化されうる。しかしながら、多くの場合、対象とする環境のモデルはわからない。すなわち、次時刻の状態は実際に観測するまでわからない。よって、マルコフ決定過程の状態の遷移確率が、場合によっては報酬又はコスト関数が、未知の状況に対応している必要がある。しかしながら、このような状況に対して頑強な手法は未だ確立されていない。
【００１７】
状態の遷移確率が既知の場合であれば、例えば動的計画法又は近似動的計画法などの効率のよい手法が適用可能である。しかし、環境の状態が時間的に進展する環境において、リアル・タイム（オンライン）で意思決定モデルを逐次更新する手法が必要である。
【００１８】
また、意思決定モデルの更新（すなわち方策の更新又は方策の学習）により動的システムへの入力パターンが変化し、当該動的システムが安定な状態に落ち着くのに要する時間（「混合時間」ともいう）が不必要に増加してしまう場合がある（非特許文献６を参照）。混合時間の直感的イメージは、マルコフ連鎖が定常状態又は定常分布に落ち着くまでに要する時間である。
【００１９】
混合時間が不必要に増加してしまう結果、意思決定モデルの更新のために用いる統計量の推定に多くのサンプルが必要になってしまう。すなわち、最適方策の学習までに膨大なサンプルが必要になってしまう。また、混合時間の増加によって、一般に、学習が非効率になる（または困難になる）ことが理論的に解析されており、また広く知られている（非特許文献６〜８を参照）。
【００２０】
例えば、混合時間と最大期待到達時間との関係は下記式で表しうる（非特許文献５、ページ１３５の最初に記載されている式を参照）。
【数１】
2013242761.tif 000003
【００２１】
また、混合時間を制御する手法はこれまでにない。
【００２２】
また、例えば、２状態２行動のマルコフ決定過程モデルでは、初期方策に偏りがある場合には、簡単に学習の停滞が発生することが知られている（非特許文献２及び非特許文献９を参照）。
【００２３】
また、例えば、３状態以上の複雑なマルコフ決定過程モデルでは、初期方策の偏りの有無に関係なく、学習の停滞が頻繁に発生することが知られている（非特許文献４を参照）。
【００２４】
そこで、本発明は、不必要な混合時間の増加を抑えながら、意思決定モデルを学習する機能を実現することを可能にするための方策パラメータを解く（すなわち、方策パラメータを動的に更新する）ことを可能にする技法を提供することを目的とする。また、本発明は、初期値依存又は学習の停滞に頑強な技法を提供することを目的とする。
【課題を解決するための手段】
【００２５】
本発明は、マルコフ決定過程システム環境下における方策パラメータθを更新するための技法を提供する。当該技法において、方策パラメータθの更新は、第１の状態（s）から第２の状態（s’）に初めて状態遷移するために必要なステップ数（以下、「到達時間」ともいう）の統計量（以下、「期待到達時間」ともいう）の第１の状態（s）と第２の状態（s’）についての重み付け和（以下、「重み付け期待到達時間和」ともいう）を減少させる項を有する更新式に従って行われることを特徴とする。
【００２６】
本発明は、マルコフ決定過程システム環境下における方策を規定する方策パラメータθを更新するための方法を提供し、当該方法は、第１の状態（s）から第２の状態（s’）に初めて状態遷移するために必要なステップ数（到達時間）の統計量（期待到達時間）の第１の状態（s）と第２の状態（s’）についての重み付け和（重み付け期待到達時間和）を減少させる項を有する更新式に従って、上記制御器の記憶部上に格納された上記方策パラメータθを更新するステップを含む。
【００２７】
また、本発明は、コンピュータの処理により、マルコフ決定過程システム環境下における方策を規定する方策パラメータを更新するための方法を提供し、当該方法は、上記コンピュータ上で、ソフトウェア的に作成された制御ロジックを実行するステップを有し、当該制御ロジックが、第１の状態（s）から第２の状態（s’）に初めて状態遷移するために必要なステップ数（到達時間）の統計量（期待到達時間）の上記第１の状態（s）と上記第２の状態（s’）についての重み付け和（重み付け期待到達時間和）を減少させる項を有する更新式に従って、上記コンピュータに備えられている記憶部上に格納された上記方策パラメータを更新するステップを実行することを含む。
【００２８】
また、本発明は、マルコフ決定過程システム環境下における方策パラメータθを更新するための制御器を提供し、当該制御器は、プロセッサと、当該プロセッサに接続されたメモリと、上記コード及び上記に記載の方法の各ステップを実行させる制御プログラムを格納する記憶装置とを備えており、上記プロセッサが、上記制御プログラムを上記メモリに読み出して、当該制御を実行し、上記方策パラメータθを更新する。
【００２９】
また、本発明は、マルコフ決定過程システム環境下における方策パラメータθを更新するための制御器を提供し、当該制御器は、上記方策パラメータθを記憶する記憶部と、第１の状態（s）から第２の状態（s’）に初めて状態遷移するために必要なステップ数（到達時間）の統計量（期待到達時間）の第１の状態（s）と第２の状態（s’）についての重み付け和（重み付け期待到達時間和）を減少させる項を有する更新式に従って、上記方策パラメータθを更新する更新部とを備えている。
【００３０】
また、本発明は、コンピュータの処理により、マルコフ決定過程システム環境下における方策を規定する方策パラメータを更新するためのコンピュータ・システムを提供し、当該コンピュータ・システムは、上記コンピュータ上でソフトウェア的に実行される制御ロジックを備えており、当該制御ロジックは、上記方策パラメータを記憶する記憶部と、第１の状態（s）から第２の状態（s’）に初めて状態遷移するために必要なステップ数（到達時間）の統計量（期待到達時間）の第１の状態（s）と第２の状態（s’）についての重み付け和（重み付け期待到達時間和）を減少させる項を有する更新式に従って、上記方策パラメータを更新する更新部とを備えている。
【００３１】
また、本発明は、対象とするシステムの時間発展がマルコフ決定過程として記述される際に、上記システムの状態に対する制御則である確率的に表現される方策を上記システムの状態量の観測により学習する制御器を提供し、当該制御器は、プロセッサと、当該プロセッサに接続されたメモリと、制御プログラムを格納する記憶装置と、上記方策に基づいて、上記システムを制御するための制御信号を生成する制御信号生成部と、上記システムの上記状態量を観測する状態量検知部と、上記状態と上記制御信号とに予め定められた関係で依存する報酬値を獲得する報酬値獲得部とを備えており、上記方策が確率的な上記方策を規定するパラメータである方策パラメータθにより規定されており、上記プロセッサが、上記記憶装置から本発明に従う方法の各ステップを実行するための制御プログラムを上記メモリ内に読み出し、当該読み出された制御プログラムを実行する。
【００３２】
また、本発明は、マルコフ決定過程システム環境下における方策パラメータθを更新するための制御プログラムを提供し、当該制御プログラムは上記制御器に上記に記載の方法の各ステップを実行させる。
【００３３】
また、本発明は、マルコフ決定過程システム環境下における方策パラメータθを更新するための制御プログラム製品を提供し、当該制御プログラム製品は上記プログラムを有している。
【００３４】
本発明の１つの実施態様において、上記期待到達時間が、
（１）第１の状態（s）から第２の状態（s’）の上記到達時間の期待値、若しくは当該期待値の推定値、又は、
（２）第１の状態（s）から第２の状態（s’）の上記到達時間の期待値を定数倍して定数を加えた値、若しくは当該値の推定値
でありうる。
【００３５】
本発明の１つの実施態様において、上記重み付け期待到達時間和を減少させる項が、
引数が第１の状態（s）と第２の状態（s’）であり且つ戻り値が上記第１の状態（s）から上記第２の状態（s’）の上記期待到達時間である関数h(s,s’)（以下、「期待到達時間関数」ともいう）と、
引数が第１の状態（s）と第２の状態（s’）であり且つ戻り値が上記第１の状態（s）から上記第２の状態（s’）の上記期待到達時間の上記方策パラメータに関する感度である関数（以下、「期待到達時間感度関数」ともいう）と
を使用して導出されうる。
【００３６】
本発明の１つの実施態様において、上記期待到達時間の上記方策パラメータθに関する上記感度が、
（１）上記期待到達時間の上記方策パラメータθに関する偏微分、又は、
（２）上記期待到達時間の上記方策パラメータθに関する上記偏微分の推定値
でありうる。
【００３７】
本発明の１つの実施態様において、上記重み付け期待到達時間和が、
（１）上記期待到達時間関数h(s,s’)の第１の状態（s）と第２の状態（s’）についての重み付け和、
（２）上記期待到達時間関数h(s,s’)の第１の状態（s）と第２の状態（s’）についての加算平均、又は、
（３）上記期待到達時間関数h(s,s’)の第１の状態（s）と第２の状態（s’）についての最大値
でありうる。
【００３８】
本発明の１つの実施態様において、上記方法は、
（１）上記期待到達時間関数h(s,s’)を更新するステップ、
（２）上記期待到達時間関数h(s,s’)を用いて上記期待到達時間を算出するステップ、特には、上記期待到達時間を全ての状態対それぞれについて算出するステップ
（３）上記期待到達時間感度関数を更新するステップ、又は、
（４）上記期待到達時間感度関数を用いて上記期待到達時間の上記方策パラメータに関する上記感度を算出するステップ、特には、上記期待到達時間感度関数を用いて上記期待到達時間の上記方策パラメータに関する上記感度を全ての状態対それぞれについて算出するステップ
のうちの少なくとも１つのステップを含みうる。上記（１）〜（４）の各ステップは独立に実施され、特に依存関係はない。しかし、例えば、上記ステップ（１）において期待到達時間関数が更新されれば、上記ステップ（２）で算出される期待到達時間が変わりうる。また、上記ステップ（１）及び（３）を実施するために、上記ステップ（２）及び（４）の操作を事前に実施する必要はない。
【００３９】
本発明の１つの実施態様において、上記方法は、
上記（２）上記期待到達時間関数h(s,s’)を用いて上記期待到達時間を算出するステップと、特には、上記期待到達時間を全ての状態対それぞれについて算出するステップと、
上記（４）上記期待到達時間感度関数を用いて上記期待到達時間の上記方策パラメータに関する上記感度を算出するステップと、特には、上記期待到達時間の上記方策パラメータに関する上記感度を全ての状態対それぞれについて算出するステップと
上記（４）で算出された感度を上記（２）で算出された各期待到達時間に基づき重み付けをして和をとることで算出されるベクトルを、上記重み付け期待到達時間和を減少させる項として導出するステップと
を含みうる。当該方法は、上記重み付け期待到達時間和を減少させる項の導出に該当する。上記重み付け期待到達時間和を減少させる項の導出するために、上記ステップ（２）及び（４）の各操作が必要となりうる。
【００４０】
本発明の１つの実施態様において、上記（１）上記期待到達時間関数を更新するステップが、
2013242761.tif 000004
を含みうる。
【００４１】
本発明の１つの実施態様において、上記方法が、
時間ステップ０で、上記期待到達時間関数h(s,s’)を初期化するステップ
をさらに含みうる。
【００４２】
本発明の１つの実施態様において、上記期待到達時間関数h(s,s’)の初期化が、以下に示す式を用いて行われうる：
【００４３】
【数２】
2013242761.tif 000005
【００４４】
本発明の１つの実施態様において、各時間ステップｔ＋１での上記期待到達時間関数h(s,s’)が以下に示す式に従って更新されうる：
【００４５】
【数３】
2013242761.tif 000006
【００４６】
【数４】
2013242761.tif 000007
【００４７】
本発明の１つの実施態様において、上記（２）上記期待到達時間関数h(s,s’)を用いて上記期待到達時間を算出するステップが
期待到達時間関数の推定（以下、「期待到達時間関数推定」ともいう）のための統計量から上記期待到達時間を算出するステップ
を含み、
上記（１）各時間ステップｔ＋１での上記期待到達時間関数を更新するステップが、
上記期待到達時間関数推定のための上記統計量を更新するステップ
を含みうる。
【００４８】
本発明の１つの実施態様において、上記方法が、
時間ステップ０で、上記期待到達時間関数推定のための上記統計量を記憶する行列を初期化するステップ
をさらに含みうる。
【００４９】
本発明の１つの実施態様において、上記期待到達時間関数推定のための上記統計量を記憶する上記行列の初期化が、以下に示す式を用いて行われうる：
【００５０】
【数５】
2013242761.tif 000008
【００５１】
本発明の１つの実施態様において、上記期待到達時間関数推定のための上記統計量を記憶する上記行列の初期化が、以下に示す式を用いて行われうる：
【００５２】
【数６】
2013242761.tif 000009
【００５３】
本発明の１つの実施態様において、上記期待到達時間関数推定のための上記統計量を更新するステップが、
2013242761.tif 000010
を含みうる：
【００５４】
【数７】
2013242761.tif 000011
【００５５】
本発明の１つの実施態様において、上記期待到達時間を算出することが以下に示す式を用いて行われうる：
【００５６】
【数８】
2013242761.tif 000012
【００５７】
本発明の１つの実施態様において、上記（３）期待到達時間感度関数を更新するステップが、
2013242761.tif 000013
を含みうる。
【００５８】
本発明の１つの実施態様において、上記方法は、
時間ステップ０で、上記期待到達時間感度関数を初期化するステップ
をさらに実行することを含みうる。
【００５９】
本発明の１つの実施態様において、上記期待到達時間感度関数の初期化が、以下に示す式を用いて行われうる：
【００６０】
【数９】
2013242761.tif 000014
【００６１】
本発明の１つの実施態様において、各時間ステップｔ＋１での上記期待到達時間感度関数が以下に示す式に従って更新されうる。
【００６２】
【数１０】
2013242761.tif 000015
【００６３】
【数１１】
2013242761.tif 000016
【００６４】
本発明の１つの実施態様において、上記（４）上記期待到達時間感度関数を用いて上記期待到達時間の偏微分の推定ベクトルを算出するステップが、
期待到達時間感度関数の推定（以下、「期待到達時間感度関数推定」ともいう）のための統計量から上記期待到達時間の上記方策パラメータに関する上記感度を算出するステップ、特には、上記期待到達時間の上記方策パラメータに関する上記感度を全ての状態それぞれについて算出するステップ
を含みうる。また、
上記（３）上記期待到達時間感度関数を更新するステップが、
上記期待到達時間感度関数のための統計量を更新するステップ
を含みうる。
【００６５】
本発明の１つの実施態様において、上記方法は、
時間ステップ０で、上記期待到達時間感度関数推定のための統計量を記憶する行列を初期化するステップ
をさらに含みうる。
【００６６】
本発明の１つの実施態様において、上記期待到達時間感度関数推定のための上記統計量を記憶する上記行列の上記初期化が、以下に示す式を用いて行われうる：
【００６７】
【数１２】
2013242761.tif 000017
【００６８】
本発明の１つの実施態様において、上記期待到達時間感度関数推定のための上記統計量を記憶する上記行列の上記初期化が、以下に示す式を用いて行われうる：
【００６９】
【数１３】
2013242761.tif 000018
【００７０】
本発明の１つの実施態様において、上記方法は、
2013242761.tif 000019
【００７１】
【数１４】
2013242761.tif 000020
【００７２】
本発明の１つの実施態様において、上記期待到達時間の上記方策パラメータに関する上記感度を算出することが以下に示す式を用いて行われうる：
【００７３】
【数１５】
2013242761.tif 000021
【００７４】
本発明の１つの実施態様において、上記方策パラメータθの更新が、以下のいずれかの式を用いて行われうる：
【００７５】
【数１６】
2013242761.tif 000022
【００７６】
本発明の１つの実施態様において、方策パラメータθの更新を行うために使用される上記式が以下に示す式で表されうる：
【００７７】
【数１７】
2013242761.tif 000023
【００７８】
本発明の１つの実施態様において、上記方策パラメータθの更新を行うために使用される上記式が以下に示す式で表されうる：
【００７９】
【数１８】
2013242761.tif 000024
【００８０】
2013242761.tif 000025
【００８１】
【数１９】
2013242761.tif 000026
又は、
【００８２】
【数２０】
2013242761.tif 000027
【００８３】
本発明の機能を実行するためのコンピュータ・プログラムは、フレキシブル・ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＤＶＤ、ＢＤ、ハードディスク装置、ＵＳＢに接続可能なメモリ媒体、ＲＯＭ、ＭＲＡＭ、ＲＡＭ等の任意のコンピュータ読み取り可能な記録媒体に格納することができる。当該コンピュータ・プログラムは、記録媒体への格納のために、通信回線で接続する他のデータ処理システムからダウンロードしたり、又は他の記録媒体から複製したりすることができる。また、当該コンピュータ・プログラムは、圧縮し、又は複数に分割して、単一又は複数の記録媒体に格納することもできる。また、様々な形態で、本発明を実施するコンピュータ・プログラム製品を提供することも勿論可能であることにも留意されたい。コンピュータ・プログラム製品は、例えば、上記コンピュータ・プログラムを記録した記憶媒体、又は、上記コンピュータ・プログラムを伝送する伝送媒体を包含しうる。
【００８４】
本発明の上記概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの構成要素のコンビネーション又はサブコンビネーションもまた、本発明となりうることに留意すべきである。
【００８５】
本発明の実施態様において使用されるコンピュータの各ハードウェア構成要素を、複数のマシンと組み合わせ、それらに機能を配分し実施する等の種々の変更は当業者によって容易に想定され得ることは勿論である。それらの変更は、当然に本発明の思想に包含される概念である。ただし、これらの構成要素は例示であり、そのすべての構成要素が本発明の必須構成要素となるわけではない。
【００８６】
また、本発明は、ハードウェア、ソフトウェア、又は、ハードウェア及びソフトウェアの組み合わせとして実現可能である。ハードウェアとソフトウェアとの組み合わせによる実行において、上記コンピュータ・プログラムがインストールされた装置における実行が典型的な例として挙げられる。かかる場合、該コンピュータ・プログラムが該装置のメモリにロードされて実行されることにより、該コンピュータ・プログラムは、該装置を制御し、本発明にかかる処理を実行させる。該コンピュータ・プログラムは、任意の言語、コード、又は、表記によって表現可能な命令群から構成されうる。そのような命令群は、該装置が特定の機能を直接的に、又は、１．他の言語、コード若しくは表記への変換、２．他の媒体への複製、のいずれか一方若しくは双方が行われた後に、実行することを可能にするものである。
【発明の効果】
【００８７】
本発明の実施態様によれば、マルコフ決定過程システム環境下で時間的大きさ（混合時間でもありうる）を抑えることによって、従来法である自然方策勾配法に比べて効率よく学習することができる。また、本発明の実施態様によれば、従来法である自然方策勾配法に比べて初期値依存性を圧倒的に減らすことができ、また最適方策をほぼ常に発見できる。本発明は、マルコフ決定として定式化される問題、例えばビジネス上の意思決定モデル、ロボット、プラント、移動機械（例えば電車、自動車、船舶及び飛行機など）などの自律的制御問題に適用されうる。また、本発明は、ビジネス上の意思決定モデル、例えばマーケティング又はＷｅｂサービス等における意思決定支援に適用されうる。
【図面の簡単な説明】
【００８８】
【図１】本発明の実施態様に従う制御器を実現するためのハードウェア構成の一例を示した図である。
【図２】図１に従うハードウェア構成を好ましくは備えており、本発明の実施態様に従う制御器の機能ブロック図である。
【図３Ａ】学習の標準的な設定を示す模式図である。
【図３Ｂ】環境の状態遷移を示す模式図である。
【図４Ａ】本発明の実施態様に従う、方策パラメータθの更新を実現する処理のためのフローチャートを示す。
【図４Ｂ】図４Ａに記載の方策パラメータθの更新を実施するステップの詳細を示すフローチャートを示す。
【図５】図３Ｂに示す２つの選択肢のある環境をモデル化したマルコフ決定過程において、本発明の実施態様及び従来方法に従い方策パラメータθを更新した場合の経時的な平均報酬についてのシミュレーション結果を示すグラフである。
【図６】図３Ｂに示す２つの選択肢のある環境を一般化したマルコフ決定過程において、本発明の実施態様及び従来方法に従い方策パラメータθを更新した場合の初期値依存性について網羅的に調査した結果を示すグラフである。
【発明を実施するための形態】
【００８９】
マルコフ連鎖、並びにマルコフ連鎖の混合時間と到達時間について、以下に説明をする。なお、数式において、細字はスカラーであり、太字大文字で表される変数は行列であり、太字小文字で表される変数はベクトルである。ただし、本明細書中において、太字と細字を区別していない箇所がありうる。
【００９０】
いわゆる強化学習（ＲＬ：Reinforcemnt Learning）は、マルコフ決定過程に対する最適制御に関する従来技術である。強化学習とは、エージェントが環境と相互作用を通じて試行錯誤し、得られる累積報酬量を最大化するような方策と呼ばれる行動則、すなわち、制御問題に用いる場合には制御規則を学習する理論的な枠組みである。この学習法は、環境やエージェント自身に関する先験的な知識をほとんど必要としない点で様々な分野から注目を集めている。
【００９１】
強化学習は、価値関数更新法と直接方策更新法（方策勾配法）の２つに分類されうる。価値関数更新法では、価値関数を用いて間接的に方策を表現し、価値関数を更新することによって方策が更新される。直接方策更新法では、方策を明示的に持ち、目的関数の勾配に従って方策が更新される。
【００９２】
直接方策更新法では、行動のランダム性を制御するパラメータを方策パラメータθに含めることによって確率的方策の獲得が可能である。また、直接方策更新法は、連続系への適用性も高いために、特に注目を集めている。しかし、直接方策更新法を一般に実タスクへ適用すると、適切な行動則を獲得するまでの時間が非現実的となることがある。そこで、複数学習器の同時利用、モデルの利用、教示信号の利用等の補助機構を入れて学習時間を短縮させることが行われている。
【００９３】
方策勾配強化学習法（ＰＧＲＬ）は、方策パラメータθについての平均報酬の偏微分を用いることにより、方策パラメータθを改善して平均報酬を最大化するための強化学習の一般的なアルゴリズムである。上記平均報酬の偏微分は、方策勾配（ＰＧ：Policy Gradient）とも呼ばれる。方策勾配強化学習法は、エージェントが環境と相互作用する際に得られる報酬の時間平均値を目的関数とし、当該目的関数を局所最大化する方策（行動則）の獲得を目指した方策探索法であり、方策パラメータθを目的関数の勾配により逐次更新することで実現される。
【００９４】
方策さえ適切にパラメータ化すれば、エージェント又は環境に関する知識を必要とせずに、マルコフ決定過程に実装可能である。また、行動のランダム性を制御するパラメータも方策パラメータθに含めることで確率的な方策の獲得も可能になる。
【００９５】
以下では、マルコフ決定過程が、有限状態集合Ｓと、有限行動集合Ａで定義される。また、有限状態集合の要素s∈Ｓと、有限行動集合の要素a∈Ａを考える。ここで、dは方策パラメータθの次元であり、Ｒdはd次元実数ベクトルの集合である。
【００９６】
方策（意思決定モデル）は、微分可能なパラメータ化された確立モデルであり、π(a|s;θ)で表される。ここで、aは行動、sは状態、θは方策パラメータである。行動aと状態sとの関係は、ある状態sのときにある行動aをとるということである。方策パラメータθは実数ベクトルでありうる。方策パラメータθは、θ∈Ｒdである。そして、マルコフ決定過程では、各時間ステップｔで、学習主体（学習器ともいう）は、π(a|s;θ)という確率モデルをもつ方策に従い、行動atを選択する。方策π(a|s;θ)は、離散時間マルコフ決定過程では、π(a|s;θ)≡Pr(a|s;θ)で与えられる。π(a|s;θ)の具体的な確率モデルとしては例えば、多項ロジットモデル、ロジスティック・シグモイド関数、又はニューラルネットワークを利用しうる。なお、以下の説明において、方策がPr(a|s;θ)で示されている場合であっても、離散時間マルコフ決定過程以外のものを排除する意味ではないことに留意されたい。
【００９７】
マルコフ決定過程では、状態数及び行動数は既知であるが、状態遷移確率及び報酬分布（又はコスト分布）は未知である。学習主体は、各時間ステップｔで、確率的方策に従って行動を選択し、次状態st+1と報酬rtを受け取る。学習問題、例えば強化学習問題として、マルコフ決定過程は、方策固定のもとでは、以下に示す状態遷移確率をもつマルコフ連鎖とみなせる。
【数２１】
2013242761.tif 000028
【００９８】
離散時間マルコフ決定過程では、前述のように、各時間ステップｔで、学習主体が、方策パラメータθ∈Ｒdによって規定されるπ(a|s;θ)という確率モデルをもつ方策に従い、行動atを選択する。そして状態遷移確率Pr(st+1|st;θ)によって新しい状態st+1に遷移し、有界な報奨関数r(st,at,st+1)により定まる即時報酬rt+1を獲得する。報奨関数r()は、有界であるなら、どのようなものでもよく、課題に応じて設計者が決定しうる。例えば、ロボットに、得点を獲得することを目的とするゲームを対戦で行わせるなら、得点を入れた時間ステップでは正の大きい報酬、得点を取られた時間ステップでは負の報酬、それ以外では報酬がゼロになるようにしうる。
【００９９】
方策パラメータθを決めるとは、即時報酬の時間平均である平均報酬を局所最大化する方策パラメータθ*を同定することである。方策パラメータθは、下記の式に従い決定されうる。
【０１００】
【数２２】
2013242761.tif 000029
【０１０１】
こうして同定された方策パラメータθ*により規定される方策π(a|s;θ*)は、目的方策と呼ばれる。
【０１０２】
なお、方策π(a|s;θ)は、パラメータθに関して滑らか（すなわち、偏微分可能）であり、状態遷移確率と方策により規定されるマルコフ連鎖は、エルゴード性、すなわち初期状態によらない定常分布をもつとする。
【０１０３】
2013242761.tif 000030
【０１０４】
到達時間は例えば、下記式で表されうる。
【０１０５】
【数２３】
2013242761.tif 000031
【０１０６】
期待到達時間は、到達時間の統計量と定義されうる。期待到達時間は、
（１）第１の状態（s）から第２の状態（s’）の到達時間の期待値、若しくは当該期待値の推定値、又は、
（２）第１の状態（s）から第２の状態（s’）の到達時間の期待値を定数倍して定数ｘを加えた値、若しくは当該値の推定値
でありうる。定数ｘは適当な定数である。
【０１０７】
第１の状態（s）から第２の状態（s’）の到達時間の期待値（すなわち、ある確率変数Ｘの期待値）は、例えば、E[ X(s, s’)]で表されうる。また、第１の状態（s）から第２の状態（s’）の到達時間の期待値の推定値は、例えば、1/N Σn=1N X_n(s,s’)で表されうる。
【０１０８】
期待到達時間は例えば、下記式で表されうる。
【０１０９】
【数２４】
2013242761.tif 000032
【０１１０】
重み付け期待到達時間和は、期待到達時間の統計量の第１の状態（s）と第２の状態（s’）についての重み付け和であり、当該重み付け期待到達時間和は、
（１）上記期待到達時間関数h(s,s’)の第１の状態（s）と第２の状態（s’）についての重み付け和、
（２）上記期待到達時間関数h(s,s’)の第１の状態（s）と第２の状態（s’）についての加算平均、又は、
（３）上記期待到達時間関数h(s,s’)の第１の状態（s）と第２の状態（s’）についての最大値
でありうる。
【０１１１】
最大期待到達時間は例えば、下記式で表されうる。
【０１１２】
【数２５】
2013242761.tif 000033
【０１１３】
上記期待到達時間の方策パラメータθに関する感度は、
（１）期待到達時間の上記方策パラメータθに関する偏微分、又は、
（２）期待到達時間の上記方策パラメータθに関する上記偏微分の推定値でありうる。
【０１１４】
期待到達時間の方策パラメータθ∈Rd に関する偏微分は例えば、下記式で表されうる。
【０１１５】
【数２６】
2013242761.tif 000034
【０１１６】
本発明は、マルコフ決定過程の状態対の時間的距離に由来する指標、好ましくは混合時間（推定困難である）の上限である最大期待到達時間、が不必要に大きくなり、学習が非効率になることを防ぐために、従来の方策更新量を上記指標の方策を規定する方策パラメータθを、上記指標の方策パラメータθに関する感度、好ましくは上記指標の偏微分、で正規化する。
【０１１７】
上記指標は、下記に述べる推定手法１によって推定可能である。上記感度は、下記に述べる推定手法２によって推定可能である。そして、上記正規化は、下記に述べる方策パラメータθの更新手法（ステップ１及び２を含む）によって実現可能である。当該正規化は、混合時間の増加を抑制しうる。
【０１１８】
（Ａ）推定手法１及び２について
本発明において、方策パラメータθの更新は、当該方策パラメータθを更新するための更新式を実施することによって行われうる。具体的には、方策パラメータθは、本発明に従う、以下に示す推定手法１又は推定手法２によってそれぞれ求められうる期待到達時間又は重み付け期待到達時間和の方策パラメータθに関する感度を使用して、更新されうる。
【０１１９】
（１）推定手法１
推定手法１は、経験サンプルからの期待到達時間を推定する手法である。推定手法１には、オンライン・マナー方法（On-line manner method）及び最小二乗法に基づく方法（Least squares based method）の２つがある。オンライン・マナー方法は、最小二乗法に基づく方法に比べて計算コストは低いが非効率である。一方、最小二乗法に基づく方法はオンライン・マナー方法に比べて効率的であるが、計算コストが高い。従って、推定手法１のいずれの方法を用いるかは、計算環境、意思決定モデルの種類などによって、ユーザが任意に決定しうる。また、好ましくは、ユーザは、推定手法１及び２の両方を用いるように設定しうる（下記図４Ａ、ステップ４０３）。
【０１２０】
（１−１）推定手法１におけるオンライン・マナー方法について以下に説明する。
【０１２１】
（１−１−Ａ）期待到達時間関数の初期化（下記図４Ａ、ステップ４０２）
・制御器（２０１）は、時間ステップ０で、上記期待到達時間関数を初期化しうる。制御器（２０１）は、当該期待到達時間関数の初期化を例えば、以下に示す式を用いて行いうる。
【０１２２】
【数２７】
2013242761.tif 000035
【０１２３】
（１−１−Ｂ）期待到達時間関数の更新（下記図４Ａ、ステップ４０８）
【０１２４】
2013242761.tif 000036
【０１２５】
・制御器（２０１）は、各時間ステップｔ＋１での上記期待到達時間関数を以下に示す式に従って更新しうる：
【０１２６】
【数２８】
2013242761.tif 000037
【０１２７】
【数２９】
2013242761.tif 000038
【０１２８】
（１−２）推定手法１における最小二乗法に基づく方法について以下に説明する。
【０１２９】
（１−２−Ａ）期待到達時間関数推定のための統計量を記憶する行列の初期化（図４Ａ、ステップ４０２）
・制御器（２０１）は、時間ステップ０で、上記期待到達時間関数推定のための統計量を記憶する行列を初期化しうる。制御器（２０１）は、当該行列の初期化を例えば、以下に示す式を用いて行いうる。
【０１３０】
【数３０】
2013242761.tif 000039
【０１３１】
制御器（２０１）は、また、単純な初期化の一つとして以下に示す式を用いて上記統計量を記憶する行列を初期化しうる。
【０１３２】
【数３１】
2013242761.tif 000040
【０１３３】
（１−２−Ｂ）期待到達時間関数推定のための統計量の更新（図４Ａ、ステップ４０８）
【０１３４】
2013242761.tif 000041
【０１３５】
【数３２】
2013242761.tif 000042
【０１３６】
・制御器（２０１）は、期待到達時間関数の算出を以下に示す式を用いて行いうる。制御器（２０１）は、期待到達時間関数の算出を当該期待到達時間の算出が必要なときのみ、例えば方策の更新時に実行しうる。
【０１３７】
【数３３】
2013242761.tif 000043
【０１３８】
推定手法１のみを使用して方策パラメータθを更新するアプリケーション例として、ソーシャルネットワーク等の全人間／アイテム間の距離（つながり度）の推定、又は、道路ネットワーク等の全２点間の時間的距離（連結度合い）の推定がありうる。
【０１３９】
（２）推定手法２
推定手法２は、経験サンプルからの、期待到達時間の方策パラメータθに関する感度、好ましくは期待到達時間の上記方策パラメータに関する偏微分又は当該偏微分の推定値、を計算又は更新する手法である。推定手法２には、オンライン・マナー方法（On-line manner method）及び最小二乗法に基づく方法（Least squares based method）の２つがある。オンライン・マナー方法は、最小二乗法に基づく方法に比べて計算コストは低いが非効率である。一方、最小二乗法に基づく方法はオンライン・マナー方法に比べて効率的であるが、計算コストが高い。従って、ユーザは、推定手法２のいずれの方法を用いるかを、計算環境、意思決定モデルの種類などによって任意に決定しうる。
【０１４０】
（２−１）推定手法２におけるオンライン・マナー方法について以下に説明する。
【０１４１】
（２−１−Ａ）方策パラメータθに関する期待到達時間関数の偏微分関数、すなわち期待到達時間感度関数の初期化（図４Ａ、ステップ４０２）
・制御器（２０１）は、時間ステップ０で、第１の状態（s）及び第２の状態（s’）についての状態対（s，s’）の関数であり且つ期待到達時間感度関数を初期化しうる。制御器（２０１）は、当該期待到達時間感度関数の初期化を例えば、以下に示す式を用いて行いうる。
【０１４２】
【数３４】
2013242761.tif 000044
【０１４３】
（２−１−Ｂ）期待到達時間感度関数の算出（図４Ａ、ステップ４０８）
【０１４４】
2013242761.tif 000045
【０１４５】
・制御器（２０１）は、各時間ステップｔ＋１での上記期待到達時間感度関数を以下に示す式に従って更新しうる。
【０１４６】
【数３５】
2013242761.tif 000046
【０１４７】
【数３６】
2013242761.tif 000047
【０１４８】
（２−２）推定手法２における最小二乗法に基づく方法について以下に説明する。
【０１４９】
（２−２−Ａ）期待到達時間感度関数推定のための統計量を記憶する行列の初期化（図４Ａ、ステップ４０２）
・制御器（２０１）は、時間ステップ０で、上記期待到達時間感度関数推定のための上記統計量を記憶する上記行列を初期化しうる。制御器（２０１）は、当該統計量を記憶する行列の初期化を例えば、以下に示す式を用いて行いうる。
【０１５０】
【数３７】
2013242761.tif 000048
【０１５１】
・制御器（２０１）は、また、単純な初期化の一つとして以下に示す式を用いて上記統計量を記憶する行列を初期化しうる。
【０１５２】
【数３８】
2013242761.tif 000049
【０１５３】
（２−２−Ｂ）期待到達時間感度関数のための統計量の更新（図４Ａ、ステップ４０８）
【０１５４】
2013242761.tif 000050
【０１５５】
【数３９】
2013242761.tif 000051
【０１５６】
忘却率βtは例えば、0.95、又は、tanh(f+t)でありうる。パラメータｆは、ユーザが予め設定しうるパラメータである。推定手法２における忘却率βtは、推定手法１における忘却率βtと同一である必要はない。
【０１５７】
2013242761.tif 000052
【０１５８】
・制御器（２０１）は、上記期待到達時間感度関数の算出を以下に示す式を用いて行いうる。制御器（２０１）は、上記期待到達時間感度関数の算出を当該感度が必要なときのみ、例えば方策の更新時に実行しうる。
【０１５９】
【数４０】
2013242761.tif 000053
【０１６０】
推定手法１及び２はそれぞれ単独で用いられてもよく、又は、いずれか一方を用いてもよい。
【０１６１】
（Ｂ）方策パラメータθの更新手法について（図４Ａ、ステップ４１０；下記図４Ｂ）
本発明において、混合時間を抑えた方策パラメータθの更新手法は、上記した推定手法１及び／又は推定手法２で得られた各推定値を使用して行いうる。
【０１６２】
上記方策パラメータθの更新は、重み付け期待到達時間和を減少させる項を用いて方策パラメータθを更新することによって行われうる。
【０１６３】
上記方策パラメータθの更新は、下記オプション式１を用いて行われうる。
【０１６４】
・オプション式１
【０１６５】
【数４１】
2013242761.tif 000054
【０１６６】
オプション式１は例えば、下記のオプション式２に書き換えられる。
【０１６７】
・オプション式２
【０１６８】
【数４２】
2013242761.tif 000055
【０１６９】
オプション式１は例えば、下記のオプション式３に書き換えられる。
【０１７０】
【数４３】
2013242761.tif 000056
【０１７１】
2013242761.tif 000057
【０１７２】
2013242761.tif 000058
【０１７３】
【数４４】
2013242761.tif 000059
又は、
【０１７４】
【数４５】
2013242761.tif 000060
【０１７５】
以下に、本発明を実施するための最良の形態を図面に基づいて詳細に説明するが、以下の実施態様は特許請求の範囲に係る発明を限定するものでなく、また実施態様の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。また、本発明は多くの異なる態様で実施することが可能であり、以下の実施態様において、種々の変更又は改良を加えることが可能であることが当業者に明らかである。
【０１７６】
以下において、特に断らない限り、発明を実施するための形態の説明の全体を通じて同じ要素には同じ番号を付している。
【０１７７】
図１は、本発明の実施態様に従う制御器、例えばコンピュータを実現するためのハードウェア構成の一例を示した図である。
【０１７８】
図１は、本発明の実施形態に従う制御器（１０１）を示す。制御器（１０１）は、例えばコンピュータ、コンピュータ・システム、ロボット若しくはその他の電気製品でありうる。代替的には、制御器（１０１）は例えばＩＣチップ又は制御基板であり、例えばコンピュータ、コンピュータ・システム、ロボット若しくはその他の電気製品が当該ＩＣチップ又は制御基板を備えうる。制御器（１０１）は、ソフトウェア構成である上記制御ロジック（図示せず）を備えうる。制御器（１０１）は、ＣＰＵ（１０２）とメイン・メモリ（１０３）とを備えており、これらはバス（１０４）に接続さうる。ＣＰＵ（１０２）は好ましくは、３２ビット又は６４ビットのアーキテクチャに基づくものであり、例えば、インテル社のＣｏｒｅ  ｉ（商標）シリーズ、Ｃｏｒｅ  ２（商標）シリーズ、Ａｔｏｍ（商標）シリーズ、Ｘｅｏｎ（商標）シリーズ、Ｐｅｎｔｉｕｍ（登録商標）シリーズ、Ｃｅｌｅｒｏｎ（登録商標）シリーズ、ＡＭＤ社のＯｐｔｅｒｏｎ（商標）シリーズ、Ｐｈｅｎｏｍ（商標）シリーズ、Ａｔｈｌｏｎ（商標）シリーズ、Ｔｕｒｉｏｎ（商標）シリーズ、Ｓｅｍｐｒｏｎ（商標）又はＡシリーズ、インターナショナル・ビジネス・マシーンズ・コーポレーション（登録商標）のＰｏｗｅｒＰＣ（登録商標）が使用されうる。バス（１０４）には、ディスプレイ・コントローラ（１０５）を介して、ディスプレイ（１０６）、例えば液晶ディスプレイ（ＬＣＤ）が接続されうる。ディスプレイ（１０６）は、コンピュータの管理のために、通信回線を介してネットワークに接続されたコンピュータについての情報と、そのコンピュータ上で動作中のソフトウェアについての情報を、適当なグラフィック・インタフェースで表示するために使用される。バス（１０４）にはまた、ＳＡＴＡ又はＩＤＥコントローラ（１０７）を介して、ディスク（１０８）、例えばシリコン・ディスク又はハードディスクが接続されうる。また、バス（１０４）にはまた、ＳＡＴＡ又はＩＤＥコントローラ（１０７）を介して、任意的に、ドライブ（１０９）、例えばＣＤ、ＤＶＤ又はＢＤドライブが接続されうる。バス（１０４）にはさらに、任意的に、キーボード・マウスコントローラ（１１０）又はＵＳＢバス（図示せず）を介して、キーボード（１１１）及びマウス（１１２）が接続されうるが、本発明を実施する上では必要ない。
【０１７９】
ディスク（１０８）には、オペレーティング・システム、Ｐｙｔｈｏｎ処理環境、Ｐｙｔｈｏｎアプリケーション、Ｐｙｔｈｏｎ実行時コンパイラを提供するプログラム、Ｊ２ＥＥなどのＪａｖａ（登録商標）処理環境、Ｊａｖａ（登録商標）アプリケーション、Ｊａｖａ（登録商標）仮想マシン（ＶＭ）、Ｊａｖａ（登録商標）実行時（ＪＩＴ）コンパイラを提供するプログラム、その他のプログラム、及びデータが、メイン・メモリにロード可能なように記憶されている。また、ディスク（１０８）には、コードの入力乃至は編集を可能にするソフトウェア、文字変換処理ソフトウェアであるフロント・エンド・プロセッサ（ＦＥＰ）がメイン・メモリにロード可能なように記憶されている。また、ディスク（１０８）には、様々な統計量及びパラメータなど、永続的に保存され且つ随時書き換えられる可能性のあるデータが格納されうる。また、ディスク（１０８）には、オペレーティング・システムは、例えば、ＬＩＮＵＸ（登録商標）ディストリビュータが提供するＬＩＮＵＸ（登録商標）、マイクロソフト・コーポレーションが提供するＷｉｎｄｏｗｓ（登録商標）オペレーティング・システム、アップル・コンピュータ・インコーポレイテッドが提供するＭａｃＯＳ（登録商標）若しくはｉＯＳ（登録商標）、Ｘ  Ｗｉｎｄｏｗ  Ｓｙｓｔｅｍを備えるＵＮＩＸ（登録商標）系システム（たとえば、インターナショナル・ビジネス・マシーンズ・コーポレーション（登録商標）が提供するＡＩＸ（登録商標））でありうる。また、オペレーティング・システムは、制御器（１０１）内に組み込まれた組み込み用オペレーティング・システムでありうる。オペレーティング・システムは、電源投入時にメイン・メモリ（１０３）にロードされ、ＣＰＵ（１０２）及びその他の周辺装置を制御する動作を行う。
【０１８０】
ドライブ（１０９）は、必要に応じて、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ又はＢＤからプログラムをディスク（１０８）にインストールするために使用されうる。
【０１８１】
通信インタフェース（１１４）は、例えばイーサネット（登録商標）・プロトコルに従う。通信インタフェース（１１４）は、通信コントローラ（１１３）を介してバス（１０４）に接続され、コンピュータ（１０１）を通信回線（１１５）に物理的に接続する役割を担い、コンピュータ（１０１）のオペレーティング・システムの通信機能のＴＣＰ／ＩＰ通信プロトコルに対して、ネットワーク・インタフェース層を提供する。なお、通信回線は、有線ＬＡＮ環境に基づくもの、又は、無線ＬＡＮ環境、例えば、ＩＥＥＥ８０２．１１ａ／ｂ／ｇ／ｎなどのＷｉ−Ｆｉ規格に基づくものであってもよい。
【０１８２】
バス（１０４）は、所定の入出力インターフェース（図示しない）を介して、センサ（図示しない）及びアクチュエータ（図示しない）が接続されうる。センサは例えば、ＧＰＳ及び位置検出装置でありうる。位置検出装置については、これに限定されないが例えば特開２００５−２７４３６３号公報に記載されているような室内無線局の三角測量技術を使用しうる。上記センサによって検出された位置の信号は、バス（１０４）を介してＣＰＵ（１０２）に送られ、後述する本発明の処理に従い、方策パラメータθを更新するために使用されうる。アクチュエータは例えば、ＣＰＵ（１０２）からバス（１０４）を経由して送られる駆動信号に基づき、モータなどにより二次元又は三次元的に移動をもたらす機構でありうる。アクチュエータについては、これに限定されないが例えば特開２００２−３０７３３７号公報に記載されているような、適宜四輪を駆動して、ロボットを室内で二次元的に移動させる機構でありうる。
【０１８３】
以上から、本発明の実施態様において使用されるコンピュータは、特定のオペレーティング・システム環境に限定されるものではないことを理解することができるであろう。
【０１８４】
図２は、図１に従うハードウェア構成を好ましくは備えており、本発明の実施態様に従う制御器の機能ブロック図である。
制御器（２０１）は、本発明の前提となる確率的な意思決定モデルのシステムを実装しうる。制御器（２０１）では、マルコフ決定過程が例えば、有限状態集合Ｓと、有限行動集合Ａで定義されている。また、当該マルコフ決定過程において、有限状態集合の要素がs∈Ｓであり、有限行動集合の要素がa∈Ａであるとする。そして、学習主体が、マルコフ決定過程では、各時間ステップｔで、方策パラメータθ∈Ｒdによって規定されるπ(a|s;θ)という確率モデルをもつ方策２０２に従い、行動atを選択する。ここで、dはパラメータθの次元であり、Ｒdはd次元実数ベクトルの集合である。
【０１８５】
制御器（２０１）は、方策（２０２）、及び本発明を実装するための更新処理実施部（２０５）を備えている。
【０１８６】
また、制御器（２０１）は、観測器（２０４）をその中に備えているか、又は、観測器（２０４）に接続されているか、又は、観測器（２０４）からの観測データを受信しうる。観測器（２０４）は例えば、位置センサ、角度センサ、加速度センサ、角加速度センタでありうるが、これらに制限されない。観測器（２０４）が制御器に渡す信号（情報）は離散状態であるとする。
【０１８７】
また、制御器（２０１）は、記憶装置（２１０）を内蔵しているか、又は、制御器（２０１）外にある記憶装置（２１０）に有線的に又は無線的に接続されうる。
【０１８８】
制御器（２０１）が、例えばロボットの制御システムであるとすると、行動atは、例えば上記したアクチュエータの駆動を引き起こし、ロボットは、学習する環境（２０３）としての所定の室内を移動する。その移動に従い、制御器（２０１）は、即時報酬rt+1を受け取り、状態量は、st+1となる。なお、制御器（２０１）が、ロボットの制御システムに限定されず、ビジネス上の意思決定モデル、プラント、移動機械（電車、自動車、船舶及び飛行機など）などの自律的制御問題を適用可能な、さまざまな適用技術があることを、この分野の当業者なら理解するであろう。
【０１８９】
状態量は、観測器（２０４）によって観測され、観測器（２０４）の観測結果sは、方策（２０２）に入力される。
【０１９０】
更新処理実施部（２０５）は、第１の状態（s）から第２の状態（s’）に初めて状態遷移するために必要なステップ数（到達時間）の統計量（期待到達時間）の第１の状態（s）と第２の状態（s’）についての重み付け和（重み付け期待到達時間和）を減少させる項を有する更新式に従って、記憶装置（２１０）上に格納された方策パラメータ（２１２）、又は、制御器（２０１）中のメモリ（１０３）内に格納された方策パラメータθを更新する。重み付け期待到達時間和を減少させる項は、引数が第１の状態（s）と第２の状態（s’）であり且つ戻り値が当該第１の状態（s）から当該第２の状態（s’）の期待到達時間である関数（期待到達時間関数）と、引数が第１の状態（s）と第２の状態（s’）であり且つ戻り値が当該第１の状態（s）から当該第２の状態（s’）の上記期待到達時間の上記方策パラメータθに関する感度である関数（期待到達時間感度関数）とを使用して導出されうる。
【０１９１】
また、更新処理実施部（２０５）は、上記に述べた推定手法１、推定手法２、そして上記に述べたステップ１及び２に従う方策パラメータθの更新を実施し、そして更新された方策パラメータθを方策（２０２）に反映させうる。
【０１９２】
特に、方策（２０２）及び更新処理実施部（２０５）とは、環境から獲得されたパラメータに基づき、あたかもＣＰＵ（１０２）が主体となって計算し更新していくように見なされるので、学習主体と呼ぶことにする。
【０１９３】
記憶装置（２１０）は、経験サンプル（２１１）、方策パラメータ（２１２）、及び学習主体によって使用されうる各種パラメータ（２１３）を格納しうる。経験サンプル（２１１）は、更新処理実施部（２０５）が上記推定手法１及び２を実施する上で使用されうる。方策パラメータ（２１２）については、上記で述べた通りである。各種パラメータ（２１３）は、例えば学習率αt、忘却率βt、統計量、及び状態量でありうるがこれらに制限されない。
【０１９４】
図３Ａは、学習の標準的な設定を示す模式図である。
学習主体（３０１）は、各時間ステップｔで、確率的方策に従って行動（３１１）を選択し、次状態st+1（３１２）と報酬rt（３１３）を受け取る。マルコフ決定過程では、状態数及び行動数は既知であるが、状態遷移確率及び報酬分布（又はコスト分布）は未知である（３０２）。学習問題、例えば強化学習問題として、マルコフ決定過程は、方策固定のもとでは、上記に述べた通り状態遷移確率をもつマルコフ連鎖とみなせる。
【０１９５】
図３Ｂは、環境の状態遷移を示す模式図である。
図３Ｂは、２状態２行動のマルコフ決定過程をモデル化した図である。図３Ｂにおける問題設定は、２つの選択肢、例えばキャンペーンを実施する又は実施しないがあり、その選択肢の変更に時間がかかるような一般的な状況をモデル化する。当該２状態２行動のマルコフ決定過程では、状態S1（３２１）からS2（３２２）への状態遷移若しくはその逆の状態遷移、又は、S1（３２１）からS1（３２１）への自己遷移若しくはS2（３２２）からS2（３２２）への自己遷移が示されている。
【０１９６】
上記例において、方策（意思決定モデル）は、下記式によって示される。
【０１９７】
【数４６】
2013242761.tif 000061
【０１９８】
上記問題設定では、初期方策に偏りがあると、簡単に、学習の停滞が発生するベンチマーク課題である（非特許文献３及び非特許文献９を参照）。
【０１９９】
図４Ａ及び図４Ｂは、本発明の実施態様に従う、方策パラメータθの更新を実現する処理のためのフローチャートを示す。この処理に係るプログラムは、予めＲＯＭ又はハードディスク・ドライブ（１０８）に格納され、メイン・メモリ（１０３）に実行可能なようにロードされうる。
【０２００】
図４Ａは、上記方策パラメータθの更新を実現する処理のためのフローチャートの全体図を示す。
ステップ４０１では、更新処理実施部（２０５）は本発明の実施態様に従う方策パラメータθの更新のための処理を開始する。
【０２０１】
ステップ４０２では、更新処理実施部（２０５）は、方策π(a|s;θ)をメモリ（１０３）内に呼び出す。方策π(a|s;θ)は例えば、ユーザによって事前に制御器（２０１）に与えられうる。ユーザは、方策π(a|s;θ)を決められうるものである。離散時間マルコフ決定過程では、当該方策はπ(a|s;θ)≡Pr(a|s;θ)で与えられうる。
【０２０２】
ステップ４０３では、更新処理実施部（２０５）は、推定手法をメモリ（１０３）内に呼び出す。推定手法は、上記した推定手法１及び／又は推定手法２である。更新処理実施部（２０５）がどの推定手法を使用するかは、例えば予めユーザによって指定されうる。また、更新処理実施部（２０５）は、方策π(a|s;θ)を初期化しうる。更新処理実施部（２０５）は、マルコフ決定過程が離散時間マルコフ決定過程である場合には、Pr(a|s;θ)を初期化しうる。
【０２０３】
また、更新処理実施部（２０５）は、推定手法１及び推定手法２において、並びに、方策パラメータθの更新手法において使用されうるパラメータ、そしてハイパーパラメータを初期化しうる。当該パラメータは、例えば、忘却率βt、学習率αt、及び統計量を包含しうる。
【０２０４】
忘却率βtは、忘却率βt∈[0,1]が適当に選ばれうる。忘却率βtとして、tに依存しない一定値を選んでもよい。
【０２０５】
学習率αt >0は、tに依存しない正の実数であってよい。
【０２０６】
統計量の初期化は、例えば統計量の計算に使用されるパラメータ、A, B, C, D, E, x, y, F, G, zを全て0にセットすることによって行われる。なお、ここでは、添え字を表示していないが、当該パラメータは例えばA0, B0, C0, ... , などと表しうる。
【０２０７】
また、更新処理実施部（２０５）は、従来技術である手法、例えば強化技法を用いて方策パラメータθの更新を併用する場合には、当該従来技術において使用されうるパラメータを初期化しうる。
【０２０８】
また、更新処理実施部（２０５）は、初期状態（s0）を決定しうる。
【０２０９】
ステップ４０４では、更新処理実施部（２０５）は、tを0にセットする。
【０２１０】
ステップ４０５では、更新処理実施部（２０５）は、t＞0であるかどうかを判断する。処理の最初の段階ではt := 0とセットされているので、ここの判断は否定的となり、更新処理実施部（２０５）はステップ４０７に進む。更新処理実施部（２０５）は、t＞0であることに応じて処理をステップ４０６に進める。更新処理実施部（２０５）は、t＞0でないことに応じて処理をステップ４０７に進める。ステップ４０５は、ｔがt＜0〜Tまで繰り返し、ステップ４０６〜４１１を行うことを意味する。
【０２１１】
ステップ４０６では、更新処理実施部（２０５）は、t＞0であることに応じて、観測器（２０４）が観測したφ(st)と即時報酬rt rt(st,at,st+1)を受け取る。当該φ(st)の観測は例えば、観測器（２０４）、例えば上記したセンサにより位置を検知することにより取得されたものでありうる。
【０２１２】
ステップ４０７では、更新処理実施部（２０５）は、t＞0でないことに応じて、更新処理実施部（２０５）は、観測器（２０４）が観測したφ(st)を受け取る。更新処理実施部（２０５）は、処理をステップ４１３に進める。
【０２１３】
ステップ４０８では、更新処理実施部（２０５）は、上記で述べた推定手法１及び２をそれぞれ単独で用いて、期待到達時間の推定値又は期待到達時間の偏微分の推定値を求めうる。代替的には、更新処理実施部（２０５）は、上記で述べた推定手法１及び２の両方を用いて、期待到達時間の推定値及び期待到達時間の偏微分の推定値を求めうる。
【０２１４】
ステップ４０９では、更新処理実施部（２０５）は、方策を更新する条件を満たすかどうかを判断する。方策を更新する条件としては、様々なものが考えられるが、例えば、適当に1より大きい整数mを定めて、mod(t,m)= 0であることを以って、方策更新条件を満たすとしうる。mod(t,m)は、tをmで割った余りを出力する関数である。なお、ステップ４０９は必須ではないが、ステップ４０９がないと、ステップ４１０での方策パラメータθの更新の実施が毎回行われることになる。ステップ４１０を毎回行うことは、コストの負担を増やし効率的でないことがある。従って、ステップ４０９を入れて、上記コストを減らすようにしうる。
【０２１５】
ステップ４１０では、更新処理実施部（２０５）は、方策を更新する条件を満たすことに応じて、本発明に従う上記した方策パラメータθの更新手法を使用して、方策パラメータθの更新を実施する。方策パラメータθの当該更新は、必ずしもステップ４０６〜４１１の繰り返しステップ毎に実施しなくてもよく、例えば上記繰り返しステップの１０ステップ毎に実施するようにしてもよい。
【０２１６】
また、更新処理実施部（２０５）は、本発明に従う上記した方策パラメータθの更新手法を使用する前又は後に、従来技術である方法、例えば強化学習法に従い、方策パラメータθを更新しうる。
【０２１７】
ステップ４１１では、更新処理実施部（２０５）は、学習終了条件を満たすかどうかを判断する。学習終了条件とは、例えば、tがある所与のステップ数Ｔを超えたかどうかである（t＜Ｔ）。あるいは、更新処理実施部（２０５）は、方策パラメータθの前回の値との変化量が、ある閾値以下になったことによって判定しうる。更新処理実施部（２０５）は、学習終了条件を満たすことに応じて、処理をステップ４１２に進めて、上記開始した処理を終了する。一方、更新処理実施部（２０５）は、学習終了条件を満たさないことに応じて、処理をステップ４１３に進める。
【０２１８】
ステップ４１２では、更新処理実施部（２０５）は、学習終了条件を満たすことに応じて方策を確定し、当該確定した方策π(a|s;θ)を方策（２０２）に戻す。そして、更新処理実施部（２０５）は、本発明の実施態様に従う方策パラメータθの更新のための上記処理を終了する。
【０２１９】
ステップ４１３では、下記が行われる。
（１）方策π(at|st;θ)に従い、行動atを決定する。
（２）環境に対して、行動atを実施する。行動atを実施は、例えば上記したアクチュエータを動作させて、ロボットを移動させることでありうる。
（３）行動atの結果として、新しい状態st+1に遷移する。
（４）tを1つ増分する。
【０２２０】
ステップ４１３を経由してステップ４０５に戻ると、最早再びt=0となることはないので、ステップ４０５からステップ４０７の経路に再び進むことはない。こうして、更新処理実施部（２０５）は、処理をステップ４０６に進める。
【０２２１】
図４Ｂは、図４に記載の方策パラメータθの更新を実施するステップの詳細を示すフローチャートを示す。
ステップ４２１では、更新処理実施部（２０５）は、方策を更新する条件を満たすことに応じて、本発明に従う上記した方策パラメータθの更新手法を使用して、方策パラメータθの更新を実施する処理を開始する。
【０２２２】
ステップ４２２では、更新処理実施部（２０５）は、ステップ４０８において推定手法１により得られた期待到達時時間の推定値から選択された状態対、又は、推定手法１により得られた期待到達時時間の推定値が最大である状態対、を探索する。
【０２２３】
ステップ４２３では、更新処理実施部（２０５）は、ステップ４０８において推定手法２により得られた偏微分の推定値を用いて方策パラメータθを更新する。
【０２２４】
ステップ４２４では、更新処理実施部（２０５）は、方策パラメータθの更新を実施する上記処理を終了して、処理をステップ４１１に進める。
【０２２５】
図５は、２つの選択肢のある環境をモデル化したマルコフ決定過程（図３Ｂを参照）において、本発明の実施態様及び従来方法に従い方策パラメータθを更新した場合の経時的な平均報酬についてのシミュレーション結果を示すグラフである。
【０２２６】
当該グラフは、横軸が学習試行回数を示し、縦軸が１００回試行分の平均報酬を表している。また、エラーバーは、１００回試行の標準を示す。
【０２２７】
初期方策は、下記の通りである。
【０２２８】
【数４７】
2013242761.tif 000062
【０２２９】
試験１（５１１）は、本発明の実施態様に従うオプション３を使用して、方策パラメータθを更新した場合である。
試験２（５１２）は、本発明の実施態様に従うオプション４を使用して、方策パラメータθを更新した場合である。
試験３（５１３）は、従来技術である方策勾配法（非特許文献１及び非特許文献２を参照）を使用して、方策パラメータθを更新した場合である。
試験４（５１４）は、従来技術である自然方策勾配法（非特許文献３及び非特許文献４を参照）を使用して、方策パラメータθを更新した場合である。
【０２３０】
結果は、次の通りである。試験１では、学習試行回数の早い時期から高い平均報酬を示した。試験２では、学習試行が開始するとすぐに高い平均報酬を示した。試験３では、学習試行回数がある程度増えることによって高い平均報酬を示した。一方、試験４では、学習試行の開始から学習試行回数が増えた場合であっても、平均報酬がほとんど変わらなかった。従って、学習率の成績は、試験２（５１２）＞試験１（５１１）＞試験３（５１３）＞試験４（５１４）の順である。
【０２３１】
従って、本発明の実施態様に従い方策パラメータθを更新した場合（すなわち、試験１及び２）において、従来法（すなわち試験３及び４）に比べて、パフォーマンスが優れていることが確認された。従って、本発明の実施態様に従い方策パラメータθを更新した場合に、従来法と比べて効率良く、本結果において１０倍以上の効率で学習が可能となっていた。
【０２３２】
図６は、２つの選択肢のある環境を一般化したマルコフ決定過程設定において、本発明の実施態様及び従来方法に従い方策パラメータθを更新した場合の初期値依存性について網羅的に調査した結果を示すグラフである。
【０２３３】
当該グラフは、ｘ軸が初期方策パラメータθ１を示し、ｙ軸が初期方策パラメータθ２を示し、ｚ軸は成功率を示す。
【０２３４】
初期方策は、下記の通りである。
【０２３５】
【数４８】
2013242761.tif 000063
【０２３６】
試験では、一定時間以内に平均報酬が最適値（＝２）の９９％（１．９８）以上になる確率を調べた。
【０２３７】
試験１（６０１）は、本発明の実施態様に従うオプション３を使用して、方策パラメータθを更新した場合である。
試験２（６０２）は、本発明の実施態様に従うオプション４を使用して、方策パラメータθを更新した場合である。
試験３（６０３）は、従来技術である方策勾配法（非特許文献１及び非特許文献２を参照）を使用して、方策パラメータθを更新した場合である。
試験４（６０４）は、従来技術である自然方策勾配法（非特許文献３及び非特許文献４を参照）を使用して、方策パラメータθを更新した場合である。
【０２３８】
その結果、特に試験２では、初期値依存性が、従来法（すなわち試験３及び４）と比べて圧倒的に解消できることが確認された。また、試験１においでも、初期値依存性が、従来法（試験３及び４）と比べて解消できることが確認された。従って、本発明の実施態様に従い方策パラメータθを更新した場合に、従来法と比べて初期依存性を減らし、最適方策をほぼ常に発見できることが示された。
【図１】
2013242761.tif 000079
【図２】
2013242761.tif 000080
【図３Ａ】
2013242761.tif 000081
【図３Ｂ】
2013242761.tif 000082
【図４Ａ】
2013242761.tif 000083
【図４Ｂ】
2013242761.tif 000084
【図５】
2013242761.tif 000085
【図６】
2013242761.tif 000086