(57)【特許請求の範囲】
【請求項１】
対象とするシステムの時間発展がマルコフ過程として記述される際に、前記システムの状態に対する制御則である方策を前記システムの状態量の観測により学習する制御器であって、
前記方策に基づいて、前記システムを制御するための制御信号を生成する制御信号生成手段と、
前記システムの前記状態量を観測する状態量検知手段と、
前記状態量により特定される状態と制御信号値の同時分布のフィッシャー情報行列をリーマン計量行列とする、平均報酬の自然勾配である自然定常方策勾配を推定する自然定常方策勾配推定手段と、
前記方策勾配推定手段による推定結果とに基づいて、前記方策を規定する方策パラメータを更新することで、前記方策を更新する方策更新手段とを備える、制御器。
【請求項２】
前記自然定常方策勾配推定手段は、
前記状態と前記制御信号とに予め定められた関係で依存する報酬値を獲得する報酬値獲得手段と、
各タイムステップにおける前記状態量と前記制御信号とに基づいて、定常分布の対数の偏微分を推定し、推定された偏微分により特定される状態と制御信号との基底関数を規定とする線形関数近似器により前記報酬値を回帰することで、前記自然定常方策勾配を推定する推定手段とを含む、請求項１記載の制御器。
【請求項３】
対象とするシステムの時間発展がマルコフ過程として記述される際に、前記システムの状態に対する制御則である方策を前記システムの状態量の観測により学習する制御方法であって、
前記方策に基づいて、前記システムを制御するための制御信号を生成する制御信号生成ステップと、
前記システムの前記状態量を観測する状態量検知ステップと、
前記状態量により特定される状態と制御信号値の同時分布のフィッシャー情報行列をリーマン計量行列とする、平均報酬の自然勾配である自然定常方策勾配を推定する自然定常方策勾配推定ステップと、
前記方策勾配推定ステップによる推定結果とに基づいて、前記方策を規定する方策パラメータを更新することで、前記方策を更新する方策更新ステップとを備える、制御方法。
【請求項４】
対象とするシステムの時間発展がマルコフ過程として記述される際に、前記システムの状態に対する制御則である方策を前記システムの状態量の観測により学習する制御方法をコンピュータに実行させるためのプログラムであって、
前記方策に基づいて、前記システムを制御するための制御信号を生成する制御信号生成ステップと、
前記システムの前記状態量を観測する状態量検知ステップと、
前記状態量により特定される状態と制御信号値の同時分布のフィッシャー情報行列をリーマン計量行列とする、平均報酬の自然勾配である自然定常方策勾配を推定する自然定常方策勾配推定ステップと、
前記方策勾配推定ステップによる推定結果とに基づいて、前記方策を規定する方策パラメータを更新することで、前記方策を更新する方策更新ステップとを含む、制御処理をコンピュータに実行させるための制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、方策勾配法により制御対象を制御する制御器、制御方法および制御プログラムの構成に関する。
【背景技術】
【０００２】
「マルコフ決定過程」として定式化される制御問題は、ロボット、プラント、移動機械（電車、自動車）などの自律的制御問題として、幅広い応用を持つ重要な技術である。
【０００３】
マルコフ決定過程に対する最適制御に関する従来技術として、いわゆる「強化学習」がある。
【０００４】
「強化学習」とは、エージェントが環境と相互作用を通じて試行錯誤し、得られる累積報酬量を最大化するような「方策」と呼ばれる行動則、すなわち、制御問題に用いる場合には、「制御規則」を学習する理論的な枠組みである。この学習法は、環境やエージェント自身に関する先験的な知識をほとんど必要としない点で様々な分野から注目を集めている。
【０００５】
強化学習は大まかに２つに分類できる。価値関数を用いて間接的に方策を表現し、価値関数を更新することで方策も更新される「価値関数更新法」と、方策を明示的にもち目的関数の勾配に従って方策を更新する「直接方策更新法（方策勾配法）」である。
【０００６】
方策勾配法は、行動のランダム性を制御するパラメータも方策パラメータに含めることで確率的方策の獲得が可能であり、また連続系への適用性も高いため、特に注目を集めている。しかし一般に実タスクへ適用すると、適切な行動則を獲得するまでの時間が非現実となることがある。そこで、複数学習器の同時利用、モデルの利用、教示信号の利用等の補助機構を入れて学習時間を短縮させる研究が活発に行われ、成果も著しい。
【０００７】
ここで、方策勾配強化学習法（ＰＧＲＬ）は、方策パラメータについての平均報酬の偏微分を用いることにより、方策パラメータを改善して平均報酬を最大化するための強化学習（ＲＬ：Reinforcement Learning）の一般的なアルゴリズムである。ここで、平均報酬の偏微分は、方策勾配（ＰＧ：Policy Gradient）と呼ばれる。
【０００８】
すなわち、方策勾配強化学習法は、エージェントが環境と相互作用する際に得られる報酬の時間平均値を目的関数とし、この目的関数を局所最大化する方策（行動則）の獲得を目指した方策探索法で、方策パラメータを目的関数の勾配により逐次更新することで実現される。
【０００９】
方策さえ適切にパラメータ化すれば、エージェントや環境に関する知識を必要とせずマルコフ決定過程(MDP： Markov Decision Process）に実装可能である。また行動のランダム性を制御するパラメータも方策パラメータに含めることで確率的な方策の獲得も可能なため、履歴を要しない方策族の中で最適なものが確率的になる場合がある部分観測マルコフ決定過程（POMDP： Partially Observable MDP）に対しても、パラメータ化された方策をその表現可能な範囲で最適化することができる[非特許文献3]〜[非特許文献7]。
【００１０】
一方で、課題によっては良い方策を獲得するまでの時間が膨大になる問題がある。そのため副報酬の導入[非特許文献8]、モデルの利用[非特許文献9] や教示信号の利用[非特許文献10] 等の補助機構による学習時間の短縮を目指した研究は行われているが、一般に特定の課題を想定しており、課題についての事前知識を必要とするため汎用性に乏しい。よって標準的な強化学習の枠組みに手を加えない、つまり課題に依存しないような方策勾配アルゴリズムの改良が望まれる。
【００１１】
なお、以下、本文中で引用することとなる方策勾配学習法に関連した先行技術文献を以下に挙げる。
【非特許文献１】S. Amari: “Natural gradient works efficiently in learning”, Neural Computation, 10, 2, pp. 251-276 (1998).
【非特許文献２】S. Kakade: “A natural policy gradient”, Advances in NeuralInformation Processing Systems, Vol. 14, MIT Press (2002).
【非特許文献３】R. J. Williams: “Simple statistical gradient-following algorithms for connectionist reinforcement learning”, Machine Learning, 8, pp. 229-256 (1992).
【非特許文献４】D. P. Bertsekas and J. N. Tsitsiklis: “Neuro-Dynamic Programming”, Athena Scientific (1996).
【非特許文献５】H. Kimura and S. Kobayashi: “An analysis of actor/critic algorithms using eligibility traces: Reinforcement learning with imperfect value function”,International Conference on Machine Learning, pp.278-286 (1998).
【非特許文献６】J. Baxter and P. Bartlett: “Infinite-horizon policygradientestimation”, Journal of Artificial Intelligence Research, 15, pp. 319-350 (2001).
【非特許文献７】J. Baxter, P. Bartlett and L. Weaver: “Experiments with infinite-horizon policy-gradient estimation”, Journal of Artificial Intelligence Research, 15, pp. 351-381 (2001).
【非特許文献８】A. Y. Ng, D. Harada and S. Russell: “Policy invariance under reward transformations: theory and application to reward shaping”, International Conference on Machine Learning, pp. 278-287 (1999).
【非特許文献９】D. Bagnell, S. Kakade, A. Ng and J. Schneider: “Policy search by dynamic programming”, Advances of Neural Information Processing Systems (2004).
【非特許文献１０】M. T. Ronsenstein and A. G. Barto: “Supervised actor-critic reinforcement learning”, Learning and Approximate Dynamic Programming: Scaling Up to the Real World, John Wiley & Sons, Inc., pp. 359-380 (2004).
【非特許文献１１】K. F. S. Amari: “Local minima and plateaus in hierarchical structures of multilayer perceptrons”, Neural Networks, 13, 3, pp. 317-327 (2000).
【非特許文献１２】S. Amari, A. Cichocki and H. H. Yang: “A new learning algorithm for blind signal separation”, Advances in Neural Information Processing Systems, Vol. 8, MIT Press (1996).
【非特許文献１３】D. MacKay: “Maximum likelihood and covariant algorithms for independent component analysis”, Technical report, University of Cambridge (1999).
【非特許文献１４】S. Amari, H. Park and K. Fukumizu: “Adaptive method of realizing natural gradient learning for multilayer perceptrons”, Neural Computation, 12, 6, pp. 1399-1409 (2000).
【非特許文献１５】J. Peters, S. Vijayakumar and S. Schaal: “Reinforcement learning for humanoid robotics”, IEEE-RAS International Conference on Humanoid Robots (2003).
【非特許文献１６】D. Bagnell and J. Schneider: “Covariant policy search”, Proceedings of the International Joint Conference on Artificial Intelligence (2003).
【非特許文献１７】J. Peters, S. Vijayakumar and S. Schaal: “Natural actor-critic”, European Conference on Machine Learning (2005).
【非特許文献１８】Y. Nakamura, T. Mori and S. Ishii: “Natural policy gradient reinforcement learning for a CPG control of a biped robot”, International conference on parallel problem solving from nature, pp. 972-981 (2004).
【非特許文献１９】T. Morimura, E. Uchibe and K. Doya: “Utilizing natural gradient in temporal difference reinforcement learning with eligibility traces”, International Symposium on Information Geometry and its Applications (2005).
【非特許文献２０】S. Richter, D. Aberdeen and J. Yu: “Natural actorcritic for road traffic optimisation”, Advances in Neural Information Processing Systems, MIT Press (2007).
【非特許文献２１】D. P. Bertsekas: “Dynamic Programming and Optimal Control, Volumes 1 and 2”, Athena Scientific (1995).
【非特許文献２２】R. S. Sutton and A. G. Barto: “Reinforcement Learning”, MIT Press (1998).
【非特許文献２３】R. S. Sutton, D. McAllester, S. Singh and Y. Mansour:“Policy gradient methods for reinforcement learning with function approximation”, Advances in Neural Information Processing Systems, Vol. 12, MIT Press (2000).
【非特許文献２４】S. Amari and H. Nagaoka: “Method of Information Geometry”, Oxford University Press (2000).
【非特許文献２５】R. Fletcher: “Practical Methods of Optimization”, Wiley (1987).
【非特許文献２６】T. Morimura, E. Uchibe, J. Yoshimoto and K. Doya:“Reinforcement learning with log stationary distribution gradient”, Technical report, Nara Institute of Science and Technology (2007).
【非特許文献２７】C. M. Bishop: “Neural Networks for Pattern Recognition”, Oxford University Press (1995).
【非特許文献２８】福水, 栗木, 竹内, 赤平：“特異モデルの統計学”, 岩波書店
【非特許文献２９】M. Rattray and D. Saad: “Analysis of natural gradient descent for multilayer neural networks”, Physical Review E, 59, 4, pp. 4523-4532 (1999).
【非特許文献３０】S. J. Bradtke and A. G. Barto. Linear least-squares algorithms for temporal difference learning. Machine Learning, 22(1-3):33-57, 1996.
【非特許文献３１】J. A. Boyan. Least-squares temporal difference learning. Machine Learning, 49(2-3):233-246, 2002.
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかしながら、最適方策への収束を遅くしている理由を学習すべきパラメータ空間の構造の性質から考察した場合に、これをいかにして改善するべきかについては、従来、明らかではなかった。
【００１３】
では、何が学習時間を膨大にしているのだろうか。もちろん課題が複雑になれば一般に方策パラメータの探索空間は膨大になり学習は困難になるが、それ以外にMDP の確率分布に対して各方策パラメータの敏感さの相違やその相関を無視している問題がある。つまりパラメータを座標系とするMDP で表現可能な確率分布の集合はユークリッド空間ではなくリーマン多様体となるが、従来の勾配法によるパラメータ更新方向（偏微分）はリーマン空間における最急勾配方向とは異なり学習が停滞してしまう問題である。実際に２状態MDPのような極めて単純なモデルであっても深刻なプラトー（学習の停滞期間）に陥ることが報告されている[非特許文献2]。これはパラメータを座標系とする目的関数の幾何構造が局所的に平坦になっている部分があり、そこでは勾配が極端に小さくなるからである[非特許文献11]。
【００１４】
この解決法としてリーマン空間上の最急勾配法である“自然勾配法” が知られている[非特許文献1]。これは他の機械学習分野ではよく研究されているが[非特許文献1]、 [非特許文献12]〜[非特許文献14]、強化学習についての理論的な研究はあまり進んでいない[非特許文献2]、 [非特許文献15]〜[非特許文献17]。
【００１５】
特に自然勾配法ではどのリーマン計量行列を用いるかで勾配方向が異なるため、リーマン計量の設計は大切な問題である。
【００１６】
しかしながら自然勾配の強化学習への適用[非特許文献15]〜[非特許文献20] は全てKakade [非特許文献2] の提案した行動の確率分布に関するリーマン計量が用いられており、他のリーマン計量ついては議論も提案もされていなかった。
【００１７】
そこで本発明では、方策パラメータに関する状態と行動の同時分布に関する新しいリーマン計量を提案し、そのリーマン計量における平均報酬の自然勾配による新しい自然方策勾配法である自然定常方策勾配法（NSG:National Stationarypolicy Gradient）を提案する。
【００１８】
したがって、本発明は、上記のような問題点を解決するためになされたものであって、その目的は、学習のプラトーの発生を回避して試行回数（学習時間）を減少させることが可能な自然勾配を用いた強化学習に基づく、制御器、制御方法、制御プログラムを提供することである。
【課題を解決するための手段】
【００１９】
以下の説明で明らかとなるように、我々が提案するリーマン計量は、Kakade のリーマン計量や平均報酬のヘッセ行列と比較して妥当性なものである。さらに、我々が提案する自然勾配は方策パラメータにより規定される基底関数の線形結合によって即時報酬を最小二乗近似した際の線形結合係数に一致する。
【００２０】
このような目的を達成するために、本発明の制御器は、対象とするシステムの時間発展がマルコフ過程として記述される際に、システムの状態に対する制御則である方策をシステムの状態量の観測により学習する制御器であって、方策に基づいて、システムを制御するための制御信号を生成する制御信号生成手段と、システムの状態量を観測する状態量検知手段と、状態量により特定される状態と制御信号値の同時分布のフィッシャー情報行列をリーマン計量行列とする、平均報酬の自然勾配である自然定常方策勾配を推定する自然定常方策勾配推定手段と、自然定常方策勾配推定手段による推定結果とに基づいて、方策を規定する方策パラメータを更新することで、方策を更新する方策更新手段とを備える。
【００２１】
好ましくは、自然定常方策勾配推定手段は、状態と制御信号とに予め定められた関係で依存する報酬値を獲得する報酬値獲得手段と、各タイムステップにおける状態量と制御信号とに基づいて、定常分布の対数の偏微分を推定し、推定された偏微分により特定される状態と制御信号との基底関数を規定とする線形関数近似器により報酬値を回帰することで、自然定常方策勾配を推定する推定手段とを含む。
【００２２】
この発明の他の局面に従うと、対象とするシステムの時間発展がマルコフ過程として記述される際に、システムの状態に対する制御則である方策をシステムの状態量の観測により学習する制御方法であって、方策に基づいて、システムを制御するための制御信号を生成する制御信号生成ステップと、システムの状態量を観測する状態量検知ステップと、状態量により特定される状態と制御信号値の同時分布のフィッシャー情報行列をリーマン計量行列とする、平均報酬の自然勾配である自然定常方策勾配を推定する自然定常方策勾配推定ステップと、自然定常方策勾配推定ステップによる推定結果とに基づいて、方策を規定する方策パラメータを更新することで、方策を更新する方策更新ステップとを備える。
【００２３】
この発明のさらに他の局面に従うと、対象とするシステムの時間発展がマルコフ過程として記述される際に、システムの状態に対する制御則である方策をシステムの状態量の観測により学習する制御方法をコンピュータに実行させるためのプログラムであって、方策に基づいて、システムを制御するための制御信号を生成する制御信号生成ステップと、システムの状態量を観測する状態量検知ステップと、状態量により特定される状態と制御信号値の同時分布のフィッシャー情報行列をリーマン計量行列とする、平均報酬の自然勾配である自然定常方策勾配を推定する自然定常方策勾配推定ステップと、自然定常方策勾配推定ステップによる推定結果とに基づいて、方策を規定する方策パラメータを更新することで、方策を更新する方策更新ステップとを含む、制御処理をコンピュータに実行させる。
【発明を実施するための最良の形態】
【００２４】
（本発明の内容のあらまし）
一般に統計モデルや機械学習のパラメータの空間は、その出力の変化に関してユークリッドではなくリーマン空間としての性質を持ち、その最急勾配方向は従来の勾配である出力の偏微分と必ずしも一致しない。
【００２５】
この問題に対してAmari [非特許文献1] は自然勾配法を提案し、Kakade [非特許文献2] がマルコフ決定過程の最適化手法の一つである方策勾配強化学習法に自然勾配を適用した。
【００２６】
自然勾配方向はリーマン構造を規定するリーマン計量のもと定まるので、その選択は重要な問題となる。しかしながら、Kakade の用いたリーマン計量行列は方策のパラメータ摂動による行動の確率分布変化だけを考慮した計量行列であり、同様に方策の影響を受けるはずの状態の確率分布変化に関しては無視していた。そこで本発明では、状態の確率分布も考慮した新しいリーマン計量を提案し、その計量に基づく新しい自然方策勾配、自然定常方策勾配を導出する。さらに、この自然定常方策勾配は方策パラメータにより規定される基底関数をもつ線形関数近似器で即時報酬を近似した際に学習されるパラメータに一致することを証明する。また様々な状態数のマルコフ決定問題に適用した数値実験より、特に状態数が多い場合に従来法に比べ提案法は有効に働くことを示す。
【００２７】
以下の説明の構成の概要を説明すると、（１．本発明の概要）において、本発明の全体的な構成を説明し、2．1 節にて強化学習における勾配法である方策勾配法を解説する。2．2 節ではAmari [非特許文献1] によって提案された自然勾配法を解説し、その強化学習への適用である自然方策勾配法を紹介して、2．3 節にてその疑問点を指摘する。
【００２８】
（１．本発明の概要）
後に説明するように、本発明では、「自然定常方策勾配」を導出して「方策」を更新し、制御対象の制御を行う。ここで、この自然定常方策勾配の導出にあたっては、後に説明するように、逆方向マルコフ連鎖の方法とＴＤ（temporal difference）学習アルゴリズムにより、定常分布の勾配としてのＬＳＤＧ（定常分布の対数の偏微分−ＬＳＤＧ(LogStationary Distribution Gradients））が導出され、これを用いることができる。
【００２９】
以下、図面を参照して本発明の実施の形態について説明する。
以下の説明で明らかとなるとおり、本発明は、ロボット、プラント、移動機械（電車、自動車）などの制御問題として、幅広い応用を持つ。
【００３０】
ただし、以下では、本発明の具体的な適用例として、特に簡単なロボットの自動制御問題を対象とするものとして説明を行う。また、数値計算の結果は、さらに簡単なモデルに対する比較を示している。しかしながら、本発明は、このような応用に限定されるものではなく、より一般的に、対象システムの時間発展が複雑な場合の対象システムの制御に適用することができる。そのようなものの例としては、巨大プラント（溶鉱炉、原子力プラント）、マルチリンクロボット（ヒューマノイドロボット）、ノンホロノームシステム（宇宙ステーション）、地下鉄ホームでの人の流れなどがある。これらは、いずれも古典的制御法での制御が困難であり、かつ重要な制御対象である。
【００３１】
（２．本発明のシステム構成）
図１は、本発明の制御方法および制御プログラムが適用される制御器を用いたシステム１０００の一例を示す概念図である。
【００３２】
図１を参照して、システム１０００は、制御対象となる被制御装置２００と、この被制御装置２００に対して制御信号を与えるためのコンピュータ１００とを備える。
【００３３】
図１を参照してこのコンピュータ１００は、ＣＤ−ＲＯＭ（Compact Disc Read-Only Memory ）上の情報を読込むためのＣＤ−ＲＯＭドライブ１０８およびフレキシブルディスク（Flexible Disk、以下ＦＤ）１１６に情報を読み書きするためのＦＤドライブ１０６を備えたコンピュータ本体１０２と、コンピュータ本体１０２に接続された表示装置としてのディスプレイ１０４と、同じくコンピュータ本体１０２に接続された入力装置としてのキーボード１１０およびマウス１１２とを含む。
【００３４】
図２は、このコンピュータ１００の構成をブロック図形式で示す図である。
図２に示されるように、このコンピュータ１００を構成するコンピュータ本体１０２は、ＣＤ−ＲＯＭドライブ１０８およびＦＤドライブ１０６に加えて、それぞれバスＢＳに接続されたＣＰＵ（Central Processing Unit ）１２０と、ＲＯＭ（Read Only Memory) およびＲＡＭ （Random Access Memory）を含むメモリ１２２と、直接アクセスメモリ装置、たとえば、ハードディスク１２４と、被制御装置２００とデータの授受を行うための通信インタフェース１２８とを含んでいる。ＣＤ−ＲＯＭドライブ１０８にはＣＤ−ＲＯＭ１１８が装着される。ＦＤドライブ１０６にはＦＤ１１６が装着される。
【００３５】
被制御装置２００からは、コンピュータ１００に対して被制御装置２００の状態を示すパラメータ（状態量）の情報、たとえば、被制御装置２００の可動部分の位置、速度、加速度、角度、角速度等の情報が与えられる。一方、コンピュータ１００からは、被制御装置２００に対して、これら状態量を制御するための制御情報が制御信号（以下に説明する「行動」に対応）として与えられる。
【００３６】
なお、ＣＤ−ＲＯＭ１１８は、コンピュータ本体に対してインストールされるプログラム等の情報を記録可能な媒体であれば、他の媒体、たとえば、ＤＶＤ−ＲＯＭ（Digital Versatile Disc）やメモリカードなどでもよく、その場合は、コンピュータ本体１０２には、これらの媒体を読取ることが可能なドライブ装置が設けられる。
【００３７】
本発明の制御器の主要部は、コンピュータハードウェアと、ＣＰＵ１２０により実行されるソフトウェアとにより構成される。一般的にこうしたソフトウェアはＣＤ−ＲＯＭ１１８、ＦＤ１１６等の記憶媒体に格納されて流通し、ＣＤ−ＲＯＭドライブ１０８またはＦＤドライブ１０６等により記憶媒体から読取られてハードディスク１２４に一旦格納される。または、当該装置がネットワークに接続されている場合には、ネットワーク上のサーバから一旦ハードディスク１２４にコピーされる。そうしてさらにハードディスク１２４からメモリ１２２中のＲＡＭに読出されてＣＰＵ１２０により実行される。なお、ネットワーク接続されている場合には、ハードディスク１２４に格納することなくＲＡＭに直接ロードして実行するようにしてもよい。
【００３８】
図１および図２に示したコンピュータのハードウェア自体およびその動作原理は一般的なものである。したがって、本発明の最も本質的な部分は、ＦＤ１１６、ＣＤ−ＲＯＭ１１８、ハードディスク１２４等の記憶媒体に記憶されたソフトウェアである。
【００３９】
なお、一般的傾向として、コンピュータのオペレーティングシステムの一部として様々なプログラムモジュールを用意しておき、アプリケーションプログラムはこれらモジュールを所定の配列で必要な時に呼び出して処理を進める方式が一般的である。そうした場合、当該制御器を実現するためのソフトウェア自体にはそうしたモジュールは含まれず、当該コンピュータでオペレーティングシステムと協働してはじめて制御器が実現することになる。しかし、一般的なプラットフォームを使用する限り、そうしたモジュールを含ませたソフトウェアを流通させる必要はなく、それらモジュールを含まないソフトウェア自体およびそれらソフトウェアを記録した記録媒体（およびそれらソフトウェアがネットワーク上を流通する場合のデータ信号）が実施の形態を構成すると考えることができる。
【００４０】
［制御方法の一般的説明］
以下、本発明の構成について、その理論的な構成を説明する。なお、数式において細字はスカラーであり、太字で表される変数は、ベクトル（または行列）を表す。ただし、本文中では、太字と細字を区別していない点を予め断っておく。
（2． 1 方策勾配強化学習）
強化学習問題として、有限状態集合S∋sと有限行動集合A∋a の上で定義される離散時間マルコフ決定過程(MDP) を考える[非特許文献21]、 [非特許文献22]。
【００４１】
各時間ステップt で、エージェントは方策パラメータθ∈Ｒdによって規定される以下の確率的方策に従い行動atを選択する。
【００４２】
【数１】
0005150371.tif 000002
【００４３】
その上で、以下の状態遷移確率に従って新しい状態st+1に遷移し、有界な予め定められた報酬関数r(st, at, st+1) により定まる即時報酬rt+1 を獲得する。ここでは、常に方策π（a|s;θ）はパラメータθに関して滑らかであり、状態遷移確率と方策により規定される以下のマルコフ連鎖はエルゴード性を満足していると仮定する。
【００４４】
【数２】
0005150371.tif 000003
【００４５】
よって方策パラメータを定めれば初期状態s0 に依存しない、以下のような唯一の(状態の) 定常分布ｄ（下付θ）が存在し、さらには、以下で定義されるように極限分布と一致する：
【００４６】
【数３】
0005150371.tif 000004
【００４７】
強化学習（方策探索）の目的は、即時報酬の時間平均である、以下の式（３）で表される平均報酬を最大にする方策パラメータθ＊を同定することである。
【００４８】
【数４】
0005150371.tif 000005
【００４９】
ここでE｛…｝は期待値を表しており、エルゴード性の仮定から右辺は初期状態s0に依存しない値となることに注意する。また時間平均と空間平均は一致（式(2)）するので、平均報酬は以下の式（４）のように書き直すことができる[非特許文献21]：
【００５０】
【数５】
0005150371.tif 000006
【００５１】
したがって、方策パラメータに関する平均報酬の勾配は、以下の式（５）のように表現できる。
【００５２】
【数６】
0005150371.tif 000007
【００５３】
となる。ただしaTはあるベクトルa の転置を表す。
よって、方策パラメータを下式より更新すれば目的関数である平均報酬R（θ）は増加する：
【００５４】
【数７】
0005150371.tif 000008
【００５５】
ここで、上式で左辺と右辺をつなぐ記号は、左辺の変数に右辺の値を代入する演算子を表しており、ηは学習率とよばれ十分に小さな定数である。以上の枠組みは、一般に方策勾配（強化学習）法と呼ばれる[非特許文献6]、[非特許文献23]。
（2．2 自然勾配[非特許文献1]）
あるパラメータ空間がリーマン空間であるとは、パラメータθ∈Ｒdがリーマン計量行列G（θ）∈Ｒdｘd (正定値行列) で規定されるリーマン多様体上にあることをいう。すなわち、パラメータθとθを微少変動をさせてできるベクトル(θ+ dθ) との二乗距離が、以下の式で定義されることを意味する。
【００５６】
【数８】
0005150371.tif 000009
【００５７】
ここで、ｇi,jとは行列Gの（i, j）番目の要素のことである。
十分に小さい正の定数をεとして移動距離｜ｄθ｜＝εの拘束下で関数R（θ）を最大にするdθの方向、つまりリーマン空間における最急勾配方向は、以下の式（６）のようになり、「自然勾配」と呼ばれる。
【００５８】
【数９】
0005150371.tif 000010
【００５９】
特に、強化学習においては、つまりθが方策パラメータでR（θ）が平均報酬である場合は、自然方策勾配と呼ばれる[非特許文献2]。
【００６０】
そして、自然（方策）勾配法では、以下の式（７）に従ってパラメータを逐次的に更新することで目的関数の（局所）最大化を行う。
【００６１】
【数１０】
0005150371.tif 000011
【００６２】
ある変数x の出現確率があるパラメータθで規定される統計モデルPr(ｘ｜θ)を考える場合には、一般にリーマン計量行列G(θ）として、以下の式（８）のフィッシャー情報行列Fx（θ）がよく用いられる: 
【００６３】
【数１１】
0005150371.tif 000012
【００６４】
その理由としてフィッシャー情報行列は確率分布間の擬距離を表すKullback-Leibler(KL) ダイバージェンスの局所近似と対応付けられるからである。すなわち、2 つの確率分布Pr(ｘ｜θ)とPr(ｘ｜θ＋Δθ)のKL ダイバージェンスは以下のように表せるからである[非特許文献24]。
【００６５】
【数１２】
0005150371.tif 000013
【００６６】
（2．3 自然方策勾配法の疑問点）
方策勾配強化学習法は、確率的方策π（a|s;θ）と状態遷移確率P(s'|s,a)により規定される統計モデル上で方策パラメータθの最適化をしているとみなせるので、その統計モデルのフィッシャー情報行列をもとにリーマン計量行列Ｇ（θ）を設計すれば、式（６）より自然方策勾配は自然に導出される。そして自然方策勾配法は任意にパラメータ化される方策のパラメータ空間ではなくてリーマン計量行列Ｇ（θ）で規定されるリーマン空間における勾配法であるため、強化学習問題におけるリーマン計量を設計できれば自然方策勾配は非常に有効な手法となる。
【００６７】
しかしKakade [非特許文献2] も指摘しているように強化学習におけるリーマン計量は
必ずしも一つには定まらず様々なものが考えられ、そして式（６）より明らかに自然方策勾配方向は、用いるリーマン計量行列Ｇ（θ）に依存する。
【００６８】
そのため適切なリーマン計量は何かという問題について議論しておくべきである。しかしながら、これまでの自然方策勾配に関する研究[非特許文献15]〜[非特許文献20] ではその点には触れず、Kakade [非特許文献2] の提案した行動分布のフィッシャー情報に関するリーマン計量行列が用いられていた。つまり、方策勾配強化学習法に関してどういった統計モデルが考えられ、どのリーマン計量が強化学習問題を解くのに有効なのかという議論はこれまであまりされてこなかった。そこで、本発明では強化学習における統計モデル及びリーマン計量について議論し、新しいリーマン計量を提案する。
（3． 方策勾配におけるリーマン計量行列）
3． 1 節で強化学習における新しいリーマン計量行列を提案し、3． 2 と3． 3 節ではこのリーマン計量をKakade [非特許文献2] が提案したリーマン計量や平均報酬のヘッセ行列と比較し、その妥当性を議論する。
（3． 1 状態行動に関する提案リーマン計量行列と提案自然定常方策勾配）
強化学習で直接調整できる関数は方策π（a|s;θ）であるため、これまでの自然方策勾配の研究は方策関数にのみ、つまり統計モデルPr(a|s,Ｍ（θ）)に着目したものであった。しかしながら、実際は方策が変われば状態の分布Pr(s|Ｍ（θ）)も変わる。そして式（４）より、平均報酬R（θ）は状態行動(s,a)∈Ｓ×Ａの同時分布より規定されるので、強化学習の目的である平均報酬の（局所）最大化において注目すべき統計モデルはPr(s,a|Ｍ（θ）)が妥当であると考えられる。
【００６９】
何故なら、もしPr(s,a|Ｍ（θ）)のフィッシャー情報行列をリーマン計量行列として用いれば、その自然方策勾配は、方策パラメータθに関する状態行動同時分布における、以下のKL ダイバージェンスＤKLの微小変化一定という拘束下での平均報酬の最急勾配方向と一致するからである。
【００７０】
【数１３】
0005150371.tif 000014
【００７１】
この統計モデルに対応するフィッシャー情報行列Fs,a（θ）は、式（８）を用いて次の式（９）のように求まる：
【００７２】
【数１４】
0005150371.tif 000015
【００７３】
そして状態行動の同時分布によるフィッシャー情報行列Fs,a（θ）をリーマン計量行列Ｇ（θ）とする提案する自然方策勾配である自然定常方策勾配（NSG:National Stationarypolicy Gradient）は式（６）より次式で求まる：
【００７４】
【数１５】
0005150371.tif 000016
【００７５】
（3． 2 従来リーマン計量行列との比較）
これまで自然方策勾配に用いられた唯一のリーマン計量行列は、Kakade [非特許文献2] がアドホックに提案した行列であり、方策のフィッシャー情報行列Fa（s,θ）を定常分布で重み付けして積算した以下の式（１２）であった。
【００７６】
【数１６】
0005150371.tif 000017
【００７７】
これはFs,a（θ）の式（９）の第二項そのものである。方策パラメータの変化により定常分布が変化しないという仮定をおけば、式（１０）において、以下の関係がなりたつ。
【００７８】
【数１７】
0005150371.tif 000018
【００７９】
しかし、上式の仮定は一般に成立しない。言い換えれば、Kakadeのリーマン計量行列は状態行動の同時分布の統計モデルPr(s,a|Ｍ（θ）)において、方策パラメータθの摂動による状態の次式で表される定常分布の変化を無視したリーマン計量行列であることが分かる。
【００８０】
【数１８】
0005150371.tif 000019
【００８１】
一方でBagnell et al． [非特許文献16] やPeters et al． [非特許文献15] らは、以下の内容を示した。
【００８２】
【数１９】
0005150371.tif 000020
【００８３】
そしてBagnell et al． [非特許文献16] とPeters et al． [非特許文献15] らは、強化学習問題つまり平均報酬最大化問題は、式（３）より結局のところシステム軌跡の最適化に帰着するのでKakadeのリーマン計量行列は妥当なリーマン計量行列になり得ることを主張している。
【００８４】
しかし、以下のことがいえる。
【００８５】
【数２０】
0005150371.tif 000021
【００８６】
これはシステム軌跡の統計モデルではシステムの時間進展まで考慮したものであるが、状態行動の統計モデルは考慮していないためであり、以下で明確にする。
【００８７】
【数２１】
0005150371.tif 000022
【００８８】
ではどのフィッシャー情報行列が強化学習問題である平均報酬最大化に適しているのだろうか。先にも述べたように平均報酬（式（４））は状態行動の同時分布（１時間ステップのシステム軌跡）により定まり２時間ステップ以降のシステム進展には依存しないため、Kakade のフィッシャー情報行列は冗長な統計モデルを想定したものであり、状態行動の同時分布のフィッシャー情報行列Fs,a(θ)が最も自然なリーマン計量であると考えられる。単位行列I、フィッシャー情報行列Fs,a(θ)やKakadeのリーマン計量行列等をそれぞれリーマン計量とする自然勾配の数値比較実験は５．節にて示す。
【００８９】
さらに、以下のことがいえる。
【００９０】
【数２２】
0005150371.tif 000023
【００９１】
（3． 3 フィッシャー情報行列とヘッセ行列の類似性）
フィッシャー情報行列Fs,a(θ)とKakadeのリーマン計量行列を平均報酬の方策パラメータθに関する二階偏微分であるヘッセ行列と比較する。
【００９２】
【数２３】
0005150371.tif 000024
【００９３】
Kakade の（無限時間システム軌跡における正規化フィッシャー情報行列）リーマン計量行列の式（１２）とヘッセ行列H(θ) の式（１６）を見比べれば、Kakadeも主張しているように[非特許文献2] 、Kakade のリーマン計量行列はH(θ)の式（１６）の中括弧｛…｝内の初めの二項以外については何ら情報を保持していない。
【００９４】
【数２４】
0005150371.tif 000025
【００９５】
一方、式（９）と（１５）より、状態行動におけるフィッシャー情報行列Fs,a(θ)は明らかにH(θ)の全ての項に関して何らかの情報を保持している。よって、ヘッセ行列との比較の上でも提案フィッシャー情報行列Fs,a(θ)は妥当なリーマン計量になり得ることが示唆される。
【００９６】
また特筆すべきことに、一般に平均報酬は方策パラメータθに関して二次形式ではなく、特にθが最適パラメータθ＊から離れている場合、ヘッセ行列は不定値行列になりやすい。一方で、フィッシャー情報行列はその定義（式(8)）より不定値行列にはならず半正定性が保証されるため、特に強化学習問題においては自然勾配法はヘッセ行列H(θ)を用いるニュートン・ラフソン法等[非特許文献25] より汎用的な共変的な勾配法であると考えられる。これらの数値比較実験は5． 節に示す。
【００９７】
またθにも依存するある特殊な報酬関数を用いた場合、Fs,a(θ)とヘッセ行列は一致する（付録2．）。
（４．フィッシャー情報行列Fs,a(θ) による自然定常方策勾配）
状態と行動の同時分布Pr(s,a|Ｍ（θ）)のフィッシャー情報行列Fs,a(θ)をリーマン計量行列とする平均報酬の自然勾配である自然定常方策勾配の推定を考える。この推定は、報酬関数r(s,a, s') の回帰問題に帰着することを示す。
【００９８】
【数２５】
0005150371.tif 000026
【００９９】
このとき次の[定理1］が成り立つ。
【０１００】
【数２６】
0005150371.tif 000027
【０１０１】
以上より、以下の式で表される関数を基底関数とした線形関数近似器を考える。
【０１０２】
【数２７】
0005150371.tif 000028
【０１０３】
この線形関数近似器で即時報酬rt+1 を最小二乗近似すれば、その学習パラメータωが、次式で表される自然定常方策勾配の不偏推定量になることが分かる。
【０１０４】
【数２８】
0005150371.tif 000029
【０１０５】
よって、自然定常方策勾配推定は報酬関数回帰問題に帰着するので、単純に最小二乗法によっても、またMorimura et al． [非特許文献19] の手法を拡張することでフィッシャー情報行列を明示的に必要としない勾配法によっても自然定常方策勾配は推定可能である。
【０１０６】
また実際に実装する上で、以下の点での注意が必要である。
【０１０７】
【数２９】
0005150371.tif 000030
【０１０８】
なお、この非特許文献26に記載の実装方法については、この文献に詳しいので、後に、簡単に概要をまとめるにとどめる。また、この非特許文献２６の内容は、本件と同一の特許出願人により、特願２００８−０７７６７１号として出願されている。
（5． 数値実験）
本節では、任意性のある様々な状態数のマルコフ決定過程に提案する自然定常方策勾配法や従来勾配法を適用して比較する。
（5.1 計量の比較）
図３は、リーマン計量行列の位相平面上での相違を示す図である。
【０１０９】
図３において、（ｉ）は、提案するフィッシャー情報行列Fs,a(θ)の場合を示し、（ｉｉ）は、Kakadeのリーマン計量行列を示し、（ｉｉｉ）は、単位行列Ｉを示している。
【０１１０】
ここでは、各状態ｓ∈｛1, 2｝が自身と相互の遷移行動Ａ∈｛ｌ, ｍ｝を有し、かつ、各状態遷移が決定論的な２状態マルコフ決定過程（ＭＤＰ）である。
【０１１１】
なお、方策πについては、後に図４で説明するマルコフ決定過程と同様にシグモイド関数としている。
【０１１２】
図において、背景のグレースケールの変化は、状態１と状態２の定常状態分布の比をＬｏｇスケールで表現したものであり、各楕円は、一定の距離ΔθTＧ（θ）Δθ＝ε2を満足するようなΔθの組に対応しており、自然定常方策勾配は、平均勾配の最急勾配を示している。
【０１１３】
提案方法では、楕円の短軸の方向が定常分布の変化方向に沿っており、方策パラメータθの摂動による定常分布の変化をうまく扱えるのがわかる。
（5．2  学習の比較）
（5．2. 1 実験の設定）
状態数｜S｜∈｛3, 10, 20, 35, 50, 65, 80, 100｝、行動数|A|= 2 のマルコフ決定過程（ＭＤＰ）を以下の手順で設定した。
【０１１４】
状態遷移確率p(s’|s,a)に関しては、理論で仮定したマルコフ連鎖M(θ) のエルゴード性が破綻しないように、また一般的な強化学習課題[非特許文献22] にも相当して各状態の結合が粗となるように、言い換えれば状態数増加に従ってM(θ) の混合時間が増すよう設計した。
【０１１５】
具体的な構成方法については、以下のとおりである。
【０１１６】
【数３０】
0005150371.tif 000031
【０１１７】
報酬関数r(s,a,s’)に関しては、引数の各組み合わせの戻り値をそれぞれ標準正規分布Ｎ(μ＝0,σ2＝１) に従って一時的に定め、そして各MDP 設定の平均報酬の大きさを揃えるために、平均報酬の最大値max R(θ) = 1、最小値minR(θ) = 0 となるように次式で報酬関数を正規化した：
【０１１８】
【数３１】
0005150371.tif 000032
【０１１９】
また、方策π(a|s;θ)に関しては、以下のように設定した。すなわち、
【０１２０】
【数３２】
0005150371.tif 000033
【０１２１】
（5． 2． 2 各勾配法の設定）
上記のMDP に提案法と3 種の従来法の計4 種の方策勾配法を適用した。それらの違いは勾配を求める際に用いるリーマン計量行列G(θ)（式(6)）に関してで、この４種の方策勾配法とは、以下のとおりである。
【０１２２】
【数３３】
0005150371.tif 000034
【０１２４】
このヘッセ行列調整法は、λmax に応じて調整の程度が変わる点以外は、偏微分方向とニュートン方向を内挿する一般的な調整法である[非特許文献27]。
【０１２５】
調整度合いが大きい時、その勾配方向は以下の偏微分の方向と変わらなくなってしまうので、本実験では可能な限りヘッセ行列の性質を消失させないために必要最小限の補正で済むよう調整度合いを可変とした。
【０１２６】
各勾配法を実装するにあたり、本発明では勾配推定のためのデータサンプリング問題は議論しておらず、その勾配方向だけに注目しているので、各勾配は解析的に求めた。その際に必要となる値のうち、定常分布とその偏微分の導出は単純でないので、付録3． に示した。学習ステップ総数T は300とし、方策パラメータ更新（式(7)）における各勾配法の学習率ηは、以下の式により定めた。
【０１２７】
【数３４】
0005150371.tif 000035
【０１２８】
もしも学習率ηが適切であれば、Ｒ（θ）は、式（７）による方策の更新で、常に増加する。それゆえ、方策の更新がＲ（θ）を減少させるときは、学習率を”η：＝η／２”と調節し、同じタイムステップにおいて、再度、更新を試みることとした。このような調整は、ΔＲ（θ）＞＝０である範囲で維持された。一方で、η0＞ηが、次のステップでも成り立つときは、” η：＝２η”と調整して、学習が停止するのを防止した。
【０１２９】
（5．3 実験結果と考察）
図４は、5． 2． 1 節に従って設定した状態数｜S｜= 100 のMDP について、それぞれ初期設定値の異なる１０のエピソードの学習曲線を示す図である。ただし他のMDP 設定においても同様な結果となる。
【０１３０】
図４より提案自然定常方策勾配法は他の勾配法に比べ一様に方策パラメータの最適化に成功したことが分かる。例えば、あるエピソードに関して各勾配法を比べれば唯一提案法のみ学習が成功していて、他の勾配法は学習プラトー（停滞）に陥っていたことが確認できる。ただし、特定のエピソードで比べると全ての勾配法で学習が成功していて、提案法に関しては学習も平均報酬の立ち上がりも最も遅い、という場合もみられる。これらには次の理由が考えられる。平均報酬とは式(4) より報酬関数を状態行動同時分布Pr(s,a|Ｍ（θ）)で重み付けした線形結合和で定まるため、一般にPr(s,a|Ｍ（θ）)が大きく変わればその値も大きく変わる。そして提案勾配法はPr(s,a|Ｍ（θ）)のフィッシャー情報行列Fs,a(θ)をリーマン計量として用いるため、十分に小さい学習率ηのもとで一回の方策パラメータの更新ΔθによるKL ダイバージェンスは一定であり、Pr(s,a|Ｍ（θ）) が大きく変わることはないため平均報酬R(θ) も急激には変化しない。
【０１３１】
一方で、他の勾配法では他のリーマン計量を用いているためPr(s,a|Ｍ（θ）) が急激に変化し得るために、即時的に平均報酬を素早く大きくすることが可能である。しかしその分、他の学習法では学習プラトーに陥りやすくなってしまい、図５ のような結果が得られたのだと考えられる。その具体的な原因の一つとして、Pr(s,a|Ｍ（θ）)が急激に変われば、偏微分（式(5)）も大きく変わり易く極めて0 に近づくこともあり、そこでは各勾配法におけるパラメータ空間に対する目的関数R(θ)の幾何構造も平坦に成り易かった問題が考えられる。
【０１３２】
また図４は、多層パーセプトロンの学習に自然勾配を用いたAmari et al． [非特許文献14] の結果とも一致している。
【０１３３】
図５は各状態数｜S｜∈｛3, 10, 20, 35, 50, 65, 80, 100｝のMDP における各勾配法の300 エピソードによる学習成功率(Success Rate)を表す図である。
【０１３４】
平均報酬R(θ) の最大値は1 と設定したので、R(θT ) > 0.95 ならその学習を成功とした。
【０１３５】
図５より状態数が少ないMDP の場合、提案自然勾配法とKakade の自然勾配法は他の勾配法に比べプラトーに陥らず適切に学習していたことがわかる。これは、提案自然勾配法ではそのものだが、Kakade の自然勾配法で用いるリーマン計量行列も統計モデルPr(s,a|Ｍ（θ）)のフィッシャー情報行列と関連した計量であるためだと考えられる。
【０１３６】
一方で状態数が多い場合、提案自然勾配法に比べKakade の自然勾配法は学習に失敗している。これは3． 2 節で理論的に議論した通りKakade 法は状態の分布に関するフィッシャー情報量Fs(θ) を無視しているためだと考えられる。
【０１３７】
さらに図よりKakade 法は擬似ニュートン勾配法に対しても、状態数が多い場合では劣っていたことが確認できる。これはKakade 法はFs(θ) に関する情報を何ら捉えていない一方で、擬似ニュートン勾配法はFs(θ) という形ではないがθによる定常分布の微分に関する情報も持った「計量行列G(θ) が−（擬似ヘッセ行列）に等しい」との関係を用いていたためだと考えられる（式(16)）。
【０１３８】
図６は、各勾配法がどの程度学習プラトーに陥っているかを示す図である。図６において、縦軸は、プラトーの指標として学習曲線の滑らかさ（離散曲率）Δ2Ｒ（θt）の絶対値の積算を用いた。
【０１３９】
図６より、どの状態数においても提案自然勾配法が最も滑らかに学習していたことが確認でき、これまでの結果とも一致して提案手法が最もプラトーに陥いり難い手法であることが示唆される。
【０１４０】
以上数値実験より、提案自然勾配法はMDP の環境設定(p, r, ψ ) 及び初期方策パラメータ値θ0に依存せず、また特に定常分布と方策パラメータに強い相関があっても状態数に依存せず、学習のプラトーを避け適切に学習できることが確認できた。よって本勾配法はKakade が提案した自然方策勾配法より、より自然な自然方策勾配法であると考えられる。
【０１４１】
付録１．として、式（１４）の導出は、以下のように行うことができる。
【０１４２】
【数３５】
0005150371.tif 000036
【０１４３】
また、付録２．として、フィッシャー情報行列とヘッセ行列の一致性は以下のようにして示される。
【０１４４】
【数３６】
0005150371.tif 000037
【０１４５】
さらに、付録３．として、定常分布とその偏微分の導出は以下のようにして行われうる。
【０１４６】
【数３７】
0005150371.tif 000038
【０１４７】
式（A-2）より、定常分布ベクトルは、以下のようにして求まる。
【０１４８】
【数３８】
0005150371.tif 000039
【０１４９】
同様にして、第２階偏微分は次式で求まる。
【０１５０】
【数３９】
0005150371.tif 000040
【０１５１】
図７は、本発明の制御器の構成の一例を示す概念図である。
図７の例では、制御器は、行動、すなわち、制御信号を制御対象に与える処理を行って、制御対象の状態量を観測器（たとえば、位置センサ、角度センサ、加速度センサ、角加速度センサなど）で観測し、この観測結果により「定常分布の対数の偏微分」（ＬＳＤＧ）を推定し、これを用いて「自然定常方策勾配」を推定して、方策パラメータを更新し、これにより方策を更新する。そして、更新された方策により、制御信号（以上の説明での行動に対応する）が生成され、さらに、制御対象が制御される。
（６．非特許文献２６に示される定常分布の勾配の導出の実装の概要）
方策の勾配および定常分布の勾配の導出の実装については、非特許文献２６に詳しいが、以下では、その実装方法の大略を確認のためにまとめる。
【０１５２】
なお、一部ノーテーションについては、以降の説明では、新たに定義し直しているものがある。
【０１５３】
以下では、マルコフ決定過程（ＭＤＰ）について考えることにし、制御対象（制御器の環境）は状態遷移確率（時刻ｔにおいて、状態ｘtであるときに行動（制御）ｕtを実行することで状態がｘt+1となる確率）と報酬関数ｒt+1＝ｒ（ｘt，ｕt）（なお、ｒt+1＝ｒ（ｘt＋１,ｘt，ｕt  ）の場合にも同様に議論できる）によって特徴づけられるものとする。なお、この報酬関数については、制御対象の制御目標に応じて予め定められているものとする。状態入力ｘ∈Ｘから行動出力ｕ∈Ｕへの写像を方策と呼び、以下で説明するように確率的に表現する。方策は、パラメータθで、規定される。
【０１５４】
有限な状態Ｘ∋ｘの組と行動Ｕ∋ｕとを有する離散時間ＭＤＰは、以下の状態遷移確率ｐと報酬関数ｒ+1によって規定される。
【０１５５】
【数４０】
0005150371.tif 000041
【０１５６】
ここで、記載の簡単のために、ｘ+1は、状態ｘにおいて、行動ｕにより与えられる次の状態であり、ｒ+1は、ｘ+1において観測された即時報酬である。ｘ+kおよびｕ+kは、それぞれ、状態ｘからｋ時間ステップ先の状態および行動であり、添え字が−ｋとなっていれば、その反対である。（ＭＤＰにおける）決定は、θ∈Ｒdによりパラメータ化された以下の確率的方策πにしたがってなされる。
【０１５７】
【数４１】
0005150371.tif 000042
【０１５８】
以下の方策πは、全てのｘ∈Ｘおよびｕ∈Ｕに対して、θについて微分可能であると仮定する。
【０１５９】
【数４２】
0005150371.tif 000043
【０１６０】
さらに、以下のような仮定をおく。
（仮定１）
以下のような状態遷移確率ｐと確率的方策πとを有するマルコフ連鎖Ｍ（θ）は、全ての方策パラメータについてエルゴート的（既約で非周期的）である。
【０１６１】
【数４３】
0005150371.tif 000044
【０１６２】
したがって、以下のただ１つの定常分布が存在する。
【０１６３】
【数４４】
0005150371.tif 000045
【０１６４】
この定常分布は、初期状態には独立であって、以下の式を満たす。
【０１６５】
【数４５】
0005150371.tif 000046
【０１６６】
ここで、以下の式が成り立つ。
【０１６７】
【数４６】
0005150371.tif 000047
【０１６８】
ＰＧＲＬの目的は、以下の「平均報酬」と呼ばれる即時報酬の平均を最大化する方策パラメータθ＊を見いだすことである。
【０１６９】
【数４７】
0005150371.tif 000048
【０１７０】
仮定１の下では、平均報酬は、初期状態ｘには独立で、以下の式に等しいことが示される：
【０１７１】
【数４８】
0005150371.tif 000049
【０１７２】
方策勾配ＲＬアルゴリズムは、方策パラメータθを、以下の式に示されるθについての平均報酬Ｒ（θ）の勾配の方向に更新する。
【０１７３】
【数４９】
0005150371.tif 000050
【０１７４】
以下、単に方策勾配（ＰＧ）と、しばしば呼ばれる。この方策勾配は、以下のように与えられる。
【０１７５】
【数５０】
0005150371.tif 000051
【０１７６】
以下の式に示される定常分布の対数の偏微分の導出は簡単ではない。
【０１７７】
【数５１】
0005150371.tif 000052
【０１７８】
そこで、従来のＰＧアルゴリズムは、ＰＧのもう一つの表現を利用している。
【０１７９】
【数５２】
0005150371.tif 000053
【０１８０】
ここで、割引率γ∈［０，１）で、それぞれ、行動価値関数Ｑと状態価値関数Ｖとは以下のように表される。
【０１８１】
【数５３】
0005150371.tif 000054
【０１８２】
式（２３）の第２項の寄与は、γが１に近づくにつれて小さくなるので、従来のアルゴリズムは、γ〜１とすることで、第１項のみからＰＧを近似している。このような省略による偏りは、割引率γを1に近づければ小さくなるが、推定の分散は多くなってしまう。
【０１８３】
ここでは、もう１つのアプローチを提案する。そこでは、以下の式の定常分布の対数の偏微分（ＬＳＤＧ）を推定し、ＰＧを導出するために式（２２）を用いる。
【０１８４】
【数５４】
0005150371.tif 000055
【０１８５】
著しい特徴は、価値関数を学習する必要がなく、したがって、そのアルゴリズムは、割引率γの選択において、偏りと分散のトレードオフと関係がないことである。
（６．１   定常分布の対数の偏微分の推定）
以下では、最小二乗法に基づくＬＳＤＧ推定アルゴリズム、ＬＳＤＧ（λ）を提案する。この目的のために、エルゴート的なマルコフ連鎖Ｍ（θ）の逆過程を定式化し、ＬＳＤＧは、ＴＤ法の枠組みで推定できることを示す。
（６．１．１  順方向および逆方向マルコフ連鎖の性質）
ベイズの理論を用いれば、現在の状態から過去の状態および行動の対への逆方向の確率は、以下の式で表される。
【０１８６】
【数５５】
0005150371.tif 000056
【０１８７】
以下の事後確率ｑは事前分布ｐに依存する。
【０１８８】
【数５６】
0005150371.tif 000057
【０１８９】
以下のように、事前分布ｐが定常分布ｄと方策πに従うとき、事後分布ｑは、定常逆方向確率と呼ばれ、下付添え字Ｂ（θ）が加えられる。
【０１９０】
【数５７】
0005150371.tif 000058
【０１９１】
マルコフ連鎖―Ｍ（θ）とＢ（θ）の両方―は、以下の２つの定理において記述されるように密接に関連している。
（定理１）
【０１９２】
【数５８】
0005150371.tif 000059
【０１９３】
（証明）
式（２４）の両辺に以下の定常分布をかける。
【０１９４】
【数５９】
0005150371.tif 000060
【０１９５】
すると、全ての可能な行動ｕ-1∈Ｕについて総和をとると、以下の式が得られる：
【０１９６】
【数６０】
0005150371.tif 000061
【０１９７】
そして、式（２６）の両辺を可能な状態ｘ∈Ｘについて総和をとると、以下の式が成り立つ。
【０１９８】
【数６１】
0005150371.tif 000062
【０１９９】
このことは、以下の２点を成立させる．（ｉ）Ｂ（θ）は、Ｍ（θ）と同一の定常分布を有すること、（ｉｉ）Ｂ（θ）はＭ（θ）と同じ既約な性質を有すること。
【０２００】
【数６２】
0005150371.tif 000063
【０２０１】
このことは、（ｉｉｉ）Ｂ（θ）がＭ（θ）と同じ非周期的な性質をもっていることを示唆する。式（２５）は、（ｉ）−（ｉｉｉ）により直接証明される。
（定理２）
【０２０２】
【数６３】
0005150371.tif 000064
【０２０３】
（証明）
マルコフ連鎖の特性と式（２４）を代入することにより、以下の関係が得られる。
【０２０４】
【数６４】
0005150371.tif 000065
【０２０５】
このことは、有限のＫの場合において式（２７）が成立することを証明する。定理１から以下の式が導かれるので、式（２７）のＫ→∞の極限の場合も成立することが、すぐさま証明される。
【０２０６】
【数６５】
0005150371.tif 000066
【０２０７】
定理１および定理２は、これらが、定常分布に収束する状態分布の下で、順方向マルコフ連鎖Ｍ（θ）からのサンプルは、そのまま、逆方向マルコフ連鎖Ｂ（θ）に関する推定に使用できることになるので、重要である。そして、これらは、後に利用されうるものである。
（６．１．２  逆方向から順方向のマルコフ連鎖のＬＳＤＧのためのＴＤ（Temporal Difference）学習法）
ＬＳＤＧは式（２４）を用いて、以下のように分解される。
【０２０８】
【数６６】
0005150371.tif 000067
【０２０９】
式（２９）は、状態ｘのＬＳＤＧは、以下の式で表される方策の対数の偏微分の状態ｘから逆方向マルコフ連鎖Ｂ（θ）の無限区間の集積であることを暗示している。
【０２１０】
【数６７】
0005150371.tif 000068
【０２１１】
式（２８）および（２９）から、ＬＳＤＧは、Ｍ（θ）よりもむしろ逆方向マルコフ連鎖Ｂ（θ）についての、以下のような逆方向ＴＤ  δに関するＴＤ学習により推定されうる。
【０２１２】
【数６８】
0005150371.tif 000069
【０２１３】
ここで、最初の２つの項は、Ｂ（θ）における方策の対数の偏微分の１ステップ前の実際の観測値と１ステップ前のＬＳＤＧであり、現在の状態のＬＳＤＧが最後の項である。
【０２１４】
【数６９】
0005150371.tif 000070
【０２１５】
適格度減衰率λ∈［０，１］と逆方向追跡時間ステップＫ∈Ｎを用いて、式（２９）は、以下のように一般化される。
【０２１６】
【数７０】
0005150371.tif 000071
【０２１７】
上記のような設定でなくとも、大きなλやＫを用いたならば、このような最小化は従来の価値関数に対するＴＤ（λ）学習の場合のように、非マルコフ効果に対しては、より敏感ではない。
【０２１８】
【数７１】
0005150371.tif 000072
【０２１９】
理論的な仮定と現実への適用との間のギャップを埋めるために、以下の２つのうちのいずれかの戦略をとる必要がある。（ｉ）λ〜１ならば、Ｋは、あまり大きな整数に設定しない、（ｉｉ）Ｋ〜ｔならば、λは、１に設定しない、ここで、ｔは、現実の順方向マルコフ連鎖の現在のタイムステップである。
（６．１．３  ＬＳＤＧ推定アルゴリズム：制限付き逆方向ＴＤ（λ）の最小二乗法）
【０２２０】
【数７２】
0005150371.tif 000073
【０２２１】
この６．１．３では、最小二乗法に基づく、ＬＳＤＧ推定アルゴリズム、ＬＳＤＧ（λ）を提案する。これは、同時に、平均二乗を減少させるとともに、制約条件を満足することを達成しようとするものである。
【０２２２】
【数７３】
0005150371.tif 000074
【０２２３】
したがって、最小化すべき対象となる関数は、以下の式（３２）となる。
【０２２４】
【数７４】
0005150371.tif 000075
【０２２５】
ここで、右辺の第２項は、式（３１）の制約条件のためのものである。したがって、式（３２）の偏微分は、以下のようになる。
【０２２６】
【数７５】
0005150371.tif 000076
【０２２７】
一般的なＲＬ問題では、このような相関が存在するので、このような偏りを除くために、操作変数法（instrumental variable method）を適用する。
【０２２８】
【数７６】
0005150371.tif 000077
【０２２９】
以下では、現実のマルコフ連鎖Ｍ（θ）における時間ステップｔの状態を示すために、ノーテーションをｘｔに変更する。提案するＬＳＤＧ推定アルゴリズム、ＬＳＤＧ（λ）は、適格性減衰率λ∈［０，１）の下で、逆方向にさかのぼる時間ステップＫを現在の状態ｘｔのタイムステップｔと同じにする。すなわち、以下が成り立つ。
【０２３０】
【数７７】
0005150371.tif 000078
【０２３１】
図８は、ＬＳＤＧ（λ）を求める手順をアルゴリズム１として示す図である。
【０２３２】
【数７８】
0005150371.tif 000079
【０２３３】
また、図９は、アルゴリズム１を示すフローチャートである。
図９を参照して、まず、ステップＳ１００において、処理の前提として、以下の設定がなされる。
【０２３４】
【数７９】
0005150371.tif 000080
【０２３５】
続いて、初期化処理として、以下の処理が行われる（ステップＳ１０２）。
【０２３６】
【数８０】
0005150371.tif 000081
【０２３７】
時間ステップｔがｔ＝０とされ（ステップＳ１０４）、以下の処理が、ｔ＝０からｔ＝Ｔ−１まで繰り返される（ステップＳ１０６〜Ｓ１１６）。
【０２３８】
まず、ステップＳ１０６においてｔ＝０であれば、初期状態が観測され（ステップＳ１０８）、続いて、以下の設定が行われる（Ｓ１１０）。
【０２３９】
【数８１】
0005150371.tif 000082
【０２４０】
一方、ステップＳ１０６において、ｔが０でなければ、以下の処理が行われる（ステップＳ１１２）。
【０２４１】
【数８２】
0005150371.tif 000083
【０２４２】
ステップＳ１１０またはＳ１１２に続いて、以下の計算が行われる（ステップＳ１１４）。
【０２４３】
【数８３】
0005150371.tif 000084
【０２４４】
ステップＳ１１６にて、ｔがＴよりも小さければ処理はステップＳ１０６に復帰し、ｔがＴ以上であれば、処理はステップＳ１１８に移行して、以下の計算を行う。
【０２４５】
【数８４】
0005150371.tif 000085
【０２４６】
続いて、以下の計算によりＬＳＤＧの推定値を得る。
【０２４７】
【数８５】
0005150371.tif 000086
【０２４８】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【図面の簡単な説明】
【０２４９】
【図１】本発明の制御方法および制御プログラムが適用される制御器を用いたシステム１０００の一例を示す概念図である。
【図２】コンピュータ１００の構成をブロック図形式で示す図である。
【図３】リーマン計量行列の相違を示す図である。
【図４】学習曲線を示す図である。
【図５】各勾配法の学習成功率を表す図である。
【図６】各勾配法がどの程度学習プラトーに陥っているかを示す図である。
【図７】本発明の制御器の構成の一例を示す概念図である。
【図８】ＬＳＤＧ（λ）を求める手順をアルゴリズム１として示す図である。
【図９】アルゴリズム１を示すフローチャートである。
【符号の説明】
【０２５０】
１００  コンピュータ、１０２  コンピュータ本体、１０４  ディスプレイ、１０６  ＦＤドライブ、１０８  ＣＤ−ＲＯＭドライブ、１１０  キーボード、１１２  マウス、１１８  ＣＤ−ＲＯＭ、１２０  ＣＰＵ、１２２  メモリ、１２４  ハードディスク、１２８  通信インタフェース、２００  被制御装置、１０００  システム。
【図１】
0005150371.tif 000087
【図２】
0005150371.tif 000088
【図７】
0005150371.tif 000089
【図８】
0005150371.tif 000090
【図９】
0005150371.tif 000091
【図３】
0005150371.tif 000092
【図４】
0005150371.tif 000093
【図５】
0005150371.tif 000094
【図６】
0005150371.tif 000095