(57)【特許請求の範囲】
【請求項１】
行動によって遷移する一連の状態と各状態での行動とを表す訓練行動列からなる集合、および、前記訓練行動列それぞれの適切さを表す訓練順序評価値の集合を記憶する訓練行動列記憶部と、
状態に対する報酬値を求める報酬関数を用い、前記訓練行動列が表す一連の状態の報酬値に対応する順序評価値を得る訓練行動列評価部と、
前記順序評価値の集合と前記訓練順序評価値の集合との相違に基づいて前記報酬関数を更新する報酬関数調整部と、
を有する報酬関数推定装置。
【請求項２】
請求項１の報酬関数推定装置であって、
所定の終了条件が満たされるまで、前記訓練行動列評価部による処理および前記報酬関数調整部による処理が繰り返され、
前記報酬関数調整部は、前記所定の終了条件が満たされた場合に前記報酬関数を表す情報を出力する、
ことを特徴とする報酬関数推定装置。
【請求項３】
請求項１または２の報酬関数推定装置であって、
前記訓練順序評価値のそれぞれは、前記訓練行動列からなる集合に属する２個の訓練行動列からなる組に対応し、当該組をなす２個の訓練行動列のうちいずれのほうが適切であるかを表し、
前記順序評価値のそれぞれは、前記訓練行動列からなる集合に属する２個の訓練行動列からなる組に対応し、当該組をなす２個の訓練行動列のうちいずれに対応する前記報酬値または当該報酬値の期待値のほうが高い評価を表すかを表す、
ことを特徴とする報酬関数推定装置。
【請求項４】
請求項３の報酬関数推定装置であって、
前記訓練行動列評価部は、
前記訓練行動列が表す一連の状態の初期状態と同じ状態から行動によって遷移する一連の状態と各状態での行動とを表す行動列の集合から、前記報酬関数によって得られる前記一連の状態の報酬値の合計が最大となる行動列を選択し、当該報酬値の合計が最大となる行動列を当該訓練行動列に対応する最適行動列とし、
前記報酬関数を用いて得られる、前記訓練行動列が表す一連の状態の報酬値の和と当該訓練行動列に対応する前記最適行動列が表す一連の状態の報酬値の和との差、または、前記訓練行動列が表す一連の状態の報酬値の期待値の総和と当該訓練行動列に対応する前記最適行動列が表す一連の状態の報酬値の期待値の総和との差を、前記訓練行動列のシステム評価値として得、
前記組をなす２個の訓練行動列に対応する２個のシステム評価値の大小関係を表す前記順序評価値を得る、
ことを特徴とする報酬関数推定装置。
【請求項５】
請求項４の報酬関数推定装置であって、
前記報酬関数は、前記状態とベクトルである報酬関数パラメータとに対応し、
前記訓練順序評価値のそれぞれは、前記組をなす前記２個の訓練行動列の一方が他方よりも適切である場合に正値であり、当該他方が当該一方よりも適切である場合に負値であり、当該一方と当該他方との適切さが等しい場合にゼロ値であり、
前記順序評価値のそれぞれは、前記組をなす前記２個の訓練行動列の前記一方に対応するシステム評価値が前記他方に対応するシステム評価値よりも大きい場合に正値であり、当該一方に対応するシステム評価値が当該他方に対応するシステム評価よりも小さい場合に負値であり、当該一方に対応するシステム評価値と当該他方に対応するシステム評価とが等しい場合にゼロ値であり、
前記報酬関数調整部は、前記訓練順序評価値と前記順序評価値との正負が異なる前記組をなす前記２個の訓練行動列の前記一方に対応するシステム評価値から前記他方に対応するシステム評価値を減じた値の前記報酬関数パラメータでの偏微分値と、当該正負が異なる前記組をなす前記２個の訓練行動列に対応する前記訓練順序評価値と、の乗算値の総和に対応する更新ベクトルを得、当該更新ベクトルによって前記報酬関数パラメータを更新することで前記報酬関数を更新する、
ことを特徴とする報酬関数推定装置。
【請求項６】
請求項４の報酬関数推定装置であって、
前記報酬関数は、前記状態に対応するベクトルとベクトルである報酬関数パラメータとに対応し、
前記訓練順序評価値のそれぞれは、前記組をなす前記２個の訓練行動列の一方が他方よりも適切である場合に正値であり、当該他方が当該一方よりも適切である場合に負値であり、当該一方と当該他方との適切さが等しい場合にゼロ値であり、
前記順序評価値のそれぞれは、前記組をなす前記２個の訓練行動列の前記一方に対応するシステム評価値が前記他方に対応するシステム評価値よりも大きい場合に正値であり、当該一方に対応するシステム評価値が当該他方に対応するシステム評価よりも小さい場合に負値であり、当該一方に対応するシステム評価値と当該他方に対応するシステム評価とが等しい場合にゼロ値であり、
前記報酬関数調整部は、前記訓練順序評価値と前記順序評価値との正負が異なる前記組をなす前記２個の訓練行動列の前記一方に対応するシステム評価値から前記他方に対応するシステム評価値を減じた値の前記報酬関数パラメータでの偏微分値と、当該正負が異なる前記組をなす前記２個の訓練行動列に対応する前記訓練順序評価値と、の乗算値の総和に対応する更新ベクトルを得、
前記訓練行動列が表す一連の状態のそれぞれに対応するベクトルの総和から、当該訓練行動列に対応する最適行動列が表す一連の状態のそれぞれに対応するベクトルの総和を減じて得られるベクトルの総和に対応する逆強化学習ベクトルを得、
前記更新ベクトルおよび前記逆強化学習ベクトルによって前記報酬関数パラメータを更新することで前記報酬関数を更新する、
ことを特徴とする報酬関数推定装置。
【請求項７】
訓練行動列記憶部と訓練行動列評価部と報酬関数調整部とを有する報酬関数推定装置が実行する報酬関数推定方法であって、
行動によって遷移する一連の状態と各状態での行動とを表す訓練行動列からなる集合、および、前記訓練行動列それぞれの適切さを表す訓練順序評価値の集合が前記訓練行動列記憶部に格納されており、
前記訓練行動列評価部で、状態に対する報酬値を求める報酬関数を用い、前記訓練行動列が表す一連の状態の報酬値に対応する順序評価値を得、
前記報酬関数調整部で、前記順序評価値の集合と前記訓練順序評価値の集合との相違に基づいて前記報酬関数を更新する、
ことを特徴とする報酬関数推定方法。
【請求項８】
請求項１から６のいずれかの報酬関数推定装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、強化学習問題において行動列（ある状態とその状態に対する行動のペアの連なり）と行動列に付与された評価（あるタスクに対する行動列の適切さを表す指標）に基づき、評価の高い行動列を再現するための報酬関数を推定する報酬関数推定装置、方法、プログラムに関する。
【背景技術】
【０００２】
報酬関数に基づき意思決定を行う手法として、強化学習と呼ばれる手法（非特許文献１，２参照）が知られている。強化学習とは、ある環境内におけるエージェントが、現在の「状態」を観測し、取るべき「行動」を決定する問題を扱う機械学習の一種を意味する。強化学習では、例えばある環境中で自律的に行動するロボットシステムが環境から得られる「状態」に応じて、「報酬」が最大になるような「行動」を選択していくという問題を扱う。すなわち強化学習では、達成させたい「タスク」に応じて「報酬」を設計することで、システムの行動を設計することができる。なお報酬関数とは、入力された「状態」に対応する「報酬」を出力する関数を意味する。具体例を挙げる。例えば「穴が開いてるGridに切られた世界（Gridworld）で、エージェントが穴に落ちないように、ゴールまで最短距離で移動する」という「タスク」を想定する。このようなタスクのための報酬関数の一例は、穴という「状態」に対して-100という「報酬」を出力し、ゴールという「状態」に対して+100という「報酬」を出力し、それ以外の位置という「状態」に対して-1という「報酬」を出力する関数である。
【０００３】
従来、プログラムの設計者はこの報酬関数をあらかじめ適切に設計しておく必要があった。しかし、特定の望ましい行動をシステムに取らせたい場合に報酬関数をどのように設定すればよいかは、人のヒューリスティックな知識に依存し、難しい問題であった（非特許文献３参照）。
【０００４】
この問題を解決し、所与の行動列を再現する報酬関数を推定する方法として、逆強化学習に基づく報酬関数推定手法（非特許文献４，５参照）が知られている。これらの手法では、適当な報酬関数を用いて所与の行動列が再現されるかどうかをシミュレーションによってテストし、所与の行動列と異なる行動が選択された場合に報酬関数のパラメータを修正して再度テストすることを繰り返し、適切な報酬関数を推定する。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Jason D. Williams. Applying POMDPs to dialog systems in the troubleshooting domain, In Workshop on Bridging the Gap, pp. 1-8, Rochester, New York, 2007. Association for Computational Linguistics.
【非特許文献２】Toyomi Meguro, Ryuichiro Higashinaka, Yasuhiro Minami, and Kohji Dohsaka. Controlling Listening-oriented Dialogue using Partially Observable Markov Decision Processes. In Coling, 2010.
【非特許文献３】A. Boularias, H.R. Chinaei, and B. Chaib-draa. Learning the Reward Model of Dialogue POMDPs from Data. NIPS 2010 Workshop on Machine Learning for Assistive Technologies (MLAT-2010), pp. 1-9, 2010.
【非特許文献４】Pieter Abbeel and Andrew Y. Ng. Apprenticeship learning via inverse reinforcement learning. Twenty-first international conference on Machine learning - ICML'04, 2004.
【非特許文献５】B.D. Ziebart, Andrew Maas, J.A. Bagnell, and A.K. Dey. Maximum entropy inverse reinforcement learning. In Proc. AAAI, pp. 1433-1438, 2008.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献４，５では、与えられた行動列が全て正しく、再現すべき対象であるという前提で報酬関数の推定が行われる。しかし、実際の行動列はそれぞれタスクに対する適切さが異なっている。例えば、人を説得する対話（状態：対話相手の発言，行動：説得するための発話）や、けん玉のコントロール（状態：けん玉の位置・自分の腕位置など，行動：腕・手関節制御信号）などの行動列の場合、タスクを失敗した不適切な行動列も再現対象の行動列に含まれ得る。これらを同一の適切さを持つ行動列として報酬関数を推定すると、不適切な行動列を生成した報酬関数を含んだ報酬関数が推定されてしまう。また、適切な行動列のみを人手で選んで非特許文献４，５の入力とした場合には、今度は学習データサイズが減ってしまう。そのような場合、対応する学習データが存在しない「状態」および「行動」が増えてしまう。これにより、何らかの原因でそうした「行動」を取らざるを得ない「状態」に置かれた場合、この欠損によって致命的な行動を回避できないという問題が発生する。
【０００７】
本発明はこのような点に鑑みてなされたものであり、従来よりも適切な報酬関数を推定することが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明では、行動によって遷移する一連の状態と各状態での行動とを表す訓練行動列からなる集合、および、訓練行動列それぞれの適切さを表す訓練順序評価値の集合が格納されており、状態に対する報酬値を求める報酬関数を用い、訓練行動列が表す一連の状態の報酬値に対応する順序評価値を得、順序評価値の集合と訓練順序評価値の集合との相違に基づいて報酬関数を更新する。
【発明の効果】
【０００９】
本発明では、報酬関数を用いて得られる訓練行動列の順序評価値と訓練行動列の訓練順序評価値との相違に基づいて報酬関数を推定する。そのため、訓練行動列の適切さを考慮して報酬関数を推定でき、従来よりも適切に報酬関数を推定できる。
【図面の簡単な説明】
【００１０】
【図１】実施形態の補修関数推定装置の機能構成を例示するブロック図。
【図２】実施形態の補修関数推定方法を例示するフロー図。
【図３】シミュレーション方法を説明するための図。
【図４】シミュレーション結果を説明するための図。
【発明を実施するための形態】
【００１１】
以下、図面を参照して本発明の実施形態を説明する。
図１に例示するように、本形態の報酬関数推定装置１は、訓練行動列記憶部１１、状態遷移計算部１２、行動評価部１３、行動決定部１４、訓練行動列評価部１５、報酬関数調整部１６、および制御部１７を有する。報酬関数推定装置１は、例えば、公知または専用のコンピュータに所定のプログラムが読み込まれることで構成される特別な装置である。あるいは例えば、報酬関数推定装置１を構成する各部の少なくとも一部がハードウェアによって構成されてもよい。報酬関数推定装置１は、制御部１７による制御に従って各処理を実行する。学習時には、例えば、訓練行動列記憶部１１、状態遷移計算部１２、行動評価部１３、行動決定部１４、訓練行動列評価部１５、および報酬関数調整部１６によって、適切な報酬関数を推定する。実行時には、例えば、状態遷移計算部１２、行動評価部１３、および行動決定部１４によって適切な行動を得る。
【００１２】
＜事前処理＞
訓練行動列記憶部１１には、入力された複数の訓練行動列からなる集合、および、訓練行動列それぞれの適切さを表す訓練順序評価値の集合が格納される。訓練行動列のそれぞれは、例えば、ある状態とその状態に対する行動のペアの連なりであり、行動によって遷移する一連の状態と各状態での行動とを表す。訓練行動列の具体例は、行動によって遷移する一連の状態のそれぞれを表す値の列と当該各状態を表す値の列とからなる。
【００１３】
訓練順序評価値のそれぞれは、例えば、訓練行動列からなる集合に属する２個の訓練行動列からなる組に対応し、当該組をなす２個の訓練行動列のうちいずれのほうが適切であるかを表す。この例の訓練順序評価値は、訓練行動列からなる集合に属する２個の訓練行動列からなる組（ペア）ごとに付与される。すなわち、Ｎ個（Ｎ≧２）の訓練行動列からなる集合はＮ（Ｎ−１）／２個のペアを含むため、例えばＮ（Ｎ−１）／２個の訓練順序評価値が付与される。具体的には、例えば各訓練行動列のペアζ*i，ζ*jに対し、それぞれ、どちらが適切であるかを表す以下の訓練順序評価値ｏ*i，ｊが付与される。
【数１】
0005815458.tif 000002
以下では訓練行動列をζ*と総称し、訓練順序評価値をｏ*と総称する。
【００１４】
報酬関数の推定のためには、いずれの訓練行動列のほうが適切であるかを相対評価できればよく、数値で訓練行動列を評価する必要はない。上記のようなペアごとの訓練順序評価値を用いるほうが、実数の訓練順序評価値（例えば、ある発言に対する否定が-1.4，肯定が+0.3など）を用いるよりも取り扱いが容易となる。また、学習時に訓練行動列ごとに改めて順序評価する必要はない。
【００１５】
＜報酬関数推定処理＞
訓練行動列からなる集合および訓練順序評価値の集合を用い、報酬関数の推定を行う処理を説明する。
図２に例示するように、まず制御部１７がループ数に対応する変数ｓｔｅｐを０に初期化する（ステップＳ１０）。次に報酬関数調整部１６が、初期の報酬関数のパラメータ（以下「報酬関数パラメータ」という）θ０を設定する（ステップＳ１１）。本形態の報酬関数パラメータは、実数を要素とするＭ次元ベクトルである（Ｍは１以上の整数）。初期の報酬関数のパラメータθ０は、ランダムに選択された要素からなるＭ次元ベクトルであってもよいし、予め定められた要素からなるＭ次元ベクトルであってもよい。
【００１６】
その後、報酬関数推定装置１は、以下のループに従って報酬関数パラメータθｓｔｅｐを逐次的に更新する。
まず訓練行動列評価部１５が、現在の報酬関数パラメータθｓｔｅｐに基づいて、訓練行動列記憶１１から読み出した訓練行動列ζ*の集合を評価し、訓練行動列ζ*の集合に対応する順序評価値の集合を得て出力する。すなわち訓練行動列評価部１５は、報酬関数パラメータθｓｔｅｐに対応する報酬関数を用い、各訓練行動列ζ*が表す一連の状態の報酬値に対応する順序評価値を得て、当該順序評価値の集合を出力する。例えば順序評価値のそれぞれは、訓練行動列ζ*からなる集合に属する２個の訓練行動列ζ*i，ζ*jからなる組（ペア）に対応し、当該組をなす２個の訓練行動列ζ*i，ζ*jのうちいずれに対応する報酬値または当該報酬値の期待値のほうが高い評価を表すかを表す。この場合、Ｎ個の訓練行動列からなる集合に対し、例えばＮ（Ｎ−１）／２個の順序評価値が得られる。以下では順序評価値をｏｓｔｅｐと総称する（ステップＳ１２／詳細は後述）。
【００１７】
訓練行動列評価部１５から出力された順序評価値ｏｓｔｅｐの集合と、行動列記憶１１から読み出された訓練順序評価値ｏ*の集合とが、報酬関数調整部１６に入力される。報酬関数調整部１６は、順序評価値ｏｓｔｅｐの集合と訓練順序評価値ｏ*の集合とを比較し、それらの相違に基づいて報酬関数パラメータθｓｔｅｐを報酬関数パラメータθｓｔｅｐ＋１に更新する（ステップＳ１３／詳細は後述）。
【００１８】
制御部１７は、所定の終了条件が満たされたかを判定する（ステップＳ１４）。終了条件の例は、順序評価値ｏｓｔｅｐの集合と訓練順序評価値ｏ*の集合と間の誤差が規定の値を下回る、既定回数更新しても当該誤差の改善量が規定量を下回る、または、繰り返し回数が規定数に達するなどである。順序評価値ｏｓｔｅｐの集合と訓練順序評価値ｏ*の集合と間の誤差の例は、対応する順序評価値ｏｓｔｅｐと訓練順序評価値ｏ*とが互いに相違する訓練行動列のペアの個数、順序評価値ｏｓｔｅｐの集合と訓練順序評価値ｏ*の集合との距離などである。
【００１９】
ステップＳ１４で所定の終了条件が満たされていないと判定された場合、制御部１７はｓｔｅｐ＋１を新たな変数ｓｔｅｐの値とし（ステップＳ１５）、処理をステップＳ１２に戻す。一方、所定の終了条件が満たされたと判定された場合、報酬関数調整部１６は、報酬関数パラメータθｓｔｅｐ＋１に対応する報酬関数を表す情報を出力する。報酬関数を表す情報の例は、報酬関数そのものや報酬関数パラメータθｓｔｅｐ＋１などである（ステップＳ１６）。このように、所定の終了条件が満たされるまで、訓練行動列評価部１５や報酬関数調整部１６等による処理（ステップＳ１２および１３）が繰り返され、所定の終了条件が満たされた場合に報酬関数を表す情報が出力される。
【００２０】
＜ステップＳ１２の詳細＞
ステップＳ１２の詳細を例示する。ここでは、報酬関数パラメータθｓｔｅｐに対応する報酬関数に基づいて、各訓練行動列ζ*のシステム評価値ｅ（ζ*｜θｓｔｅｐ）を得、各ペアζ*i，ζ*jに対応するシステム評価値ｅ（ζ*i｜θｓｔｅｐ），ｅ（ζ*j｜θｓｔｅｐ）の大小関係を表す情報を、各ペアζ*i，ζ*jに対応する順序評価値ｏｓｔｅｐ（以下「順序評価値ｏｓｔｅｐi，ｊ」と表記）とする。なお、各システム評価値ｅ（ζ*i｜θｓｔｅｐ）は、報酬関数パラメータθｓｔｅｐに対応する報酬関数を用いて計算された各訓練行動列ζ*iの評価値である。システム評価値ｅ（ζ*i｜θｓｔｅｐ）は、各訓練行動列ζ*iが表す一連の状態の報酬値またはその期待値の和に対応する。報酬値または期待値は、報酬関数パラメータθｓｔｅｐに対応する報酬関数を用いて得られる。このような値であればどのような値をシステム評価値ｅ（ζ*i｜θｓｔｅｐ）としてもよい。
【００２１】
システム評価値ｅ（ζ*i｜θｓｔｅｐ）の一例は、訓練行動列ζ*iが表す一連の状態の報酬値Ｒ（ζ*i｜θｓｔｅｐ）と、当該訓練行動列ζ*iに対応する最適行動列ζＡiが表す一連の状態の報酬値Ｒ（ζＡi｜θｓｔｅｐ）との差分である。
ｅ（ζ*i｜θｓｔｅｐ）＝Ｒ（ζ*i｜θｓｔｅｐ）−Ｒ（ζＡi｜θｓｔｅｐ）    (1)
なお、報酬値Ｒ（ζ*i｜θｓｔｅｐ）およびＲ（ζＡi｜θｓｔｅｐ）は、報酬関数パラメータθｓｔｅｐに対応する報酬関数を用いて得られる値である。報酬値Ｒ（ζ*i｜θｓｔｅｐ）およびＲ（ζＡi｜θｓｔｅｐ）の具体例は以下の通りである。
【数２】
0005815458.tif 000003
ここで、ｓ*ｉ，ｔおよびｓＡｉ，ｔは、それぞれ、訓練行動列ζ*iおよび最適行動列ζＡiが表すｔ番目の状態（時点ｔでの状態）を表す。ｆ（ｓ*ｉ，ｔ）およびｆ（ｓＡｉ，ｔ）は、それぞれ、状態ｓ*ｉ，ｔおよびｓＡｉ，ｔに対応する素性を表すＭ次元ベクトルである。ｆ（ｓ*ｉ，ｔ）およびｆ（ｓＡｉ，ｔ）の各要素は正の実数である。βＴはβの転置を表す。θｓｔｅｐＴ・ｆ（ｓ*ｉ，ｔ）およびθｓｔｅｐＴ・ｆ（ｓＡｉ，ｔ）はＭ次元ベクトルの内積を表し、報酬関数パラメータθｓｔｅｐに対応する報酬関数に相当する。なお、これらの報酬値やシステム評価値は一例にすぎず、要旨を逸脱しない範囲での変更は可能である。
【００２２】
また最適行動列ζＡiは、訓練行動列ζ*iが表す一連の状態の初期状態s*ｉ，０と同一の状態を初期状態sｉ，０とし、その初期状態から各行動によって遷移する一連の状態と各状態での行動とを表す行動列ζiのうち、報酬関数パラメータθｓｔｅｐに対応する報酬関数によって得られる当該一連の状態の報酬値の合計が最大となる行動列を意味する。例えば、訓練行動列ζ*iが表す初期状態s*ｉ，０を初期状態sｉ，０とする行動列ζiのうち、以下の報酬値Ｒ（ζi｜θｓｔｅｐ）を最大にする行動列ζiが最適行動列ζＡiである。
【数３】
0005815458.tif 000004
ここで、ｓｉ，ｔは、行動列ζiが表すｔ番目の状態を表す。ｆ（ｓｉ，ｔ）は、状態ｓｉ，ｔに対応する素性を表すＭ次元ベクトルである。
【００２３】
≪最適行動列ζＡiの探索≫
上記の方法でシステム評価値を計算するためには、訓練行動列記憶部１１に格納されたすべての訓練行動列ζ*iに対し、それぞれ最適行動列ζＡiを決定する必要がある。ここでは最適行動列ζＡiを決定するため、訓練行動列ζ*iごとに多数の行動列ζiを生成し、報酬値Ｒ（ζi｜θｓｔｅｐ）が最大となる行動列ζiを探索する、探索的アプローチを用いる。
【００２４】
各行動列ζiは、訓練行動列ζ*iが表す一連の状態の初期状態ｓ*ｉ，０を初期状態sｉ，０とし、各状態ｓｉ，ｔでの行動ａｉ，ｔを決定し、その行動ａｉ，ｔに基づいて次の状態ｓｉ，ｔ+１を決定するというプロセスを繰り返して生成される。問題の空間が全探索可能なほど小さい場合には、訓練行動列ζ*iごとに、初期状態ｓｉ，０から遷移し得るすべての行動列ζiを生成し、それらの中で報酬値Ｒ（ζi｜θｓｔｅｐ）が最大となる行動列ζiを最適行動列ζＡiとする（全探索法）。一方、空間が大きく全探索が困難な場合には行動列ζiを確率的に生成し、それらの中で報酬値Ｒ（ζi｜θｓｔｅｐ）が最大となる行動列ζiを最適行動列ζＡiとする（部分探索法）。
【００２５】
［最適行動列ζＡiの生成方法の例示］
最適行動列ζＡiの生成方法を例示する。
１−１−１：訓練行動列記憶部１１からある訓練行動列ζ*iが読み出され、状態遷移計算部１２に入力される。
【００２６】
１−１−２：状態遷移計算部１２で、訓練行動列ζ*iが表す一連の状態の初期状態ｓ*ｉ，０を読み出し、初期状態ｓｉ，０＝ｓ*ｉ，０を行動評価部１３へ入力する。
【００２７】
１−１−３：行動評価部１３で、現在の報酬関数パラメータθｓｔｅｐに基づき、状態ｓｉ，ｔで取りうるすべての行動ａｉ，ｔについて、以下の期待報酬値ｒｉ，ｔ（ｓｉ，ｔ，ａｉ，ｔ）を計算する。最初のループではｔ＝０とされる。
【数４】
0005815458.tif 000005
ただし、ＰＴ（ｓｉ，ｔ＋１｜ｓｉ，ｔ，ａｉ，ｔ）は、状態ｓｉ，ｔで行動ａｉ，ｔを行った場合に状態ｓｉ，ｔ+１に遷移する条件付き確率を表す。なお、条件付き確率ＰＴ（ｓｉ，ｔ＋１｜ｓｉ，ｔ，ａｉ，ｔ）は予め定められているものとする。
【００２８】
１−１−４：行動評価部１３で得られた状態ｓｉ，ｔおよび行動ａｉ，ｔごとの期待報酬値ｒｉ，ｔ（ｓｉ，ｔ，ａｉ，ｔ）は、対応する状態ｓｉ，ｔおよび行動ａｉ，ｔを表す情報とともに、行動決定部１４および訓練行動列評価部１５に入力される。
【００２９】
１−１−５：行動決定部１４で、期待報酬値ｒｉ，ｔ（ｓｉ，ｔ，ａｉ，ｔ）に基づいて状態ｓｉ，ｔでの行動ａｉ，ｔを決定し、決定した行動ａｉ，ｔおよび状態ｓｉ，ｔを表す情報を状態遷移計算部１２へ入力する。全探索法の場合、状態ｓｉ，ｔで取り得る行動が順番にａｉ，ｔとして選択される。部分探索法の場合、確率的に行動ａｉ，ｔが決定される。行動ａｉ，ｔの確率的な決定方法は後述する。
【００３０】
１−１−６：状態遷移計算部１２で、行動決定部１４で得られた行動ａｉ，ｔに基づいて、次の状態ｓｉ，ｔ＋１を決定し、決定した状態ｓｉ，ｔ＋１を表す情報を行動評価部１３へ入力する。  
【００３１】
１−１−７：所定の終了条件を満たさない場合にはｔ＋１を新たなｔとして１−１−３へ戻る。所定の終了条件を満たす場合にはループを停止し、行動評価部１３はそれまでに得られた一連の状態ｓｉ，ｔおよび行動ａｉ，ｔからなる行動列ζiを訓練行動列評価部１５へ入力する。この終了条件の例は、１−１−３〜１−１−７のループを既定回数繰り返した、既定の状態に至った等である。
【００３２】
訓練行動列評価部１５は、以上の１−１−１〜１−１−７のループを複数回繰り返し、訓練行動列ζ*iごとに複数個の行動列ζiを得る。訓練行動列評価部１５は、得られた行動列ζiのそれぞれについて報酬値Ｒ（ζi｜θｓｔｅｐ）を計算し、訓練行動列ζ*iごとに報酬値Ｒ（ζi｜θｓｔｅｐ）を最大にする行動列ζiを得、それらを各訓練行動列ζ*iに対応する最適行動列ζＡiとする。すなわち、訓練行動列評価部１５は、訓練行動列ζ*iが表す一連の状態の初期状態ｓ*ｉ，０を初期状態ｓｉ，０とする最適行動列ζＡiをｉごとに生成する。
【００３３】
［１−１−５での行動の確率的な決定方法の例］
空間が広く全探索困難な場合、行動ａｉ，ｔを確率的に決定する必要がある。その方法として、２種類の方法を例示する。
【００３４】
例１：期待報酬値ｒｉ，ｔ（ｓｉ，ｔ，ａｉ，ｔ）に基づいて確率的に選択
例１の行動決定部１４は、例えば確率ｐ（ａｉ，ｔ）∝ｅｘｐ（ｒｉ，ｔ（ｓｉ，ｔ，ａｉ，ｔ））またはｐ（ａｉ，ｔ）∝ｒｉ，ｔ（ｓｉ，ｔ，ａｉ，ｔ）に従って行動ａｉ，ｔをサンプリングし、状態ｓｉ，ｔでの行動ａｉ，ｔを決定する。ただし、β１∝β２はβ１がβ２に比例することを表し、ｅｘｐは指数関数を表す。
【００３５】
例２：ランダムに選択
例２の行動決定部１４は、期待報酬値ｒｉ，ｔ（ｓｉ，ｔ，ａｉ，ｔ）の値にかかわらず、一様分布もしくは非特許文献６のＵＣＢアルゴリズムなどの探索アルゴリズムに従って行動ａｉ，ｔをサンプリングし、状態ｓｉ，ｔでの行動ａｉ，ｔを決定する。この場合には、期待報酬値ｒｉ，ｔ（ｓｉ，ｔ，ａｉ，ｔ）が算出されなくてもよい。
［非特許文献６］P. Auer, N. Cesa-Bianchi, P. Fischer. Finite-time analysis of the multiarmed bandit problem, Machine learning, pp. 235-256, 2002.
【００３６】
≪システム評価値の計算≫
訓練行動列評価部１５は、上述の各最適行動列ζＡi、および訓練行動列記憶部１１から読み出した各訓練行動列ζ*iを用い、各訓練行動列ζ*iのシステム評価値ｅ（ζ*i｜θｓｔｅｐ）を得る。訓練行動列評価部１５は、例えば前述の式（１）に従ってシステム評価値ｅ（ζ*i｜θｓｔｅｐ）を得る。
【数５】
0005815458.tif 000006
この例のシステム評価値ｅ（ζ*i｜θｓｔｅｐ）は、報酬関数パラメータθｓｔｅｐに対応する報酬関数を用いて得られる、訓練行動列ζ*iが表す一連の状態の報酬値の和と、当該訓練行動列ζ*iに対応する最適行動列ζＡiが表す一連の状態の報酬値の和と、の差に相当する。
【００３７】
あるいは、式（１）に従ってシステム評価値ｅ（ζ*i｜θｓｔｅｐ）を得るのではなく、訓練行動列評価部１５が、最適行動列ζＡiおよび訓練行動列ζ*iに対応する期待報酬値ｒｉ，ｔ（ｓｉ，ｔ，ａｉ，ｔ）（式（２）参照）を用い、以下のようにシステム評価値ｅ（ζ*i｜θｓｔｅｐ）を得てもよい。
【数６】
0005815458.tif 000007
この例のシステム評価値ｅ（ζ*i｜θｓｔｅｐ）は、報酬関数パラメータθｓｔｅｐに対応する報酬関数を用いて得られる、訓練行動列ζ*iが表す一連の状態の報酬値の期待値の総和と、当該訓練行動列ζ*iに対応する最適行動列ζＡiが表す一連の状態の報酬値の期待値の総和との差に相当する。
【００３８】
≪順序評価値の計算≫
訓練行動列評価部１５は、各システム評価値のペアζ*i，ζ*ｊに対応するシステム評価値ｅ（ζ*i｜θｓｔｅｐ），ｅ（ζ*ｊ｜θｓｔｅｐ）を用い、システム評価値ｅ（ζ*i｜θｓｔｅｐ），ｅ（ζ*ｊ｜θｓｔｅｐ）の大小関係を表す各順序評価値ｏｓｔｅｐi，ｊを得て出力する。例えば、訓練行動列評価部１５は、ペアζ*i，ζ*ｊごとにシステム評価値ｅ（ζ*i｜θｓｔｅｐ），ｅ（ζ*ｊ｜θｓｔｅｐ）を比較し、以下のように各順序評価値ｏｓｔｅｐi，ｊを得て出力する。
【数７】
0005815458.tif 000008
【００３９】
＜ステップＳ１３の詳細＞
ステップＳ１３の詳細を例示する。
報酬関数調整部１６は、各ペアζ*i，ζ*ｊに対応する訓練順序評価値ｏ*i，ｊと順序評価値ｏｓｔｅｐi，ｊとを入力とし、ｏ*i，ｊとｏｓｔｅｐi，ｊとをペアζ*i，ζ*ｊごとに比較し、ｏ*i，ｊとｏｓｔｅｐi，ｊとの正負が互いに異なるペアζ*i，ζ*ｊを選択する。
【００４０】
報酬関数調整部１６は、訓練行動列記憶部１１から訓練順序評価値ｏ*i，ｊと順序評価値ｏｓｔｅｐi，ｊとの正負が互いに異なるペアζ*i，ζ*ｊを抽出し、以下に従って報酬関数パラメータθｓｔｅｐを報酬関数パラメータθｓｔｅｐ＋１に更新する。
【数８】
0005815458.tif 000009
ただし、式（３）のγは所定の重み係数であり、例えば、０＜γ＜１を満たす実数である。またγは学習率であり、０.０１＜γ＜０．１程度の値とすることが望ましい。報酬関数パラメータの更新後の挙動によってγが修正されてもよい。
【００４１】
例えば、ｏ*i，ｊ＝１かつｅ（ζ*i｜θｓｔｅｐ）＜ｅ（ζ*ｊ｜θｓｔｅｐ）（すなわちｏｓｔｅｐi，ｊ≠１）のとき、ｏｓｔｅｐ＋１i，ｊ＝１とするためにはｅ（ζ*i｜θｓｔｅｐ）−ｅ（ζ*ｊ｜θｓｔｅｐ）が大きくなる方向にθｓｔｅｐを更新してθｓｔｅｐ＋１とすればよいため、
【数９】
0005815458.tif 000010
とすればよい。一方、ｏ*i，ｊ＝−１かつｅ（ζ*i｜θｓｔｅｐ）＞ｅ（ζ*ｊ｜θｓｔｅｐ）（すなわちｏｓｔｅｐi，ｊ＝１）のとき、ｏｓｔｅｐ＋１i，ｊ＝−１とするためにはｅ（ζ*i｜θｓｔｅｐ）−ｅ（ζ*ｊ｜θｓｔｅｐ）が小さくなる方向にθｓｔｅｐを更新してθｓｔｅｐ＋１とすればよいため、
【数１０】
0005815458.tif 000011
とすればよい。これらをまとめると式（３）となる。
【００４２】
以上のように、この例の報酬関数調整部１６は、訓練順序評価値ｏ*i，ｊと順序評価値ｏｓｔｅｐi，ｊとの正負が異なる組をなす２個の訓練行動列ζ*i，ζ*ｊの一方に対応するシステム評価値から他方に対応するシステム評価値を減じた値ｅ（ζ*i｜θｓｔｅｐ）−ｅ（ζ*ｊ｜θｓｔｅｐ）の報酬関数パラメータθｓｔｅｐでの偏微分値と、当該正負が異なる組をなす２個の訓練行動列ζ*i，ζ*ｊに対応する訓練順序評価値ｏ*i，ｊと、の乗算値の総和に対応する更新ベクトルγ▽θｓｔｅｐｐｒｅｆを得、当該更新ベクトルγ▽θｓｔｅｐｐｒｅｆによって報酬関数パラメータθｓｔｅｐを更新することで報酬関数を更新する。
【００４３】
以上の方法に加え、高い評価の行動列を利用した逆強化学習を行って報酬関数パラメータθｓｔｅｐを更新してもよい。その場合、報酬関数調整部１６は、高い評価の行動列を再現するよう報酬関数パラメータθｓｔｅｐを更新するために、以下のように報酬関数パラメータθｓｔｅｐを更新する。
【数１１】
0005815458.tif 000012
【００４４】
なお、式（４）のγおよびαはいずれも所定の重み係数であり、例えば、０＜γ＜１，０＜α＜１を満たす実数である。γは学習率であり、０.０１＜γ＜０．１程度の値とすることが望ましい。報酬関数パラメータの更新後の挙動によってγが修正されてもよい。また、αを大きくすると高い評価の行動列が重視されて逆強化学習（ＩＲＬ：inverse reinforcement learning）の挙動に近づく。一方、αを小さくすると本発明の方式（Preference-based ＩＲＬ）の挙動が強くなる。
【００４５】
以上のように、この例の報酬関数調整部１６は、訓練順序評価値ｏ*i，ｊと順序評価値ｏｓｔｅｐi，ｊとの正負が異なる組をなす２個の訓練行動列ζ*i，ζ*ｊの一方に対応するシステム評価値から他方に対応するシステム評価値を減じた値ｅ（ζ*i｜θｓｔｅｐ）−ｅ（ζ*ｊ｜θｓｔｅｐ）の報酬関数パラメータθｓｔｅｐでの偏微分値と、当該正負が異なる組をなす２個の訓練行動列ζ*i，ζ*ｊに対応する訓練順序評価値ｏ*i，ｊと、の乗算値の総和に対応する更新ベクトルγ▽θｓｔｅｐｐｒｅｆを得る。さらに、この例の報酬関数調整部１６は、訓練行動列ζ*iが表す一連の状態のそれぞれに対応するベクトルの総和から、当該訓練行動列ζ*iに対応する最適行動列ζＡiが表す一連の状態のそれぞれに対応するベクトルの総和を減じて得られるベクトルの総和に対応する逆強化学習ベクトルγα▽θｓｔｅｐｃｌｉｐを得る。この例の報酬関数調整部１６は、更新ベクトルγ▽θｓｔｅｐｐｒｅｆおよび逆強化学習ベクトルγα▽θｓｔｅｐｃｌｉｐによって報酬関数パラメータθｓｔｅｐを更新することで報酬関数を更新する。
【００４６】
＜シミュレーション＞
［ｃｏｌｏｒ−ｇｒｉｄｗｏｒｌｄ］
上述の方式と従来方式とを比較するため、ｃｏｌｏｒ−ｇｒｉｄｗｏｒｌｄを導入する。これは従来のＲＬ／ＩＲＬで頻繁に用いられるｇｒｉｄｗｏｒｌｄタスクを、多様な報酬関数を許容するように拡張したものである。図３を用いてｃｏｌｏｒ−ｇｒｉｄｗｏｒｌｄの概要を説明する。ｃｏｌｏｒ−ｇｒｉｄｗｏｒｌｄでは、エージェントは各時点ｔにおいて四方の任意のマス（状態ｓｔ）へ移動できる。エージェントがある状態ｓｔへ遷移するごとに、状態ｓｔに関連付けられた素性に対応する評価値を受け取る。ｃｏｌｏｒ−ｇｒｉｄｗｏｒｌｄの状態ｓｔはそれぞれ特定の色（Ｃｏｌｏｒ  ｆｅａｔｕｒｅ）を持ち、各エージェント（ａｇｅｎｔ１〜３）は図３Ｂのようにそれぞれ異なる報酬関数（色と評価値の対応関係）を持つとする。例えば図３Ｂでは、エージェント１では緑色（横ハッチング）が評価値−３に対応し、青色（斜めハッチング）が評価値＋１に対応する。この例では、一度エージェントが訪れた状態に専用の素性（Ｖｉｓｉｔｅｄ  ｆｅａｔｕｒｅ）を割り当てる（図３Ｂ中、白色（ハッチングなし））。このルールにより、高い評価の状態に留まり続けることを抑制するとともに、各方式がこうした素性に対しどのような報酬を付与するのかを検証する。このルールによって状態列の履歴を保存すると、状態列の総数は各状態が０もしくは１を取る全組み合わせ数となるため、状態数をｎとして状態列の数がＯ（２＾ｎ）となり爆発してしまう。そのため状態列数が膨大でも比較的動作するモンテカルロ法を用いてエージェントの方策を決定する。学習データには、ランダムに報酬関数と初期状態が設定された訓練エージェントによって生成された行動列に対し、評価エージェントが順序評価したものを用いる。また、推定された報酬関数の評価は、報酬関数の学習時とは異なるｃｏｌｏｒ−ｇｒｉｄｗｏｒｌｄ上で行う。
【００４７】
[シミュレーション結果]
上述した提案手法を用い、順序評価つきの訓練行動列を入力として、行動列に評価を付与した評価エージェントの報酬関数を推定する。比較対象の従来手法として、非特許文献５の手法（ＭａｘＥｎｔｌＲＬ）を用いる。さらに、この従来手法は順序評価値には対応していないため、評価エージェント自身が生成した行動列を入力として評価エージェントの報酬関数を推定するものとする。このシミュレーションを手法ごとに５回実行し、それらの評価の平均値を用いて比較する。各パラメータは以下のように設定する。各行動列の最大長Ｔは７、エージェントのモンテカルロのサンプル生成数は３０００、評価者のサンプル生成数は５０００、ＩＲＬのイテレーション回数は最大５０にする。報酬関数のパラメータの範囲は−４から＋４までとし、全エージェント間で一度訪れた状態に付与される素性に対応する報酬は−１とする。ただし、学習エージェントはこの設定を知らないものとする。
【００４８】
正解パラメータに対する推定された報酬関数の誤差（報酬関数距離）の平均値を表１に示す。色数（色の個数、すなわち素性の個数）５の場合と１５の場合で評価を行った。表１より、評価エージェントのみを用いて推定する従来手法よりも、行動列の適切さが異なるデータから順序評価を用いて推定した提案手法のほうが誤差を小さくできることが分かる。
【表１】
0005815458.tif 000013
【００４９】
＜本形態の特徴＞
本形態の手法を用いることで、従来よりも適切に報酬関数を訓練行動列から推定できる。その結果、例えば人同士の対話からそのやり方を学習することでロボットによる自然な対話を実現することが可能になる。また、システムとやりとりするユーザがどのようなものを求めているか、個人ごとにその評価関数を推定することで、より適切な推薦や情報提示が可能になる。本形態では、異なる適切さを持つ訓練行動列とその訓練順序評価に基づき、その訓練順序評価を付与した評価エージェントの報酬関数を推定する。行動列自体以外に必要になるデータは訓練行動列のペアごとの訓練順序評価であり、これは個々に絶対値で点数をつけていくやりかたや、データ全体の全順序を付与するやり方に比べ、評価付与が容易であるという利点も持つ。
【００５０】
＜変形例等＞
本発明は上述の実施形態に限定されるものではない。例えば、報酬関数は上述したものに限定されず、状態（例えば状態に対応するベクトル）と報酬関数パラメータとに対応するその他の関数が報酬関数とされてもよい。
【００５１】
システム評価値は上述したものに限定されず、例えば以下のようなシステム評価値が用いられてもよい。
【数１２】
0005815458.tif 000014
【００５２】
訓練順序評価値や順序評価値が｛−１，０，１｝の値を取るのではなく、−１の代わりに所定の負値をとり、１の代わりに所定の正値をとってもよい。また、報酬関数パラメータや報酬関数の更新方法も上記のものに限定されない。更新された報酬関数を用いて得られる順序評価値の集合と訓練順序評価値の集合との相違が、更新前の報酬関数を用いて得られる順序評価値の集合と訓練順序評価値の集合との相違よりも小さくなるように、報酬関数パラメータや報酬関数が更新されればよい。
【００５３】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００５４】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００５５】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。
【００５７】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００５８】
１  報酬関数推定装置
１１  訓練行動列記憶部
１５  訓練行動列評価部
１６  報酬関数調整部
【図１】
0005815458.tif 000015
【図２】
0005815458.tif 000016
【図３】
0005815458.tif 000017
【図４】
0005815458.tif 000018