(57)【特許請求の範囲】
【請求項１】
対象とするシステムの時間発展が順方向マルコフ決定過程として記述される際に、前記システムの状態に対する制御則である確率的に表現される方策を前記システムの状態量の観測により方策勾配法によって強化学習する制御器であって、
前記方策に基づいて、前記システムを制御するための制御信号を生成する制御信号生成手段と、
前記システムの前記状態量を観測する状態量検知手段と、
前記状態と前記制御信号とに予め定められた関係で依存する報酬値を獲得する報酬値獲得手段と、
確率的な前記方策を規定するパラメータである方策パラメータにより前記方策が規定されるとき、各タイムステップにおける前記状態量と前記制御信号とに基づいて、前記システムの状態の分布の定常分布の対数の前記方策パラメータについての偏微分である対数定常分布偏微分を推定することで、前記方策の勾配を推定する方策勾配推定手段と、
前記報酬値と前記方策勾配推定手段による推定結果とに基づいて、前記対数定常分布偏微分を用いて推定した平均報酬偏微分の方向に前記方策パラメータを微小変化させることで、前記方策を更新する方策更新手段とを備える、制御器。
【請求項２】
前記方策勾配推定手段は、前記状態の分布の前記状態についての和が一定であるとの条件により導かれる制約条件であって、前記対数定常分布偏微分の順方向マルコフ連鎖についての期待値が０であるという制約条件の下で、逆方向マルコフ連鎖に対するＴＤ学習により、前記対数定常分布偏微分を推定する、請求項１記載の制御器。
【請求項３】
前記ＴＤ学習においては、ｉ）前記逆方向マルコフ連鎖における前記方策の対数の偏微分の１ステップ前の観測値と１ステップ前の前記対数定常分布偏微分の和と、現在の状態の前記対数定常分布偏微分との差をδとするとき、前記δの２乗の前記順方向マルコフ連鎖についての期待値と、ｉｉ）前記対数定常分布偏微分の前記順方向マルコフ連鎖についての期待値の２乗との和を最小化することにより、前記対数定常分布偏微分を推定する、請求項２記載の制御器。
【請求項４】
対象とするシステムの時間発展が順方向マルコフ決定過程として記述される際に、前記システムの状態に対する制御則である確率的に表現される方策を前記システムの状態量の観測により方策勾配法によって強化学習する制御方法であって、
前記方策に基づいて、前記システムを制御するための制御信号を生成する制御信号生成ステップと、
前記システムの前記状態量を観測する状態量検知ステップと、
前記状態と前記制御信号とに予め定められた関係で依存する報酬値を獲得する報酬値獲得ステップと、
確率的な前記方策を規定するパラメータである方策パラメータにより前記方策が規定されるとき、各タイムステップにおける前記状態量と前記制御信号とに基づいて、前記システムの状態の分布の定常分布の対数の前記方策パラメータについての偏微分である対数定常分布偏微分を推定することで、前記方策の勾配を推定する方策勾配推定ステップと、
前記報酬値と前記方策勾配推定ステップによる推定結果とに基づいて、前記対数定常分布偏微分に基づき表現される平均報酬の勾配の方向に前記方策パラメータを更新することで、前記方策を更新する方策更新ステップとを備える、制御方法。
【請求項５】
前記方策勾配推定ステップは、前記状態の分布の前記状態についての和が一定であるとの条件により導かれる制約条件であって、前記対数定常分布偏微分の順方向マルコフ連鎖についての期待値が０であるという制約条件の下で、逆方向マルコフ連鎖に対するＴＤ学習により、前記対数定常分布偏微分を推定するステップを含む、請求項４記載の制御方法。
【請求項６】
前記ＴＤ学習においては、ｉ）前記逆方向マルコフ連鎖における前記方策の対数の偏微分の１ステップ前の観測値と１ステップ前の前記対数定常分布偏微分の和と、現在の状態の前記対数定常分布偏微分との差をδとするとき、前記δの２乗の前記順方向マルコフ連鎖についての期待値と、ｉｉ）前記対数定常分布偏微分の前記順方向マルコフ連鎖についての期待値の２乗との和を最小化することにより、前記対数定常分布偏微分を推定する、請求項５記載の制御方法。
【請求項７】
対象とするシステムの時間発展が順方向マルコフ決定過程として記述される際に、前記システムの状態に対する制御則である確率的に表現される方策を前記システムの状態量の観測により方策勾配法によって強化学習する制御方法をコンピュータに実行させるためのプログラムであって、
前記方策に基づいて、前記システムを制御するための制御信号を生成する制御信号生成ステップと、
前記システムの前記状態量を観測する状態量検知ステップと、
前記状態と前記制御信号とに予め定められた関係で依存する報酬値を獲得する報酬値獲得ステップと、
前記確率的な表現を規定するパラメータである方策パラメータにより前記方策が規定されるとき、各タイムステップにおける前記状態量と前記制御信号とに基づいて、前記システムの状態の分布の定常分布の対数の前記方策パラメータについての偏微分である対数定常分布偏微分を推定することで、前記方策の勾配を推定する方策勾配推定ステップと、
前記報酬値と前記方策勾配推定ステップによる推定結果とに基づいて、前記対数定常分布偏微分に基づき表現される平均報酬の勾配の方向に前記方策パラメータを更新することで、前記方策を更新する方策更新ステップとを含む、制御方法をコンピュータに実行させるための制御プログラム。
【請求項８】
前記方策勾配推定ステップは、前記状態の分布の前記状態についての和が一定であるとの条件により導かれる制約条件であって、前記対数定常分布偏微分の順方向マルコフ連鎖についての期待値が０であるという制約条件の下で、逆方向マルコフ連鎖に対するＴＤ学習により、前記対数定常分布偏微分を推定するステップを含む、請求項７記載の制御プログラム。
【請求項９】
前記ＴＤ学習においては、ｉ）前記逆方向マルコフ連鎖における前記方策の対数の偏微分の１ステップ前の観測値と１ステップ前の前記対数定常分布偏微分の和と、現在の状態の前記対数定常分布偏微分との差をδとするとき、前記δの２乗の前記順方向マルコフ連鎖についての期待値と、ｉｉ）前記対数定常分布偏微分の前記順方向マルコフ連鎖についての期待値の２乗との和を最小化することにより、前記対数定常分布偏微分を推定する、請求項８記載の制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、方策勾配法により制御対象を制御する制御器、制御方法および制御プログラムの構成に関する。
【背景技術】
【０００２】
「マルコフ決定過程」として定式化される制御問題は、ロボット、プラント、移動機械（電車、自動車）などの自律的制御問題として、幅広い応用を持つ重要な技術である。
【０００３】
マルコフ決定過程に対する最適制御に関する従来技術として、いわゆる「強化学習」がある。
【０００４】
「強化学習」とは、エージェントが環境と相互作用を通じて試行錯誤し、得られる累積報酬量を最大化するような「方策」と呼ばれる行動則、すなわち、制御問題に用いる場合には、「制御規則」を学習する理論的な枠組みである。この学習法は、環境やエージェント自身に関する先験的な知識をほとんど必要としない点で様々な分野から注目を集めている。
【０００５】
強化学習は大まかに２つに分類できる。価値関数を用いて間接的に方策を表現し、価値関数を更新することで方策も更新される「価値関数更新法」と、方策を明示的にもち目的関数の勾配に従って方策を更新する「直接方策更新法（方策勾配法）」である。
【０００６】
方策勾配法は、行動のランダム性を制御するパラメータも方策パラメータに含めることで確率的方策の獲得が可能であり、また連続系への適用性も高いため、特に注目を集めている。しかし一般に実タスクへ適用すると、適切な行動則を獲得するまでの時間が非現実となることがある。そこで、複数学習器の同時利用、モデルの利用、教示信号の利用等の補助機構を入れて学習時間を短縮させる研究が活発に行われ、成果も著しい。
【０００７】
ここで、方策勾配強化学習法（ＰＧＲＬ）は、方策パラメータについての平均報酬の偏微分を用いることにより、方策パラメータを改善して平均報酬を最大化するための強化学習（ＲＬ：Reinforcemnt Learning）の一般的なアルゴリズムである。ここで、平均報酬の偏微分は、方策勾配（ＰＧ：Policy Gradient）と呼ばれる。従来の方策勾配強化学習法アルゴリズム（ＰＧアルゴリズム）［非特許文献１，非特許文献２］は、状態の定常分布の偏微分の計算が困難であったため、方策パラメータの変化によりもたらされる定常分布の変化に依存する方策勾配の項を無視している。これらは、定常分布の対数の偏微分−ＬＳＤＧ（(Log) Stationary Distribution Gradients）−と呼ばれる。このような省略による偏りは、いわゆる割引率γを1に近づければ減少するが、一方で推定された偏微分の分散は多くなってしまう。このようなトレードオフは、現実に、適切なγを見いだすことを困難にしていた。マルコフ連鎖の時間を混合する（mixing）ことは適切なγを決定するための尺度である［非特許文献１，非特許文献３］。しかしながら、時間の混合は、方策に依存し、したがって、一般には、学習が完了する前に、予測することは困難である。
【０００８】
また、平均報酬ＰＧアルゴリズム［非特許文献４，非特許文献５］は、ポアソン方程式の解としての微分コスト関数を導入することにより、割引率を使用しないものである。しかしながら、割引率が１に近い通常のＰＧと平均報酬ＰＧとのパフォーマンスには、理論的には、大きな相違が無いことが示唆されている［非特許文献６］。
【０００９】
したがって、上述したような推定される方策パラメータの偏りを減少させると分散が増大するというトレードオフを解決した学習方法が必要である。
【００１０】
なお、以下、本文中で引用することとなる方策勾配学習法に関連した先行技術文献を以下に挙げる。
【非特許文献１】Baxter, J. and P. Bartlett (2001) “Infinite-Horizon Policy-Gradient Estimation," Journal of Artificial Intelligence Research, Vol. 15, pp. 319-350.
【非特許文献２】H. Kimura and S. Kobayashi. An analysis of actor/critic algorithms using eligibility traces: Reinforcement learning with imperfect value function. In International Conference on Machine Learning, 1998.
【非特許文献３】S. Kakade. Optimizing average reward using discounted rewards. In Annual Conference on Computational Learning Theory, volume 14. MIT Press,2001.
【非特許文献４】J. N. Tsitsiklis and B. Van Roy. Average cost temporal-difference learning. Automatica, 35(11):1799-1808, 1999.
【非特許文献５】V. S. Konda and J. N. Tsitsiklis. On actor-critic algorithms. SIAM Journal on Control and Optimization, 42(4):1143-1166, 2001.
【非特許文献６】］J. N. Tsitsiklis and B. Van Roy. On average versus discounted reward temporal-difference learning. Machine Learning, 49(2):179-191, 2002.
【非特許文献７】P. W. Glynn. Likelihood ratio gradient estimation for stochastic systems. Communications of the ACM, 33(10):75-84, 1991.
【非特許文献８】R. Y. Rubinstein. How to optimize discrete-event system from a single sample path by the score function method. Annals of Operations Research, 27(1):175-212, 1991.
【非特許文献９】A. Y. Ng, R. Parr, and D. Koller. Policy search via density estimation. In Advances in Neural Information Processing Systems. MIT Press, 2000.
【非特許文献１０】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. Learning to predict by the methods of temporal differences. Machine Learning, 3:9-44, 1988.
【非特許文献１３】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.
【非特許文献１５】R. B. Schinazi. Classical and Spatial Stochastic Processes. Birkhauser, 1999.
【非特許文献１６】J. Peng and R. J. Williams. Incremental multi-step Q-learning. Machine Learning, 22:283-290, 1996.
【非特許文献１７】P. Young. Recursive Esimation and Time-series Analysis. Springer-Verlag, 1984.
【非特許文献１８】D. P. Bertsekas and J. N. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, 1996.
【発明の開示】
【発明が解決しようとする課題】
【００１１】
すでに、（定常）状態分布の勾配を評価するための２つの方法があるが、これらは、本願発明の方法とは異なったものであり、以下のような問題がある。最初のものは、「尤度比勾配法」あるいは「スコア関数法」と呼ばれるものであり［非特許文献７，非特許文献８］、再生プロセスにしか適用できない問題がある［非特許文献１］。非特許文献９に開示された他の方法は、状態分布の直接的な評価ではなく、密度伝搬を伴う状態分布の評価を介して実行されるものである。したがって、これらの方法は、エージェントがどの状態にあるかの知識を必要とするのに対し、後に説明する本発明の方法では、ノイズを含む状態の特徴ベクトルを観測するのみでよい。
【００１２】
したがって、本発明は、上記のような問題点を解決するためになされたものであって、その目的は、方策パラメータの偏りを減少させると分散が増大するというトレードオフを解決した方策勾配学習方法を用いた制御器、制御方法または制御プログラムを提供することである。
【００１３】
本発明の他の目的は、汎用性のある方策勾配学習方法を用いた制御器、制御方法または制御プログラムを提供することである。
【課題を解決するための手段】
【００１４】
このような目的を達成するために、本発明の制御器は、対象とするシステムの時間発展が順方向マルコフ決定過程として記述される際に、システムの状態に対する制御則である確率的に表現される方策をシステムの状態量の観測により方策勾配法によって強化学習する制御器であって、方策に基づいて、システムを制御するための制御信号を生成する制御信号生成手段と、システムの状態量を観測する状態量検知手段と、状態と制御信号とに予め定められた関係で依存する報酬値を獲得する報酬値獲得手段と、確率的な方策を規定するパラメータである方策パラメータにより方策が規定されるとき、各タイムステップにおける状態量と制御信号とに基づいて、システムの状態の分布の定常分布の対数の方策パラメータについての偏微分である対数定常分布偏微分を推定することで、方策の勾配を推定する方策勾配推定手段と、報酬値と方策勾配推定手段による推定結果とに基づいて、対数定常分布偏微分を用いて推定した平均報酬偏微分の方向に方策パラメータを微小変化させることで、方策を更新する方策更新手段とを備える。
【００１５】
好ましくは、方策勾配推定手段は、状態の分布の状態についての和が一定であるとの条件により導かれる制約条件であって、対数定常分布偏微分の順方向マルコフ連鎖についての期待値が０であるという制約条件の下で、逆方向マルコフ連鎖に対するＴＤ学習により、対数定常分布偏微分を推定する。
好ましくは、ＴＤ学習においては、ｉ）逆方向マルコフ連鎖における方策の対数の偏微分の１ステップ前の観測値と１ステップ前の対数定常分布偏微分の和と、現在の状態の対数定常分布偏微分との差をδとするとき、δの２乗の順方向マルコフ連鎖についての期待値と、ｉｉ）対数定常分布偏微分の順方向マルコフ連鎖についての期待値の２乗との和を最小化することにより、対数定常分布偏微分を推定する。
【００１６】
この発明の他の局面に従うと、対象とするシステムの時間発展が順方向マルコフ決定過程として記述される際に、システムの状態に対する制御則である確率的に表現される方策をシステムの状態量の観測により方策勾配法によって強化学習する制御方法であって、方策に基づいて、システムを制御するための制御信号を生成する制御信号生成ステップと、システムの状態量を観測する状態量検知ステップと、状態と制御信号とに予め定められた関係で依存する報酬値を獲得する報酬値獲得ステップと、確率的な方策を規定するパラメータである方策パラメータにより方策が規定されるとき、各タイムステップにおける状態量と制御信号とに基づいて、システムの状態の分布の定常分布の対数の方策パラメータについての偏微分である対数定常分布偏微分を推定することで、方策の勾配を推定する方策勾配推定ステップと、報酬値と方策勾配推定手段による推定結果とに基づいて、対数定常分布偏微分に基づき表現される平均報酬の勾配の方向に方策パラメータを更新することで、方策を更新する方策更新ステップとを備える。
【００１７】
この発明のさらに他の局面に従うと、対象とするシステムの時間発展が順方向マルコフ決定過程として記述される際に、システムの状態に対する制御則である確率的に表現される方策をシステムの状態量の観測により方策勾配法によって強化学習する制御方法をコンピュータに実行させるためのプログラムであって、方策に基づいて、システムを制御するための制御信号を生成する制御信号生成ステップと、システムの状態量を観測する状態量検知ステップと、状態と制御信号とに予め定められた関係で依存する報酬値を獲得する報酬値獲得ステップと、確率的な表現を規定するパラメータである方策パラメータにより方策が規定されるとき、各タイムステップにおける状態量と制御信号とに基づいて、システムの状態の分布の定常分布の対数の方策パラメータについての偏微分である対数定常分布偏微分を推定することで、方策の勾配を推定する方策勾配推定ステップと、報酬値と方策勾配推定ステップによる推定結果とに基づいて、対数定常分布偏微分に基づき表現される平均報酬の勾配の方向に方策パラメータを更新することで、方策を更新する方策更新ステップとを含む、制御方法をコンピュータに実行させる。
【発明を実施するための最良の形態】
【００１８】
以下の説明の構成の概要を説明すると、（１．本発明の概要）において、本発明の全体的な構成を説明し、（２．前提：方策勾配強化学習）では、従来のＰＧ法をレビューし、本発明のＬＳＤＧを評価する目的を概説する。（３．定常分布の対数の偏微分の推定）では、逆方向マルコフ連鎖の方法に基づく最小二乗ＴＤ法によるＬＳＤＧ（λ）アルゴリズムを説明する。（４.  ＬＳＤＧ推定による方策の更新）では、ＬＳＤＧ（λ）−ＰＧアルゴリズムを説明する。これは、ＬＳＤＧ（λ）を利用し、割引率γを用いない方法である。（５．数値計算の結果）では、提案する方法のパフォーマンスを確認するため、簡単なマルコフ決定過程（ＭＤＰ）における計算結果が示される。
【００１９】
（１．本発明の概要）
後に説明するように、本発明では、逆方向マルコフ連鎖の方法とＴＤ（temporal difference）学習アルゴリズムにより、定常分布の勾配としてのＬＳＤＧが導出される、新たな方策勾配法の枠組みを提案する。この枠組みにおいては、平均報酬の偏微分は、割引率γに依存せず、γ＝０とおくことにより、価値関数を学習する必要が無くなる。
【００２０】
以下、図面を参照して本発明の実施の形態について説明する。
以下の説明で明らかとなるとおり、本発明は、ロボット、プラント、移動機械（電車、自動車）などの制御問題として、幅広い応用を持つ。
【００２１】
ただし、以下では、本発明の具体的な適用例として、特に簡単なロボットの自動制御問題を対象とするものとして説明を行う。また、数値計算の結果は、さらに簡単なモデルに対する比較を示している。しかしながら、本発明は、このような応用に限定されるものではなく、より一般的に、対象システムの時間発展が複雑な場合の対象システムの制御に適用することができる。そのようなものの例としては、巨大プラント（溶鉱炉、原子力プラント）、マルチリンクロボット（ヒューマノイドロボット）、ノンホロノームシステム（宇宙ステーション）、地下鉄ホームでの人の流れなどがある。これらは、いずれも古典的制御法での制御が困難であり、かつ重要な制御対象である。
【００２２】
（１．本発明のシステム構成）
図１は、本発明の制御方法および制御プログラムが適用される制御器を用いたシステム１０００の一例を示す概念図である。
【００２３】
図１を参照して、システム１０００は、制御対象となる被制御装置２００と、この被制御装置２００に対して制御信号を与えるためのコンピュータ１００とを備える。
【００２４】
図１を参照してこのコンピュータ１００は、ＣＤ−ＲＯＭ（Compact Disc Read-Only Memory ）上の情報を読込むためのＣＤ−ＲＯＭドライブ１０８およびフレキシブルディスク（Flexible Disk、以下ＦＤ）１１６に情報を読み書きするためのＦＤドライブ１０６を備えたコンピュータ本体１０２と、コンピュータ本体１０２に接続された表示装置としてのディスプレイ１０４と、同じくコンピュータ本体１０２に接続された入力装置としてのキーボード１１０およびマウス１１２とを含む。
【００２５】
図２は、このコンピュータ１００の構成をブロック図形式で示す図である。
図２に示されるように、このコンピュータ１００を構成するコンピュータ本体１０２は、ＣＤ−ＲＯＭドライブ１０８およびＦＤドライブ１０６に加えて、それぞれバスＢＳに接続されたＣＰＵ（Central Processing Unit ）１２０と、ＲＯＭ（Read Only Memory) およびＲＡＭ （Random Access Memory）を含むメモリ１２２と、直接アクセスメモリ装置、たとえば、ハードディスク１２４と、被制御装置２００とデータの授受を行うための通信インタフェース１２８とを含んでいる。ＣＤ−ＲＯＭドライブ１０８にはＣＤ−ＲＯＭ１１８が装着される。ＦＤドライブ１０６にはＦＤ１１６が装着される。
【００２６】
被制御装置２００からは、コンピュータ１００に対して被制御装置２００の状態を示すパラメータ（状態量）の情報、たとえば、被制御装置２００の可動部分の位置、速度、加速度、角度、角速度等の情報が与えられる。一方、コンピュータ１００からは、被制御装置２００に対して、これら状態量を制御するための制御情報が制御信号として与えられる。
【００２７】
なお、ＣＤ−ＲＯＭ１１８は、コンピュータ本体に対してインストールされるプログラム等の情報を記録可能な媒体であれば、他の媒体、たとえば、ＤＶＤ−ＲＯＭ（Digital Versatile Disc）やメモリカードなどでもよく、その場合は、コンピュータ本体１０２には、これらの媒体を読取ることが可能なドライブ装置が設けられる。
【００２８】
本発明の制御器の主要部は、コンピュータハードウェアと、ＣＰＵ１２０により実行されるソフトウェアとにより構成される。一般的にこうしたソフトウェアはＣＤ−ＲＯＭ１１８、ＦＤ１１６等の記憶媒体に格納されて流通し、ＣＤ−ＲＯＭドライブ１０８またはＦＤドライブ１０６等により記憶媒体から読取られてハードディスク１２４に一旦格納される。または、当該装置がネットワークに接続されている場合には、ネットワーク上のサーバから一旦ハードディスク１２４にコピーされる。そうしてさらにハードディスク１２４からメモリ１２２中のＲＡＭに読出されてＣＰＵ１２０により実行される。なお、ネットワーク接続されている場合には、ハードディスク１２４に格納することなくＲＡＭに直接ロードして実行するようにしてもよい。
【００２９】
図１および図２に示したコンピュータのハードウェア自体およびその動作原理は一般的なものである。したがって、本発明の最も本質的な部分は、ＦＤ１１６、ＣＤ−ＲＯＭ１１８、ハードディスク１２４等の記憶媒体に記憶されたソフトウェアである。
【００３０】
なお、一般的傾向として、コンピュータのオペレーティングシステムの一部として様々なプログラムモジュールを用意しておき、アプリケーションプログラムはこれらモジュールを所定の配列で必要な時に呼び出して処理を進める方式が一般的である。そうした場合、当該制御器を実現するためのソフトウェア自体にはそうしたモジュールは含まれず、当該コンピュータでオペレーティングシステムと協働してはじめて制御器が実現することになる。しかし、一般的なプラットフォームを使用する限り、そうしたモジュールを含ませたソフトウェアを流通させる必要はなく、それらモジュールを含まないソフトウェア自体およびそれらソフトウェアを記録した記録媒体（およびそれらソフトウェアがネットワーク上を流通する場合のデータ信号）が実施の形態を構成すると考えることができる。
【００３１】
［制御方法の一般的説明］
以下、本発明の構成について、その理論的な構成をまず説明する。
【００３２】
（制御器の構成）
（２．前提：方策勾配強化学習）
以下では、マルコフ決定過程（ＭＤＰ）について考えることにし、制御対象（制御器の環境）は状態遷移確率（時刻ｔにおいて、状態ｘtであるときに行動（制御）ｕtを実行することで状態がｘt+1となる確率）と報酬関数ｒt+1＝ｒ（ｘt，ｕt）（なお、ｒt+1＝ｒ（ｘt＋１,ｘt，ｕt  ）の場合にも同様に議論できる）によって特徴づけられるものとする。なお、この報酬関数については、制御対象の制御目標に応じて予め定められているものとする。状態入力ｘ∈Ｘから行動出力ｕ∈Ｕへの写像を方策と呼び、以下で説明するように確率的に表現する。方策は、パラメータθで、規定される。
【００３３】
ここでは、従来のＰＧＲＬアルゴリズムをレビューし、本発明の新しいアルゴリズムの主たるアイデアを提示する。有限な状態Ｘ∋ｘの組と行動Ｕ∋ｕとを有する離散時間ＭＤＰは、以下の状態遷移確率ｐと報酬関数ｒ+1によって規定される。
【００３４】
【数１】
0004586129.tif 000002
【００３５】
ここで、記載の簡単のために、ｘ+1は、状態ｘにおいて、行動ｕにより与えられる次の状態であり、ｒ+1は、ｘ+1において観測された即時報酬である［非特許文献１０，非特許文献１１］。ｘ+kおよびｕ+kは、それぞれ、状態ｘからｋ時間ステップ先の状態および行動であり、添え字が−ｋとなっていれば、その反対である。（ＭＤＰにおける）決定は、θ∈Ｒdによりパラメータ化された以下の確率的方策πにしたがってなされる。
【００３６】
【数２】
0004586129.tif 000003
【００３７】
以下の方策πは、全てのｘ∈Ｘおよびｕ∈Ｕに対して、θについて微分可能であると仮定する。
【００３８】
【数３】
0004586129.tif 000004
【００３９】
さらに、以下のような仮定をおく。
（仮定１）
以下のような状態遷移確率ｐと確率的方策πとを有するマルコフ連鎖Ｍ（θ）は、全ての方策パラメータについてエルゴート的（既約で非周期的）である。
【００４０】
【数４】
0004586129.tif 000005
【００４１】
したがって、以下のただ１つの定常分布が存在する。
【００４２】
【数５】
0004586129.tif 000006
【００４３】
この定常分布は、初期状態には独立であって、以下の式を満たす。
【００４４】
【数６】
0004586129.tif 000007
【００４５】
ここで、以下の式が成り立つ。
【００４６】
【数７】
0004586129.tif 000008
【００４７】
ＰＲＧＬの目的は、以下の「平均報酬」と呼ばれる即時報酬の平均を最大化する方策パラメータθ＊を見いだすことである。
【００４８】
【数８】
0004586129.tif 000009
【００４９】
仮定１の下では、平均報酬は、初期状態ｘには独立で、以下の式に等しいことが示される［非特許文献１０］：
【００５０】
【数９】
0004586129.tif 000010
【００５１】
方策勾配ＲＬアルゴリズムは、方策パラメータθを、以下の式に示されるθについての平均報酬Ｒ（θ）の勾配の方向に更新する。
【００５２】
【数１０】
0004586129.tif 000011
【００５３】
以下、単に方策勾配（ＰＧ）と、しばしば呼ばれる。この方策勾配は、以下のように与えられる。
【００５４】
【数１１】
0004586129.tif 000012
【００５５】
以下の式に示される定常分布の対数の偏微分の導出は簡単ではない。
【００５６】
【数１２】
0004586129.tif 000013
【００５７】
そこで、従来のＰＧアルゴリズム［非特許文献１，非特許文献２］は、ＰＧのもう一つの表現を利用している。
【００５８】
【数１３】
0004586129.tif 000014
【００５９】
ここで、割引率γ∈［０，１）で、それぞれ、行動価値関数Ｑと状態価値関数Ｖとは以下のように表される［非特許文献１１］。
【００６０】
【数１４】
0004586129.tif 000015
【００６１】
式（４）の第２項の寄与は、γが１に近づくにつれて小さくなるので［非特許文献１］、従来のアルゴリズム［非特許文献１，非特許文献２］は、γ〜１とすることで、第１項のみからＰＧを近似している。このような省略による偏りは、割引率γを1に近づければ小さくなるが、推定の分散は多くなってしまう。
【００６２】
ここで、本発明では、もう１つのアプローチを提案する。そこでは、以下の式の定常分布の対数の偏微分（ＬＳＤＧ）を推定し、ＰＧを導出するために式（３）を用いる。
【００６３】
【数１５】
0004586129.tif 000016
【００６４】
著しい特徴は、価値関数を学習する必要がなく、したがって、そのアルゴリズムは、割引率γの選択において、偏りと分散のトレードオフと関係がないことである。
（３．定常分布の対数の偏微分の推定）
以下では、最小二乗法に基づくＬＳＤＧ推定アルゴリズム、ＬＳＤＧ（λ）を提案する。この目的のために、エルゴート的なマルコフ連鎖Ｍ（θ）の逆過程を定式化し、ＬＳＤＧは、ＴＤ法［非特許文献１２，非特許文献１３，非特許文献１４］の枠組みで推定できることを示す。
（３．１  順方向および逆方向マルコフ連鎖の性質）
ベイズの理論を用いれば、現在の状態から過去の状態および行動の対への逆方向の確率は、以下の式で表される。
【００６５】
【数１６】
0004586129.tif 000017
【００６６】
以下の事後確率ｑは事前分布ｐに依存する。
【００６７】
【数１７】
0004586129.tif 000018
【００６８】
以下のように、事前分布ｐが定常分布ｄと方策πに従うとき、事後分布ｑは、定常逆方向確率と呼ばれ、下付添え字Ｂ（θ）が加えられる。
【００６９】
【数１８】
0004586129.tif 000019
【００７０】
マルコフ連鎖―Ｍ（θ）とＢ（θ）の両方―は、以下の２つの定理において記述されるように密接に関連している。
（定理１）
【００７１】
【数１９】
0004586129.tif 000020
【００７２】
（証明）
式（５）の両辺に以下の定常分布をかける。
【００７３】
【数２０】
0004586129.tif 000021
【００７４】
すると、全ての可能な行動ｕ-1∈Ｕについて総和をとると、以下の式が得られる：
【００７５】
【数２１】
0004586129.tif 000022
【００７６】
そして、式（７）の両辺を可能な状態ｘ∈Ｘについて総和をとると、以下の式が成り立つ。
【００７７】
【数２２】
0004586129.tif 000023
【００７８】
このことは、以下の２点を成立させる．（ｉ）Ｂ（θ）は、Ｍ（θ）と同一の定常分布を有すること、（ｉｉ）Ｂ（θ）はＭ（θ）と同じ既約な性質を有すること。
【００７９】
【数２３】
0004586129.tif 000024
【００８０】
このことは、（ｉｉｉ）Ｂ（θ）がＭ（θ）と同じ非周期的な性質をもっていることを示唆する。式（６）は、（ｉ）−（ｉｉｉ）により直接証明される［非特許文献１５］。
（定理２）
【００８１】
【数２４】
0004586129.tif 000025
【００８２】
（証明）
マルコフ連鎖の特性と式（５）を代入することにより、以下の関係が得られる。
【００８３】
【数２５】
0004586129.tif 000026
【００８４】
このことは、有限のＫの場合において式（８）が成立することを証明する。定理１から以下の式が導かれるので、式（８）のＫ→∞の極限の場合も成立することが、すぐさま証明される。
【００８５】
【数２６】
0004586129.tif 000027
【００８６】
定理１および定理２は、これらが、定常分布に収束する状態分布の下で、順方向マルコフ連鎖Ｍ（θ）からのサンプルは、そのまま、逆方向マルコフ連鎖Ｂ（θ）に関する推定に使用できることになるので、重要である。そして、これらは、後に利用されうるものである。
（３．２  逆方向から順方向のマルコフ連鎖のＬＳＤＧのためのＴＤ（Temporal Difference）学習法）
ＬＳＤＧは式（５）を用いて、以下のように分解される。
【００８７】
【数２７】
0004586129.tif 000028
【００８８】
式（１０）は、状態ｘのＬＳＤＧは、以下の式で表される方策の対数の偏微分の状態ｘから逆方向マルコフ連鎖Ｂ（θ）の無限区間の集積であることを暗示している。
【００８９】
【数２８】
0004586129.tif 000029
【００９０】
式（９）および（１０）から、ＬＳＤＧは、Ｍ（θ）よりもむしろ逆方向マルコフ連鎖Ｂ（θ）についての、以下のような逆方向ＴＤ  δに関するＴＤ学習[非特許文献１２]により推定されうる。
【００９１】
【数２９】
0004586129.tif 000030
【００９２】
ここで、最初の２つの項は、Ｂ（θ）における方策の対数の偏微分の１ステップ前の実際の観測値と１ステップ前のＬＳＤＧであり、現在の状態のＬＳＤＧが最後の項である。
【００９３】
【数３０】
0004586129.tif 000031
【００９４】
適格度減衰率λ∈［０，１］と逆方向追跡時間ステップＫ∈Ｎを用いて、式（１０）は、以下のように一般化される。
【００９５】
【数３１】
0004586129.tif 000032
【００９６】
上記のような設定でなくとも、大きなλやＫを用いたならば、このような最小化は従来の価値関数に対するＴＤ（λ）学習の場合のように、非マルコフ効果に対しては、より敏感ではない［非特許文献１６］。
【００９７】
【数３２】
0004586129.tif 000033
【００９８】
理論的な仮定と現実への適用との間のギャップを埋めるために、以下の２つのうちのいずれかの戦略をとる必要がある。（ｉ）λ〜１ならば、Ｋは、あまり大きな整数に設定しない、（ｉｉ））Ｋ〜ｔならば、λは、１に設定しない、ここで、ｔは、現実の順方向マルコフ連鎖の現在のタイムステップである。
（３．３  ＬＳＤＧ推定アルゴリズム：制限付き逆方向ＴＤ（λ）の最小二乗法）
【００９９】
【数３３】
0004586129.tif 000034
【０１００】
この３．３では、最小二乗法に基づく［非特許文献１７，非特許文献１３，非特許文献１４］、ＬＳＤＧ推定アルゴリズム、ＬＳＤＧ（λ）を提案する。これは、同時に、平均二乗を減少させるとともに、制約条件を満足することを達成しようとするものである。
【０１０１】
【数３４】
0004586129.tif 000035
【０１０２】
したがって、最小化すべき対象となる関数は、以下の式（１３）となる。
【０１０３】
【数３５】
0004586129.tif 000036
【０１０４】
ここで、右辺の第２項は、式（１２）の制約条件のためのものである。したがって、式（１３）の偏微分は、以下のようになる。
【０１０５】
【数３６】
0004586129.tif 000037
【０１０６】
一般的なＲＬ問題では、このような相関が存在するので、このような偏りを除くために、操作変数法（instrumental variable method）を適用する［非特許文献１７，非特許文献１３］。
【０１０７】
【数３７】
0004586129.tif 000038
【０１０８】
以下では、現実のマルコフ連鎖Ｍ（θ）における時間ステップｔの状態を示すために、ノーテーションをｘｔに変更する。提案するＬＳＤＧ推定アルゴリズム、ＬＳＤＧ（λ）は、適格性減衰率λ∈［０，１）の下で、逆方向にさかのぼる時間ステップＫを現在の状態ｘｔのタイムステップｔと同じにする。すなわち、以下が成り立つ。
【０１０９】
【数３８】
0004586129.tif 000039
【０１１０】
図３は、ＬＳＤＧ（λ）を求める手順をアルゴリズム１として示す図である。
【０１１１】
【数３９】
0004586129.tif 000040
【０１１２】
また、図４は、アルゴリズム１を示すフローチャートである。
図４を参照して、まず、ステップ１００において、処理の前提として、以下の設定がなされる。
【０１１３】
【数４０】
0004586129.tif 000041
【０１１４】
続いて、初期化処理として、以下の処理が行われる（ステップＳ１０２）。
【０１１５】
【数４１】
0004586129.tif 000042
【０１１６】
時間ステップｔがｔ＝０とされ（ステップＳ１０４）、以下の処理が、ｔ＝０からｔ＝Ｔ−１まで繰り返される（ステップＳ１０６〜Ｓ１１６）。
【０１１７】
まず、ステップＳ１０６においてｔ＝０であれば、初期状態が観測され（ステップＳ１０８）、続いて、以下の設定が行われる（Ｓ１１０）。
【０１１８】
【数４２】
0004586129.tif 000043
【０１１９】
一方、ステップＳ１０６において、ｔが０でなければ、以下の処理が行われる（ステップＳ１１２）。
【０１２０】
【数４３】
0004586129.tif 000044
【０１２１】
ステップＳ１１０またはＳ１１２に続いて、以下の計算が行われる（ステップＳ１１４）。
【０１２２】
【数４４】
0004586129.tif 000045
【０１２３】
ステップＳ１１６にて、ｔがＴよりも小さければ処理はステップＳ１０６に復帰し、ｔがＴ以上であれば、処理はステップＳ１１８に移行して、以下の計算を行う。
【０１２４】
【数４５】
0004586129.tif 000046
【０１２５】
続いて、以下の計算によりＬＳＤＧの推定値を得る。
【０１２６】
【数４６】
0004586129.tif 000047
【０１２７】
（４.  ＬＳＤＧ推定による方策の更新）
ここでは、上述したＬＳＤＧ推定に基づくＰＧＲＬアルゴリズムを定義する。
【０１２８】
【数４７】
0004586129.tif 000048
【０１２９】
方策パラメータは、適切なステップサイズαの確率的勾配法により更新される。
【０１３０】
【数４８】
0004586129.tif 000049
【０１３１】
ここで、：＝は、右辺を左辺に代入することを示す。
図５は、ＬＳＤＧ（λ）-ＰＧを、ＬＳＤＧ（λ）を利用した、ＰＧアルゴリズムについての最も簡単な実現法の１つとして、アルゴリズム２として示す図である。ここで、減衰率パラメータβ∈［０，１）は、古いθの値により与えられる過去の推定を捨てていくために導入されている。
【０１３２】
関数近似器によるＬＳＤＧ推定は他の重要な内容を構成する。すなわち、特に、連続状態問題において、基底関数φ（ｘ）をいかにして設定するか、ということである。
【０１３３】
【数４９】
0004586129.tif 000050
【０１３４】
したがって、以下のような定理が有用である。
（定理３）
【０１３５】
【数５０】
0004586129.tif 000051
【０１３６】
（証明）
以下の式により証明される。
【０１３７】
【数５１】
0004586129.tif 000052
【０１３８】
図６は、図５に対応するフローチャートである。
図６を参照して、まず、ステップ２００において、処理の前提として、以下の設定がなされる。
【０１３９】
【数５２】
0004586129.tif 000053
【０１４０】
続いて、初期化処理として、以下の処理が行われる（ステップＳ２０２）。
【０１４１】
【数５３】
0004586129.tif 000054
【０１４２】
時間ステップｔがｔ＝０とされ（ステップＳ２０４）、以下の処理が、ｔ＝０からｔ＝Ｔ−１まで繰り返される（ステップＳ２０６〜Ｓ２１６）。
【０１４３】
まず、ステップＳ２０６においてｔ＝０であれば、初期状態が観測され（ステップＳ２０８）、続いて、以下の設定が行われる（Ｓ２１０）。
【０１４４】
【数５４】
0004586129.tif 000055
【０１４５】
一方、ステップＳ２０６において、ｔが０でなければ、以下の処理が行われる（ステップＳ２１２）。
【０１４６】
【数５５】
0004586129.tif 000056
【０１４７】
ステップＳ２１０またはＳ２１２に続いて、以下の計算が行われる（ステップＳ２１４）。
【０１４８】
【数５６】
0004586129.tif 000057
【０１４９】
ステップＳ１１６にて、ｔがＴよりも小さければ処理はステップＳ２０６に復帰し、ｔがＴ以上であれば、処理はステップＳ２２０に移行して、以下の計算を行うことで、方策がアップデートされる。
【０１５０】
【数５７】
0004586129.tif 000058
【０１５１】
図７は、本発明の制御器の構成の概念図である。
本発明の制御器は、行動、すなわち、制御信号を制御対象に与える処理を行って、制御対象の状態量を観測器（たとえば、位置センサ、角度センサ、加速度センサ、角加速度センサなど）で観測し、この観測結果により「定常分布の対数の偏微分」（ＬＳＤＧ）を推定し、方策パラメータを更新し、これにより方策を更新する。そして、更新された方策により、さらに、制御対象が制御される。
（５．数値計算の結果）
有限のグリッドの組Ｘ＝｛１，…、ｍ｝と２つの可能な行動Ｕ＝｛Ｌ，Ｒ｝（左（Ｌ）または右（Ｒ）への１グリッド分の運動）を有している「１次元トーラス状グリッド空間」において、われわれが提案したアルゴリズムのパフォーマンスを検証した。これは、典型的なｍ状態ＭＤＰタスクであり、状態の遷移確率は以下のように与えられる。
【０１５２】
【数５８】
0004586129.tif 000059
【０１５３】
ここで、ｘ＝０およびｘ＝ｍ（ｘ＝１およびｘ＝ｍ＋１）とは、同じ状態であり、ｐi∈［０，１］（ｉ＝１，…，ｍ）は、タスクに依存する定数である。われわれの数値計算では、確率的方策は、以下のようなシグモイダル関数で表される：
【０１５４】
【数５９】
0004586129.tif 000060
【０１５５】
ここで、状態特徴ベクトルφ（１），…，φ（ｍ）∈Ｒｍの全ての要素は、定常正規分布Ｎ（０，１２）からシミュレーションごとに独立に取り出された。これは、確率的方策のパラメータ化がいかにして、われわれのアルゴリズムのパフォーマンスに影響を与えるかを検証するためであった。状態特徴ベクトルφ（ｘ）は、ＬＳＤＧ推定のための基底関数としても使用された。各シミュレーションは、１０５タイムステップ以上からなる１つのエピソードを実行した。
【０１５６】
まず、われわれは、問題設定や方策パラメータθに関わりなく、ＬＳＤＧ（λ）がどれぐらい正確に以下の「定常分布の対数の偏微分」（ＬＳＤＧ）を推定しているのかを検証した。
【０１５７】
【数６０】
0004586129.tif 000061
【０１５８】
この目的を達成するために、タスク依存の定数ｐ1，…，ｐmは、区間［０．７，１］の均一な分布から独立に選ばれ、各シミュレーションでは固定された。方策パラメータθは、正規分布Ｎ（０，０．５2）に従ってランダムに選択され、各シミュレーションでは固定された。
【０１５９】
図８は、ｍ＝３のときに、推定されたＬＳＤＧの典型的な時間経過を示す図である。ここでは、９の異なった色が、ＬＳＤＧの異なった要素を示している。実線は、ＬＳＤＧ（０）により推定された値を示し、点線は、ＬＳＤＧの解析的な解を示している。
【０１６０】
図８に示すように、ＬＳＤＧ（０）による推定は、ｍ＝３の場合は約１００回のタイムステップで解析的な解に収束している。
【０１６１】
７状態タスクを用いて、適格性減衰率λの影響を調べた。異なった設定についての平均的なパフォーマンスを評価するために、以下で定義される「相対誤差」基準を採用した。
【０１６２】
【数６１】
0004586129.tif 000062
【０１６３】
ここで、Ω＊は定理３において定義された最適パラメータであり、解析的に計算された。図９および図１０は、λ＝０，０．３，０．９および１について、相対誤差の２００シミュレーションについての平均の時間推移を示している。これら２つの図の間の相違は、ただ、特徴ベクトルφ（ｘ）の要素の数だけである。
【０１６４】
図９において使用される特徴ベクトルφ（ｘ）∈Ｒ７は、適切なものであり、異なった状態を区別するのに十分であった一方、図１０において使用される特徴ベクトルφ（ｘ）∈Ｒ６は、適切でない。これらの結果は、理論的な予想と合致するものである。つまり、もしも基底関数が適切であれば（図９）、λ＝１以外の任意の値にλを設定できるのに対して、そうでないときは、λ＝１以外の大きな値にλを設定する必要がある（図１０）。
【０１６５】
最後に、ＬＳＤＧ（λ）―ＰＧを他の従来からのＰＧ法とを、３状態タスクにおいて比較した。ここで、状態遷移確率は、全てのｉ∈｛１，２，３｝についてｐi＝１に設定された。
【０１６６】
図１１は、このタスクにおける報酬の設定を示す図である。ここでは、２種類の報酬がある。定数“ｒ＝（±）２”と変数“ｒ＝（±）ｓ”である。変数ｓは、各シミュレーションにおいて、区間［０．８，１）での均一分布からランダムに設定された。報酬ｓは、最適方策を見いだすためのγの最小値を以下のように規定していることに注意されたい：
【０１６７】
【数６２】
0004586129.tif 000063
【０１６８】
したがって、γの設定は重要であり、このタスクにおいては困難である。従来のＰＧ法のパフォーマンスのベースラインとして、２つのアルゴリズムを採用した：ＧＰＯＭＤＰ［非特許文献１］とKondaのactor-critic法とである［非特許文献５］。
【０１６９】
図１２は、１００回のシミュレーションについての３つの方法の平均のパフォーマンスを示す図である。エラーバーは１００回についての標準偏差を示す。ここでは、パフォーマンスは、３Ｒ（θ）／（２−２ｓ）により評価された。すなわち、平均の報酬がその上限値である（２−２ｓ）／３により正規化されている。結果はＬＳＤＧ（λ）−ＰＧ法は他の方法よりもパフォーマンスが優れていることを示している。
【０１７０】
以上説明したように、本発明では、現実の順方向および逆方向のマルコフ連鎖は密接に関連しており、定理において共通の性質を有することを利用している。これらを用いて、定常分布の対数の偏微分（ＬＳＤＧ）を推定するアルゴリズムとしてＬＳＤＧ（λ）を、ＬＳＤＧ推定を用いたＰＧアルゴリズムとしてＬＳＤＧ（λ）―ＰＧを提案した。実験結果はＬＳＤＧ（λ）は、適格性減衰率λ∈［０，１）で動作することができ、かつ、ＬＳＤＧ（λ）−ＰＧは、割引率γとは独立に学習をすることができる。
【０１７１】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【図面の簡単な説明】
【０１７２】
【図１】本発明の制御方法および制御プログラムが適用される制御器を用いたシステム１０００の一例を示す概念図である。
【図２】コンピュータ１００の構成をブロック図形式で示す図である。
【図３】ＬＳＤＧ（λ）を求める手順をアルゴリズム１として示す図である。
【図４】アルゴリズム１を示すフローチャートである。
【図５】ＬＳＤＧ（λ）-ＰＧを示す図である。
【図６】図５に対応するフローチャートである。
【図７】本発明の制御器の構成の概念図である。
【図８】ｍ＝３のときに、推定されたＬＳＤＧの典型的な時間経過を示す図である。
【図９】ｍ＝７のときに、十分な特徴ベクトルを用いて推定されたＬＳＤＧの相対誤差の時間経過を示す図である。
【図１０】ｍ＝７のときに、不十分な特徴ベクトルを用いて推定されたＬＳＤＧの相対誤差の時間経過を示す図である。
【図１１】タスクにおける報酬の設定を示す図である。
【図１２】１００回のシミュレーションについての３つの方法の平均のパフォーマンスを示す図である。
【符号の説明】
【０１７３】
１００  コンピュータ、１０２  コンピュータ本体、１０４  ディスプレイ、１０６  ＦＤドライブ、１０８  ＣＤ−ＲＯＭドライブ、１１０  キーボード、１１２  マウス、１１８  ＣＤ−ＲＯＭ、１２０  ＣＰＵ、１２２  メモリ、１２４  ハードディスク、１２８  通信インタフェース、２００  被制御装置、１０００  システム。
【図１】
0004586129.tif 000064
【図２】
0004586129.tif 000065
【図３】
0004586129.tif 000066
【図４】
0004586129.tif 000067
【図５】
0004586129.tif 000068
【図６】
0004586129.tif 000069
【図７】
0004586129.tif 000070
【図１１】
0004586129.tif 000071
【図８】
0004586129.tif 000072
【図９】
0004586129.tif 000073
【図１０】
0004586129.tif 000074
【図１２】
0004586129.tif 000075