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

強化学習の基礎
木

村

元＊＊九州大学 大学院工学研究院，福岡県福岡市西区元岡 ＊             キーワード：強化学習 ,   '   - マルコフ決定過程,     & - . 学習 ,.  



­

     !"#!$ %&＊'( ')'* * *+&½ º はじめに強化学習（  

エージェント（コントローラ） ）とは，試行錯誤を

行動 at

状態観測 st通じて環境に適応する学習制御の枠組である．教師付き学報酬

rt習      と異なり，状態入力に対する正し環境（制御対象）

い行動出力を明示的に示す教師が存在しない代わりに，一連の行動に対して結果としての良し悪しを評価する「報酬（  ）」というスカラーの評価値が与えられ，これを手図がかりに学習を行うが，報酬や状態遷移には不確実性や時間的遅れがある．そのため，一般に行動を実行した直後の強化学習の枠組．エージェントは試行錯誤を通じて適切な制御規則を獲得していく．

報酬をみるだけでは，学習主体はその行動が正しかったかと表す．時刻 において環境中のとある状態    にあるとどうかを判断できないという困難を伴う．

き，エージェントが行動  を選択し実行すると，時刻  

強化学習の枠組を図  に示す．学習の主体「エ−ジェント」と制御対象「環境」は以下のやりとりを行う．
 エ−ジェントは時刻 において環境の状態観測  に応じて意思決定を行い，行動  を出力
 エ−ジェントの行動により，環境は  へ状態遷移し，その遷移に応じた報酬  をエ−ジェントへ与える．

において環境は確率的に状態    へ遷移する．その遷移確率は条件付確率     により表される．このとき環境からエージェントへ報酬  が確率的に与えられるが，その期待値は条件付期待値      により表される．すな
わち， は状態遷移の条件付確率     と報酬の条件付期待値      により表される．ここで，条件付を   に進めてステップ  へ戻る．

確率     と条件付期待値      の条件部が，時エ−ジェントは利得（    最も単純な場合，報酬の総刻 の状態  およびそのとき選択する行動  のみであるこ計）の最大化を目的として，状態観測から行動出力へのマッとから，時刻 以前の状態や行動の履歴に依存しないこと

ピング（政策（ ）と呼ばれる）を獲得する．

が分かる．この性質はマルコフ性と呼ばれる．

 時刻

エージェントは各時刻において何らかの規則に従って行

環境とエ−ジェントには一般に下記の性質が想定される．
エ−ジェントはあらかじめ環境に関する知識を持たない．

動  を選択するが，強化学習における学習目標は，後述す環境の状態遷移は確率的．

る評価規範を最大化するような行動選択の規則を見出すこ

報酬の与えられ方は確率的．

とである．このとき，環境のマルコフ性により，エージェ

状態遷移を繰返した後，やっと報酬にたどり着くようントが見出すべき行動選択の規則は，状態  を条件部としな，段取り的な行動を必要とする環境（報酬の遅れ）．

た行動  の条件付確率分布   で表現すれば十分であ

強化学習では，環境のダイナミクスをマルコフ決定過程

る．この行動選択の規則をここでは政策と呼び  と表す．

     によってモデル化し，学習アルゴリズムを解析するのが一般的である  ．本稿では， モデルおよび代表的な強化学習法として知られる  !"   法と #!  を中心に理論的な基礎にまた，この政策  のもとで状態  において行動  を選択する確率を    と表す．

 の最適性：割引報酬による評価
ある時間ステップで実行した行動が，その後の報酬獲得

ついて解説する．

にどの程度貢献したのかを評価するため，その後得られる¾ º 強化学習の基礎理論と呼ばれる．エージェントの学習目標は，利得を最大化す

 マルコフ決定過程（）モデル
環境のとりうる有限な状態集合を  $          ，エージェントがとる有限な行動集合を  $          

では，以下に示す割引報酬合計による評価を利得とする場

報酬の時系列を考える．報酬の時系列評価は利得計測と制御 第  巻 第  号  年  月号

  

ること，あるいはその政策を求めることである．強化学習
合が多い．ある時刻 の状態，あるいはそのとき実行した行動の利得を以下で定義する：

$         $












ただし  は時刻 の報酬， は割引率 % であの期待値は， ステップあたり 

る．この





 の確率

で停止するエージェントが得る報酬合計の期待値と等価である． において割引報酬合計の評価がよく用いられる理由は以下のとおりである：
実環境では環境が変化したり故障等で停止する可能性

 最適政策と状態行動価値関数

存在する．これを最適政策   という．最適政策は複数存在
することもあるが，全ての最適政策は唯一の状態価値関数を共有する．これは最適な状態価値関数



この     





 '

は以下に示す *   の最適方程式を満たす：

 $  )¼         



 





のない政策  （定常政策という）をとるとき，状態  から  $と呼ばれ，以 においてエ−ジェントが時間とともに変化すること $  )を  に近づけると，平均報酬の最適政策に一致するような割引報酬評価における最適政策を得る．



下に定義される：
 へ遷移する状態遷移確率     は以下で与えられる：¼  となるとき，政政策よりも優れた，あるいは同等な政策が少なくとも  つするのは妥当ではない．
割引率





策  は  より優れているという． では，他のどんながあるため，時系列上の全ての報酬を同じ重みで考慮
計算処理上，値が発散することがなく都合が良い．



全ての状態  において+!

また，全ての最適政策は，以下に示す唯一の行動価値   関数を共有する．



また，状態  からの１ステップの遷移に伴って得る報酬の
期待値 






 は以下で与えられる： $         ¼  

エージェントが定常政策をとるとき，式  で表された利得の期待値は，時刻 における状態  だけに依存する．

すなわち利得の期待値は状態  の関数になり，これを状態
価値 
値





   関数と呼び

 と表す．この状態価

 $











 















   

 



 





 









 

¼











 

  



 

$ 



 






 



¼



 )




       ,割引報酬最大化と平均報酬最大化
を  へ近づけると，ある割引率



以上の割引

 

  

 の解法：政策反復法と価値反復法
 の 状 態 遷 移 確 率     と 報 酬 の 期 待 値     が与えられたもとで最適方程式 + または ,

を解いて最適政策を求めることは，強化学習に対してプラションを含む非線形方程式になっており，これを解く方法は





 









       

ンニングと呼ばれる．上記の最適方程式は  ) のオペレー












      

策は平均報酬評価に関しても最適政策となる．

       $

率における最適政策は全て同じになり，このときの最適政   





 を用




 

 

 に等しく，またこの # 値を持つ行動  が最最適方程式を満たす：

割引率

      

適な行動である．この    は以下に示す *   の








# 値は

遷移で得る報酬の期待値）＋    という具合に式 & で与  '

表す．   が与えられた場合，状態  における最大の

いた連立方程式 ( を得る：



後，ずっと最適政策をとりつづけるときの利得の期待値を（   目の遷移で得る報酬の期待値）＋  （   目の遷移で得る報酬の期待値）＋    ＋   （   目の

  $  )    は最適な # 関数と呼ばれ，状態  で行動  を選択

 は，（   目の遷移で得る報酬の期待値）＋

えられ，この無限級数の式から式 ' および





 



 








 



 

     &( 種類あるが，これらはダイナミックプログラミング !
      と称される．一つは，政策反復

法      - と呼ばれ，政策の改善と価値関数の計算を交互に繰り返す方法で，もう一つは価値反復法と呼ばれ，式 + または , を反復法を用いて数値計
算により解く方法である．

計測と制御 第 $/ 巻 第号 /" # 年月号

 【政策評価】ある定常政策について以下の状態価値 Îロなど）に初期化する．

を求める：

Î

 Á

È 

 【価値関数値の更新】全ての £   について以下の式をÊ

計算して値を代入：

 【政策改善】全状態  において以下の式の値が最大になるよう政策を から ¼ へと変更する．この計算で用いる価値関数は政策 のものを利用する．

¼
   

 ¼ ¾

図

政策反復法による  の最適政策の求解





ただし
は左辺の変数に右辺の計算結果を代入するオペ
レーションを表す．右辺に左辺と同じ変数が使われているが，これは更新前の古い値を用いることを意味する．
 【打ち切りの判定】処理手順  を値が収束するまで繰り返す．

図（  ） 政策反復法
エージェントが定常政策  をとるときの状態価値関数




¼ ¾

 ¼     ¼    ¼ ¾ £¼  ¼ となり変更すべき行動が無いとき，は最適政策なので処理を打ち切る．さもなければ¼ として手順 へ戻る．

£   ¼
 ¼  ¼ 

 【打切り判定】 ¼ 政策 【初期化】全ての状態  について £   を適当な値（ゼ価値反復法による 

方程式の求解が % であるものに限定され，そのため状態と行動が有限な

 の方程式を式 ( で示したが，この方程式は線形な

 では決定論的政策の個数が有限になるので，政策反ので比較的容易に解ける．まず式 ，  で示した状態遷復法が有限のステップ数で最適政策を見出すことが証明さ

移確率     および報酬の期待値   を以下のよう






 


れている．ここでは強化学習法との関連を述べるため，あに行列で表す：





$

$

えて確率的政策を用いて表現した．









 
    
















  










         








'






  












      

 $

 





（ ） 価値反復法

      



ここでは式 , の行動価値関数に関する *   最適方.

程式を数値反復計算で求める方法を紹介する．図  にその概要を示す．状態  における最大の # 値を持つ行動  が最適な行動であるので，行動価値関数を求めれば最適政策は容易に求められる．






 



 






¿ º 強化学習アルゴリズム/ 環境下での強化学習では，状態遷移確率    

や報酬      についての知識を予め持たないため，環 

これらの行列を用いて式 &' ( を書き直し，さらに   に境とのやりとりを通じてこれらの情報を得なければならなついて解くと以下のようになる：

法や価値反復法を強化学習問題へ拡張したものと考えられ，

  $  $             $ 


確率的  とも呼ばれている．



さて，ある政策  のもとでの価値関数



%

 が得られると，政策改善の手がかりを得ることができる．ある状態 
においてのみ  とは別の政策  に従って行動をとるとき，




¼

 

¼





¼

 







  %

い．以下に紹介する強化学習法は，先に紹介した政策反復



 



  アルゴリズム

まず政策反復法の強化学習版と考えられる   !"  
法を紹介する．この手法は，確率的政策に従って行動を選択する   と呼ばれる要素と，状態価値を推定し，その情報から政策改善すべき方向を導く    と呼ばれる要素より構成される．図 & にアルゴリズムの概要を示す．図中に示された変数 1   は，政策反復法の式  の右辺に相当することに注目してほしい．また，図中の状態価値が成り立つならば，その状態  だけ政策  に従う新しい政2   の更新式は，確率的価値反復法による状態価値関数

策の状態評価値がもとの政策  よりも改善されることが証の求解に相当する．

明されている．この原理を利用して政策を改善していく．図 にその概要を示す．オリジナルの 0 の政策反復法

  !"   法は，政策  すなわち行動選択確率関数において，正規分布を適用することなどにより連続値の行動

では，政策  は全て決定論的政策，すなわち各状態においへ拡張することが容易であったり，自然勾配  てある行動を選ぶ確率が  で，それ以外の行動を選ぶ確率  や政策勾配定理 などを利用した非常に効率の良計測と制御 第  巻 第  号  年  月号

!





 エージェントは環境の状態  を観測し，確率的政策 に従って行動  を選択 環境から報酬  を受取り，状態遷移後の状態  を観測 【政策改善】以下の を計算：      



図




 エージェントは環境の状態  を観測し，任意の行動選択方
法 探査戦略 に従って行動  を実行
 環境から報酬  を受取り，状態遷移後の状態  を観測
 以下の式を用いて行動価値の推定値を更新： £     





¾

 £   

Û!

 

    かつ を満たす時間 の関数（例えば    











など）となっているとき，#!   アルゴリズムで得る# 値は最適な # 値に概収束する  ．ただし環境はエルゴー

ト性を有する離散有限  であることを仮定する．その
他，解析については文献 を参照されたい．
（ ） 行動選択方法 探査戦略

よって行動選択はランダムでもよい．しかし，強化学習で

はまだ # 値が収束していない学習の途中においてもなるべ £         アルゴリズム

く多くの報酬を得るような行動選択を求められる．序々に

挙動を改善していく行動選択方法として，
!

 選択： 確率  でランダム，それ以外は最大 #値を持つ行動を選択．
2    に比例した割合で行ボルツマン選択： 

動選択，ただし  は時間とともにゼロに近付ける．
楽天的初期値      アルゴリズム
 は    の推定値 
2    を得るため

  456：# 関数の初期値を大きめの値に設定しておき，実行してい題やロボットなどへの適用において最も実績がある．
   すれば行動選択方法（探査戦略）には依存せずに成り立つ．



#! 





線形アーキテクチャによる  関数の汎化

回数選択し，かつ学習率  がい政策改善方法が提案されているなどの理由により，実問



上記の収束定理は，全ての行動を十分な回数選択しさえ

ただし は学習率で ， は割引率である．
 時間ステップ  を   へ進めて手順 へ戻る．

図

 

エージェントの行動選択において全ての行動を十分な アルゴリズム



Ü



 £   的  と呼ばれる所以である．

 £      
（  ）  の収束定理

ただし は学習率で  ， は割引率である．
 時間ステップ  を   へ進めて手順 へ戻る．

図   
      ならば，実行した行動  は好ましいものと考えられるので，状態  で行動  を選ぶ確率を増やすよ  ならば，実行しう政策 を更新する．逆にた行動  は好ましくないと考えられるので，状態  で行
動  を選ぶ確率を減らすよう政策 を更新する．
 【状態価値の推定値更新】  を更新：        ない状態!行動を選択しやすくする．
などの方法が提案されている．
（  ） 連続空間での行動価値関数表現#! の代表的な強化学習法であり，価値反復法の強化学習版と に代表される強化学習アルゴリズムの動作の考えられる．図 ( にアルゴリズムの概要を示す．ここで注

基本は，状態入力から状態・行動価値への写像関数を構築し目すべき点は，   !"   では何らかの政策  に従ってていくことである．状態表現の生成は特徴量抽出   

行動が選択され，学習の進行とともに政策が改善されてい)く（!  と呼ばれる）のに対し，#!   ではあは扱わず，予め与えられるものとするのが一般的である．状  に関連するが，強化学習ではこの部分について
!

る程度の条件が要求されるものの行動選択方法を規定する

態入力が連続空間の場合，このテクニックは汎化

政策  とは無関係に最適行動価値関数    や最適政策

7  を求められる点（3!  と呼ばれる）である ．

ルネットワークなど幅広い分野で研究されており，強化学

また，図  の価値反復法の更新式と図 ( の #!   や関数近似と呼ばれ，強化学習に限らずニューラ

習または動的計画法と関数近似法を組み合わせた計算法は  と呼ばれる．#! の更新式の違いに注目すると，価値反復法では # 値の計算 !   部分に状態遷移確率     を用いているのに対し，#!

の最適解への収束が保障される汎化法として線形アーキテ

クチャ 

 では状態遷移確率は未知なので用いていない．こ-    がある．これは固定された基れは，エージェントが実際に環境での遷移を繰り返して小底関数集合を用いて関数近似を行うもので，ラジアル基底

さな学習率  によって少しずつ更新していくことが，状態やシグモイド関数を用いたものなど様々だが，状態!行動入遷移確率で重み付けたサンプル平均をとることになり，図力を基底関数によって特徴ベクトル  に変換し，この線形 の価値反復法と等価な計算を実現している．これが確率重み付け和で # 値を表現する点で共通する（図 + 参照）．



計測と制御 第 $/ 巻 第号 /" # 年

月号




















 エージェントは環境の状態  を観測し，任意の行動選択方
法 探査戦略 に従って行動  を実行
 環境から報酬  を受取り，状態遷移後の状態  を観測 状態 ，行動 に対する特徴ベクトル Ü         






を何らかの方法を用いて生成する．ただし，区別が必要な状態"行動ペア間では必ず互いに線形独立になるよう設定し，ノルムを にしておく．
 特徴ベクトル  と重み変数  を用いて # 値を計算：



図  格子状タイリングによる特徴ベクトル生成例．状態
行動入力   が矢印の位置のとき，特徴量ベクトル         は，該当するタイル要素   ，
それ以外の要素は全てゼロ．



徴ベクトルのノルムは常に  となることが望ましい．
図 , は最も単純な特徴ベクトル生成方法の例を示す．２次元の入力空間を１種類の格子状タイリングによって分割
し，各タイル要素に特徴量ベクトルの要素を割り当てる．

 

 以下の更新式により重み変数  を更新する：

Æ    特徴ベクトルの生成方法は問題に応じて設計者が与える必要があり，図 ( の離散空間 #!   との整合性から，特 £    £    £        Æ

ただし は学習率で  ， は割引率である．
$ 時間ステップ  を   へ進めて手順 へ戻る．

図  線形アーキテクチャを用いた     状態!行動入力があるタイル要素内にあるとき，該当する特

徴量ベクトル要素の値は  に，それ以外の要素はゼロとする．# 値は，特徴ベクトル要素と同数のパラメータ変数 










を用意し，特徴ベクトルとの線形和で表す：2  $





 



ただし  は特徴ベクトル要素の個数である．# 値を変える

場合は，パラメータ変数  の値を調節する．線形アーキ
テクチャによる #!   は，図 ( の更新式に対して単純

な勾配法に基づくパラメータ  の更新で達成される：


 

2




 



Æ



2    $  なので，
式  より      Æ

&

図





































２種類の格子状タイリングをずらせて重ねる による特徴量ベクトル生成．大きな太線の枠は状態
行動の定義域，２つの小さい太線枠は入力に対応するタイルを表す．状態行動入力が矢印の位置のとき，
特徴量ベクトルに該当するタイル要素   ，  ，それ以外の全要素はゼロ．

つまり線形アーキテクチャを用いた更新では，更新するパラメータ  に対応する特徴量の要素の値  だけを使って簡で，扱う次元数が高次元になるとメモリ空間が次元数に対

単に更新できる，図 , のような単純なグリッド分割による線して指数オーダで増加するという「次元の呪い」の問題に

形アーキテクチャの更新式は，図 ( の離散空間 #!  

直面する．そこで，図 % のようなランダムタイリングをの更新式と全く同じになる．一般に，全ての状態!行動ペア

用いた特徴ベクトル生成方法が提案されている ．ある 

が互いに線形独立な特徴ベクトルで表現されていれば最適つのランダムタイル   は，入力空間  を構成する次元

行動価値関数への収束が保障される．図 . に線形アーキのうち，任意の１次元以上の複数次元（   テクチャを用いた #!   の処理手順をまとめる．

と呼ぶ）で定義される部分空間中の，ある矩形領域を表し，（ ） 高次元空間での特徴ベクトル生成

入力された座標  がその矩形領域である場合   $  を

図 / は格子状タイリングを拡張した " " による特

出力し，それ以外の場合   $ % である．矩形領域を構成

徴量生成の例を示す．この例では  次元空間に  種類のグする次元や矩形の範囲・大きさなどは，タイル毎にランダ

リッドを重ねているが，一般に多次元空間において多数のムに与えるが，その与え方には統計的性質を持たせる ．こ

グリッドをランダムに重ねて用いる．しかし，" " は隙のように，ある１つのタイルは空間を構成する次元の一部

間なく並べられたタイリングを複数用いることが特徴なの分で構成される空間の，とある領域として処理するが，こ計測と制御 第  巻 第  号  年  月号



1

a2

Random Rectangular
Coarse Coding

T5

Rate of linearly independent vectors

T9
T8

T7
T6
T3

T2

0.8

0.6

0.4

Regular Grid Coding

0.2

T1
T4

a1

0
10

100

Number of random features

図

２次元空間での  個のタイルによるランダムタイの矢印で示
リングの例．タイル ! は部分空間される区間で定義されるタイルのため，それ以外の空間  では全領域をカバーするタイルになる．タ
イル ! も同様．

のタイルを空間全体からみると，定義される部分空間中では範囲の限定された矩形だが，それ以外の空間では全領域

Rate of linearly independent vectors

1

0.8

Random Rectangular
Coarse Coding

0.6

0.4

Regular Grid Coding
0.2をカバーするタイルと同義である．ランダムなタイルを用いることに抵抗を覚える読者が多いと思うが，実験してみ010

イリングに比べ，比較にならないほど高性能である．図 

図はそれぞれ  次元・. 次元の入力空間に対し，ランダムタ
イリングと格子状タイリングによって特徴ベクトルを生成した場合の任意の近傍点 %%% 個における線形独立性の割合を示したグラフである．線形独立の割合が高いほど，任意の  点間を区別可能であることを意味する．任意の近傍点のうちの  点は，各軸が 8% 9 の範囲に限定された入力空間に一様分布で生成し，もう  点は先に生成した点を中心に各軸に標準偏差 % 共分散 % の多次元正規分布で生成した．ロボットの強化学習では，このように空間的に少しだけ離れた  点を区別して全く別の制御を行う必要がたびたび生じるが，同じ個数の特徴量を用いた場合，特に高次元入力空間で多数の特徴量を用いた場合においてランダム
タイリングは格子状タイリングよりはるかに優れた性能を

100

1000

Number of random features

ると驚くべきことに同数の特徴量を持つ等間隔の格子状タ

多次元空間において生成した特徴ベクトルの要素数と任意の近傍点における線形独立性の割合．上が 次元，下が  次元空間での結果．" # 
$   % #  はランダムタイリング，"$  # #  は等間隔の格子状タイリ
ングを表す．

9+)  )  $6  $） 2) : 2  ' ) ! .:  ; 0! 5.)  '  '() 1 <5 *  %%7） 2) : 2) <++) ) 201) 2 = < ) >!
*+/ 4  <1  :  ; 0 ?1
@    )    - + 5 *0 2/   -5*2 )  &6 $ $） A () B,BC =/ ) *!
1 + -!
"; 0) < 1 ; 0 7) &%6%  %%
&） 吉本 潤一郎，銅谷 賢治，石井 信：強化学習の基礎理論と応用，
 6 7 
計測と制御) 9+) -)示している．この理由は，格子状タイリングでは特徴ベク
トルの要素のうちただ１つが  でそれ以外全て % という不［著 者 紹 介］

必要に大きな制約のもとで特徴ベクトルを生成しているのに対し，ランダムタイリングではそのような制約が無いた

木村 元めと考えられる．

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

（  年 % 月 & 日受付）
参） '( )考文 献*  (+) ,-! .-" /  *"00.) 1 2  %%$） 3 ( ) 2!  -  + *+/ 4 )    - +5  *0 2/  )   6 7 ） 木村 元：ランダムタイリングと 488"+0 を用いた多次元状態"行動空間における強化学習，計測自動制御学会論文集)

計測と制御 第 $/ 巻 第号 /" # 年月号