リレー解説
強化学習の最近の発展

リレー解説に寄せて：強化学習研究の歩み
木村元＊＊九州大学 大学院工学研究院，福岡県福岡市西区元岡 ＊             キーワード：強化学習 ,   '   - 分類子システム , .   '- / 学習 ,/ -，政策勾配法 ,&     '  -    '       !"#!$ %& 

＊'( ')'* * *+&º­



(a)

はじめに

強化学習とは，ゴール指向型の学習と意思決定を理解し実現するための計算論的な接近法であり，試行錯誤による強化値

環境との相互作用を通じて学習していくという点において，(b)

教師による教示や環境の完全なモデルに依存する他の学習とは区別される ．この強化学習（   ）(c)の研究には，大きく３つの流れが存在したと考えられる．第一の流れとして分類子システム 第二はニューラルネット
ワーク関連の研究における試行錯誤学習，第三にマルコフ

時間

t-4

  

図t-3

t-1

t-2

t

におけるルールの信頼度割当の例．

決定過程の最適制御問題とダイナミックプログラミングが挙げられる．このほか学習オートマトンにおいても強化学習の研究がみられるが、原理的には勾配法が多いので本稿複数のルールがマッチする可能性があるが，その場合ルーではニューラルネットワークに含めて紹介する．それぞれルに付加されている信頼度（重み変数）に基づいてルールの流れにおいて主流となる学習アルゴリズムや解析手法は選択の意思決定を行う．感覚入力と行動出力により環境中異なるが，これらの異なる分野同士で影響を及ぼし合いなで状態遷移を繰り返し，それら一連のエピソードの結果とがら研究が大きく発展してきた．本稿では，主に  年してエージェントは報酬を獲得する．このとき分類子シス代から近年に至るまでのおよそ  年間の強化学習研究にテムはルールへの信頼度の割当機能により，報酬獲得に有おけるいくつかのエポックメイキング的な手法や解析を中効なルール群を獲得していく．信頼度割当   

心に紹介し，それらの関係を示すことにより強化学習研究  のアルゴリズムとしてはまずバケツリレー法 の歩みについて概観する．

 

   が提案された．これは，報酬を獲得したエピソードにおいて実行されたルールを時系列順に考え，

 º 分類子システムにおける信頼度割当

時間的に後ろのルールから前のルールへと  と呼ばれる一定値を伝播しながら各ルールの信頼度へ加えていく方法

分類子システム     とは，分類子  である ．時間的に隣接するルール間で値をやりとりする  と呼ばれるルールを学習することにより，与えられことから，後述する  法との類似性が指摘されている ．

た環境に適応するようなプロダクションシステム，すなわ

このバケツリレー法では，エピソードのステップ数が多い

ち知識ベースおよび推論システムである．以下の３つの場合，エピソードの初期に実行するルール群を強化するた機能により構成される：めの  の伝播に時間がかかるという問題があった．そこ

感覚入力に応じて行動出力のルールを選択する機能

で，エピソードで実行したルールとその順番を記憶してお環境から与えられる報酬に基づいてルールに信頼度き，環境から報酬を得た時点でそれらのルールに対して一   を与える機能

気に信頼度割当を行う     法が提案された．図新しいルールを生成・発見する機能
このうち  番目の機能は遺伝的アルゴリズムによって与えに     法によるルールの信頼度割当による強化の例を示す．

られる．本稿では強化学習を実現する上で重要な 番目とあるエピソードで，同一の感覚入力に対して異なるルー

 番目の機能について紹介する．分類子システムのルール

ルが選択されているとき，その間のルール系列を迂回系列は以下のような形式である：といい，経験した全てのエピソード上で常に迂回系列上に ＜条件＞  ＜行動＞あるルールを無効ルールと呼ぶ．

 

 法によるルールの条件部は固定長の文字列で表され，環境からの感覚ルールの強化において，任意の無効ルールが抑制されるた

入力の文字列とマッチするルールが選択される．このとき，めの必要十分条件は以下で示される：

計測と制御 第  巻 第  号  年  月号

 【状態観測】エージェントは環境の状態 を観測し，特徴ベクトル Ü       を生成する．
 【 による行動選択】行動  を以下の式で決める：

錯誤学習と政策勾配法

  生体の神経回路網についての知見から着想を得て人工神

経回路網モデルを構築し解析することにより生体の学習について理解し，工学的に応用していくというのがニューラ

ただし  は  の重み変数を表し，この値を学習によって変更していく．関数  は以下のようなしきい値関数である：

   

ルネットワーク研究における主要なスタンスである．この流れから " 則やパーセプトロン，バックプロパゲーショ  

ンなどの目覚しい成果が生まれたのは周知のことであるが，当然ながら試行錯誤学習についても同様のアプローチが試

また は期待値  分散  の正規分布である．
 【 による行動評価】状態遷移後の状態  を観測し， を生成する．以下の式に従って状態特徴ベクトル Ü を計算する：
価値関数  および 

みられた．#

択器 $%&$ ' %  &   と，報酬の予測学
習器 $(&$  ' (   &   を組み合わせ，これ  らを " 則によって学習させることにより強化学習シス



テムを構築し，倒立振子のコントローラの学習への適用をこの状態評価値を利用して行動評価値    を計算する：

     

示した ．図  はその $%&$(& 学習器のアルゴリズムを  示す．他の関連するアルゴリズムとの関係を分かりやすく

ただし は割引率， は状態遷移に伴って得た報酬である．
 【行動の強化】 の重み変数  を以下のように更新：示すために変数等の記法をオリジナルから多少変更している．また，図  のアルゴリズム中では状態観測  が特徴量      

置と速度および振子の角度および角速度の４次元連続値の状態量を     )   ! ) の領域に分割しており，特Æ  

徴ベクトルの要素数

ただし   Æ  は減衰率である．
 【 の更新】以下のように  の重み変数  を更新： 

性について解析は示されていないものの，後に     法と呼ばれるアルゴリズム群の基本的なアイデアがほぼ全

ただし    は学習率， は  の適正度の履歴   !
    で以下のように計算する：

 

ただし     は減衰率である．
" 時間ステップ  を へ進めて手順図! ) である．行動出力は * または  の  値である．文献中においてアルゴリズムの妥当             に変換されているが，論文中では倒立振子の台車の位

ただし    は学習率，  は  の適正度の履歴      で以下のように計算する：

   Æ   

 らはパーセプトロンに類似した人工神経素子とノイズ発生器を組み合わせた試行錯誤による行動選   º ニューラルネットワークにおける試行  へ戻る．

  らの  アルゴリズムて含まれている．$%& と呼ばれる部分が   に該当し，$(& が    に相当する．特に $(& 部分の学習アルゴリズムは   法と呼ばれている．共著者の一人の % は，$(& の処理に注目し，環境がマルコフ過程である場合
において   法が割引報酬の期待値を推定していることを解析により示し，収束を証明した．これにより  の!の場合はモンテカルロ法による割引報酬のサンプル平均になり， !  の場合はマルコフ過程における非      !        

同期ダイナミックプログラミングとなり， がその中間にある場合はそれら双方の性質を兼ね備え，学習速度の点でより効果的であることを指摘し，適正度の履歴      の意味について初めて理論的な解釈を与えた．

ここで  はエピソード長， は同一感覚入力下に存在する有効ルールの最大個数である．これは無効ルール抑制定理 と呼ばれ，この条件を満たす強化関数の例としては図 のような指数関数がある．

分類子システムにおける解析では，上記のように環境のマルコフ性を仮定せず，また利得の最適性ではなく無効ルールの抑制に着目するなどの点でユニークな特徴があり，後に紹介する強化学習のアプローチとは一線を画する．

行動選択器 $%& において，その更新の手がかりとしている行動評価値    は，この呼び方は本稿の著者が都合によりこの記法で示したが，オリジナルの論文中では直接報酬の推定値 + となっている．#

 らが $(& を併用してこの    を手がかりに学習する手法を提案する以前は，   ! + の代わりに直接報酬

 を用いて学習する手法が存在しており，その方法でもある程度学習できることが示されていた．これは $%&    の行動選計測と制御 第 $0 巻 第号 0" # 年月号

択法と $%& 中の適正度の履歴を用いた学習アルゴリズムでも学習できることを意味し，これに密接に関連するアルゴリズムが  ,&-./0,(& アルゴリズムとして示されている  ．これは，エージェントが時刻  の状態  において行動 を確率（あるいは確率密度）       に従って選択することを  ステップの期間行い，その状態行動系列の結果として利得  が与えられた場合，エージェン

トの重み変数ベクトル  を以下のように更新する：

 !    1  

ただし    は学習率， は      と呼の期待値がエージェ

ントの重み変数  の条件付期待値で与えられる場合，   

 !    とすると，政策勾配定理 より以下の式が与えられる： !          2
  +  次に，真の 4 関数    を関数近似によって 
を各要素としたベクトル      を基正度
底関数とし、この各適正度に対応した要素を持つパラメー
タベクトル  との線形結合および状態価値関数    を用いて以下のように表す：

+    !     *    2 +   との  乗誤
真の 4 関数    と近似 4 関数を  !  & &1となることが証明されている．また  の値は利得  の期待値の値と同じになると 1 による更新のランダムウォークの度合いが最も低減され，確実に利得の期待値の１次勾配を登るように重み変数を更新するようになる．ここで 

ここで   !

+   は適と表すことを考える。ただしこの近似 4 関数     

ばれる定数パラメータである．報酬 !    3    !    !   !      

差が最小になるようパラメータベクトル  を調節すると，政策勾配定理 より以下が成り立つ：

 !       +    2  5     はその適正度   

つまり、   において 4 関数を近似する場合に   のが入るものとしてアルゴリズムを構築すると，$%&   にもかかわらず真の勾配方向へ政策を更新できることを意は確率的政策であり    である．利得  を割引報酬として各ステップで報酬の行動選択法と $%& 中の適正度の履歴を用いた学習アルゴリズムが導かれる．また，図  のアルゴリズムのように   と $%& 中の適正度の履歴を用いて   を更新する方法は，先の  ,&-./0,(& アルゴリズムにおける  の部分を利得  の推定値としていることと等価であることが示されている．

このように   の行動選択のメカニズムを行動の確率分布関数（確率的政策）に従って駆動し，利得の勾配方向へ政策のパラメータを更新する方法は「政策勾配法」と総適正度を基底関数として利用すると，4 関数が近似である
味する．一般に 4 関数の表現では，以下のように状態評 と呼ばれる評価値

   をできる．式（）の右辺左側の項     

 がこの価値   と， ' 用いて    !   *    のように表すことが
' 

 関数    を近似している．

この式 5 の次偏導関数で示される政策勾配を使った様々な政策改善アルゴリズム が提案される一方で， 次偏導関数も考慮に入れた「自然勾配   」と呼ばれる勾配を用いる政策改善法が提案されている．この称され，行動が連続値でも離散値でもアルゴリズムが比較

種の勾配法は， 次偏導関数しか使用しない勾配法に比べて的簡単に実装可能なのでロボットの学習制御などに実績が格段に少ない反復回数で極値を得ることができ，一般的なある ．さらに，   の政策を改善するのに必要十分な最適化手法としてニュートン法が知られているが，一般に 価値関数近似のための基底関数は何なのかについての研究次偏導関数行列（ヘッセ行列）の逆行列を求めるという大きが進められ，政策勾配定理 により、   の政策を改善な計算コストが要求される．ところが強化学習における政するのに必要な価値関数近似のための基底関数は、適正度

策パラメータに関する自然勾配は，情報理論的に興味深いすなわち行動選択確率関数（政策）の対数を政策パラメー性質を持ち、上記の逆行列計算が不要になる．$' 

タで偏微分した関数であることが示されている。確率的政関数を構成する式（）のパラメータベクトル  において，を実行する．この    は政策パラメータ群  によっす．これらが式（5）を満たすとき，目的関数   に対す

策  は，状態  において行動選択確率    に従って行動て値を調節でき，パラメータ群の各要素  により偏微分可能な関数であるとする．ここで利得  を以下で定義する：

      !     !   

2





エージェントの学習目標である目的関数   を定義する：

計測と制御 第  巻 第  号  年  月号

ある政策パラメータ  の適正度に対応する要素を  と表るパラメータ  の自然勾配単純な式で表される ：  は，以下のように驚くべき 6 !  27

すなわち，基底関数として   の適正度を用いた ' 
 関数を構成するパラメータベクトル

 は，対応する政策パラメータ  の自然勾配になっている。このアルゴリズムは、4 値を推定しつつ２次勾配も考慮しながら政策を改善していくため，マルコフ性を満たす大規模問題において極めて効率良く政策改善を行うことが期待される．

 º マルコフ決定過程の最適制御問題とダイナミックプログラミング
マルコフ決定過程 8 ' 

9 8  における最適制御問題において #   の最適方程式と呼ばれる関数方程式を立て，この方程式を解いて解を得る手法のクラスは動的計画法     9   として知られる．環境をマルコフ決定過程でモデル化し， で最適政策を得ることはプランニングと呼ばれ，完全な環境モデルを要することから強化学習とは区別されるが，の計算における状態遷移確率による重み付けの部分を確率サンプリングによる平均操作で代用し，それを未知の環境中でエージェントが試行錯誤を行うことにより実現した強化学習法が 4    である．さらに 4 値などを関数近似で表現した場合におけるアルゴリズムや収束についての詳しい解析が示された．

 º おわりに
本稿では主に３つの系統の強化学習アルゴリズム研究の歩みについて概説した．この他の重要な強化学習の話題として以下が挙げられる：
連続・多次元空間への対応：状態空間については関数近似法 や特徴ベクトルの生成問題として扱われる．空間の適応的分割などの手法 もこれに相当する．行
動空間については特に行動選択方法が問題になる．その場合，確率密度関数を確率的政策として連続値行動を扱い，政策勾配法を適用するのが一般的 であるが，ランダムタイリングと :   を組合わせて多次元状態行動空間で 4   を行う方法
がある．
状態観測の不完全性への対応：マルコフ決定過程では，状態観測が完全であることが前提であるが，実環境や） $- 3  )   -  9,+ :,& ! 0  3 !
00 : 1     ;  ##"） % )  + %     101 6. 0 <!
   ) 41  2  ))  !* ') 4 #7#） 半田 久志，二宮 明，堀内 匡，小西 忠孝，馬場 充：強化学習における矛盾の概念に沿った漸増的な状態空間の構成法，計測自動制御学会論文集 = 7 ,   .."#8>" ） ?  ) 9 ?+.     41  2   ;     .. 1 = &0 @@ '  4 1- 
9 %    )  4 4 1 ) 4  A&0 .. #8"  #7"
"） ?& 9 ( *0  4 3+ 4&   '  0  2 !
+    B0C -  )    10 3 )  1 1 @      41  2 .. 8   ##7>） A-) +  ,& 3   %)   )/  ,&@  03   0  ..  8 7 7） 木村 元，小林 重信+   に適正度の履歴を用いた  !
   アルゴリズム8 不完全な =&!B& のもとでの強化学習，人工知能学会誌 =   ,  ..">8> #） 木村 元：ランダムタイリングと % !0.  を用いた多次元状態!行動空間における強化学習，計測自動制御学会論文集
=    .. "8  "） A ) =' (   -  9,+  !     10)/  ,& @  0
3   0  ..
78   ） 宮崎 和光，小林 重信+ 離散マルコフ決定過程下での強化学習，
人工知能学会誌 =   , " ..7 87  ##>） 3 9 = D-&0  ( 1 + '  0 2    ?&0 ) '   ! .   )    ) ) ) @!' @      ?&!
0 ) '    ） &  '   ) $  + :'  0  2 + @  )& :  $) ) $ - 1 4@ 3  ##7） &  '  4   1  ( 4  & E+3   %)   41 )   '  0  2  C 1
B& .. F 0  )/ ,& @  0
3   0  ,@3  ..  >8 " ） *-  9? (   3+ 1  , + G!
2  41  2  7 ..>#8#  ##"） *  0 ' 9+  0.    %)   B  C   !
 10    '  0  2       .. #8 "  ##>） 矢入 健久，堀 浩一，中須賀 真一+ 複数行動結果を考慮した最尤推定に基づく状態一般化法，人工知能学会誌 =  " ,  .. 78 7  7） 吉本 潤一郎，銅谷 賢治，石井 信：強化学習の基礎理論と応用，計測と制御 =  ,   .. 8 7  

応用においては完全な状態観測が困難である場合がある．これをモデル化したのが部分観測マルコフ決定過程   '   8 9の環境で学習するための方法が研究されている．

木村 元

マルチエージェント：マルコフゲームでの学習  など．

## 年東京工業大学工学部制御工学科卒業． ##> 年同大学大学院総合理工学研究科知能科学専攻博士後期課程修了． ##7 年  月，同大学大学院総合理工学研究科助手． 年  月，九州大学大学院工学研究院海洋システム工学部門助教授，> 年  月，同部門において准教授へ職名変更，現在に至る．情報技術の船舶海洋分野への応用に関する研究に従事．計測自動制御学会，日本船舶海洋工学会，人工知能学会，日本ロボット学会会員．

（  年 # 月  日受付）
参） $   % &考

文 献

 '  (  )   *+ ,&  -). / 0  1   /  Æ& 2   !
  3 0           /  4!   .056  #7..787"

［著 者 紹 介］

08  であり，こ計測と制御 第 $0 巻 第号 0" # 年月号