多次元状態 行動空間での強化学習             

九州大学 大学院工学研究院 海洋システム工学部門 ○木村 元○                                                                                                                                                                

はじめに

本論文では，ランダム矩形タイルを用いて状態行動空間を汎化し， 値や行動選択確率分布を表現する方法を紹介する。次に，多次元で連続な行動空間を細かく離散化するが，  サンプリングによって空間爆発を回避しつつ行動選択を行う方法を提案する。  は代表的強化学習手法であるにもかかわらず，行動選択の困難さから高次元の行動空間を持つロボットへ実装することが困難だったが，本手法により容易に実装できることを示す。

  (  )'!" # Ü*    $% !  # &!

Û'-          !    #         "  )       +     

連続空間での行動価値関数表現
  



(  ,' $    

!      #を用意し，特徴ベクトルとの線形和で表す： 

% !  # & #!)#

ただし  は特徴ベクトル要素の個数である。 値を変える場合は，重み変数  の値を調節する。線形アーキテクチャによる   は，単純な勾配法に基づき重み変数  を更新することで達成される：   +     に代表される強化学習アルゴリズムの基本は，状態入力から状態・行動評価値への写像関数を構築していくことである。状態表現の生成は特徴抽出に関連するが，強化学習ではこの部分の学習は行わず，予め与えられたものを使うが一般的である。状態入力が連続空間の場合，このテクニックは汎化 ! + # や関数近似と呼ばれる。  の最適解への収束が保障される汎化法として線形アーキテクチャがある。これは固定された基底関数の集合を用いて関数近似を行うもので，ラジアル基底やシグモイド関数を用いたものなど様々だが，状態行動入力を基底関数によって特徴ベクトル Ü に変換し，このベクトルの線形重み付け和で  値を表現する点で共通である（( )）。特徴ベクトルの生成方法は問題に応じて設計者が与える。離散空間   との整合性から，特徴ベクトルのノルムは常に ) とするのが望ましい。

  .
% !  #式 !)# より % !  #Æ!,#

 &  なので，
 .   Æ!/#

つまり線形アーキテクチャを用いた更新では，更新する重み変数  に対応する特徴の要素の値  だけを使って簡単に更新できる。( , のような単純なグリッド分割による線形アーキテクチャの更新式は，離散   の更新式と同一である。一般に，全ての状態行動ペアが互いに線形独立な特徴ベクトルで表現されていれば最適行動価値関数への収束が保障される 0,1。( / に線形アーキテク
チャを用いた   の処理手順をまとめる。

( , は最も単純な特徴ベクトル生成方法の例を示す。
２次元の入力空間を１種類のグリッドタイリングによって分割し，各タイル要素に特徴量ベクトルの要素を割り当てる。状態行動入力があるタイル要素内にあるとき，該当する特徴量ベクトル要素の値は ) に，それ以外の要素はゼロとする。 値は，特徴ベクトル要素と同数の重み変数 ¾º½

高次元空間での特徴ベクトル生成

前節で説明した単純なグリッドタイリングやこれに準ずる
方法では，高次元空間においてメモリ爆発の問題を引き起) エージェントは環境の状態

を観測する。

a2T9 エージェントは任意の行動選択方法 探査戦略 に従って行T5T8

動  を実行する。

 環境から報酬  を受け取る。

T7

 を観測する。

 状態遷移後の状態

T6

 状態 ，行動  に対する特徴ベクトル Ü    を何らかの方法を用いて生成する。ただし，区別が必要な状態 行動ペア間では必ず互いに線形独立になるよう設定し，ノルムを にしておく。

 特徴ベクトルの要素数と同数の重み変数  を用いてを計算：

T3T1

値T4         ただし(  3' $     Æへ進めて手順へ戻る。

(  /'               3   "

    )

            )

5

 3 

         ,    6  , 

"   



P(a)

selecta2

こす。そこで，ランダム矩形タイルを用いた特徴ベクトル生成方法を紹介する。ある ) つのランダムタイル !# は，
入力空間  を構成する次元のうち，任意の１次元以上の複数次元（   と呼ぶ）で定義される部分空間中の，ある矩形領域を表し，入力された座標  がその矩形領域である場合 !# & ) を出力し，それ以外の場合!# & 2 である。矩形領域を構成する次元や矩形の範囲・大きさなどは，タイル毎にランダムに与えるが，その与え方には統計的性質を持たせる 。このように，ある１つのタイルは空間を構成する次元の一部分で構成される空間の，とある領域として処理するが，このタイルを空間全体からみると，定義される部分空間中では範囲の限定された矩形だが，それ以外の空間では全領域をカバーするタイルと同義である。( 3 に , 次元での例を示す。ランダムなタイルを用いることに抵抗を覚える読者が多いと思うが，実験してみると驚くべきことに同数の特徴量を持つ等間隔の格子状グリッドゴーディングに比べ，比較にならないほど高性能である。

      4              は学習率， は割引率。

 時間ステップ を a1  以下の更新式により重み変数  を更新する：
ÆT2a1(  6' $     "                 !#     +     )  ,    "    

 ! # に従って，どれか１つが選ばれる。( 6 は , 次元の行動空間において２次元行動空間を格子状に分割し，各メッシュの持つ確率に応じて行動選択する様子を示す。フ
ラットな行動選択では，, 次元空間 )  , で離散化された全ての格子について確率を計算し，その比率に基づいて格子を一つ選択して行動出力とする。行動の確率  ! #は，一般に状態 において行動  に割り当てられた  値!   # に応じた以下のボルツマン分布とする：
 ! # &高次元行動空間での行動選択

前節の汎化方法によって高次元空間において複雑な状態行動評価関数（ 関数）が表現できるが，この  関数に従って行動を選択する最も単純な方法は，フラットな行動選択法である。これは，行動空間を全て細かい格子状に離散化し，各超矩形領域に対して確率を割当て，ルーレット選択によっていずれかの超矩形領域に相当する行動を選択するものである。本稿では，連続な行動空間を各次元毎に等しく 分割して格子状に離散化する。よって行動空間を次元と仮定すると  コの行動  ! & )  #へ離散化される。行動は，各行動  毎に定義された確率      

  



!6#

 

一般的なボルツマン行動選択では 
! # & 2 かつ ! # &) であるが，行動空間の次元数が高い場合 ! # を状
態 における  値の平均値，! # を状態 における
 値の標準偏差とすることを推奨する 。これは  値の大きさによって行動選択の挙動が温度パラメータ  を無視して大きく変化してしまうのを防ぐためである。しかしながら式 !6# で明らかなように，フラットな行動選択では全行動空間の  値を調べる必要があるため，行動次元数が ,〜/ 次元程度ならば実行可能だが，次元数がさらに高 値の平均値や標準偏差は，状態 において行動  を 値に関係なく一様分布で 〜 個選んだときの各行動の 値から統計的に計算した値で良い。

 一様分布で入力が与えられたとき，ランダムタイルのヒット確率の期待値がある一定値（  ％程度）になるよう決める。

,

した条件付確率により , をサンプルする。これで反復 )回分であり，さらに !/# では !,# で選んだ , を固定した条件付確率により再び ) を選ぶ。このような反復を十分な回数繰返した結果得られた ) , を最終的な行動出力とする。  サンプリングでは，反復回数についての理論的な下限については現在のところ明らかにはなっておらず，実験的に決められているのが実情である。( 7 で示した
例題のように , 次元程度の空間での 7 × 7 程度の粗い分割
では，フラットな行動選択との計算量的な差はあまりないが，行動次元数や分割数が増加すると，その差は顕著に現れる。例えば行動空間が < 次元で各次元を )2 分割する場
合，フラットな行動選択では各メッシュにおける重みの計算を )2 &) 千万回行わなければならないが，  サン
プリングでは )2  <（反復回数）程度であり，反復回数を数十回程度に抑えればフラットな行動選択法に比べ，１万分の１程度の計算量で済む。

くなると離散化した行動空間が指数的に増大するため，記憶容量的にも速度的にも実行不能になる。
P(a)

a2a1

P(a)
selecta2a1(1)select一般的な   サンプリングでは行動選択確率分布自体
は式 !6# と同じだが，各行動座標軸毎に処理を行うため，記法を以下のように整理する。フラットな行動選択と同様，行動の次元数 で，行動空間は各次元毎に 分割により離散化されているものとする。ある多次元行動  について，各行動次元毎に分解して次のように表す： & !        # た
# は   
だし各次元の要素  !ただし   ) ,
ただし   ) ,
 である。ある状態
行動  に対する  値は，!  # & !         # と表す。この 値は，フラット選択における値と同一である。  サン
プリングの  回目の反復においてサンプルされた行動要素を  !#  !#     !# と表す。このとき， . ) 回目の反復で行動要素は以下の確率に従ってサンプルされる：

P(a)

a2

a1(2)
select
P(a)

a2

a1(3)

(  7' $       "     )  

          )    !/#         

   

 !  !#  !#      !## !         # , 

 !  !#  !#     !##ここで，条件付き確率  !         # は，以下のボルツマン分布で与えられる：     , ! . )# ! . )#     !)#       !,#    !)#   8  !  !#  !#     !##            

 ! . )# & )    ,   !,# 

½ ¾    

   

 ½
¾     

フラットな行動選択と比べると，考慮すべき行動が１次元ずつになり，式 !6# と同じような処理を繰り返し行うようになっただけである。このとき，全行動空間について  値を調べる必要がないのが大きな利点である。

そこで，高次元空間における確率分布に従って効率良くサンプリングする方法として   サンプリングを用いる行動選択法を提案する。  サンプリングとは，高次元の確率変数において，注目している次元以外の次元の変数の値を固定し，そのときの条件付確率分布を用いて ) 次
元ずつ順番にサンプルを行っていく処理を全ての次元に対して十分な回数繰返し，最終的に得た値をサンプルとする
9:   9 ; 法（9;9; 法）の一種である。( 7 は , 次元の行動空間における   サンプリン
グの様子を示す。, 次元空間 )  , で離散化された全ての格子における確率は ( 6 のフラット選択の場合と同じだが，) 次元ずつサンプルを行っていくので，( 6 のような全行動空間における確率を全て計算するような処理が不要となる。( 7 の !)# は , を固定した条件付確率により) をサンプルし，その下 !,# では !)# で選んだ ) を固定

この   サンプリングによる行動選択は， において   !   # を探す場合，  サンプリングを行う過程で見つかった最大の  値を用いるなど近似的に与えることになるが，前節で説明したランダムタイリン
グと組合せると，/〜< 次元を超える高次元の行動空間を持つ強化学習問題に対して非常に効果的である。

実験( = に示す冗長アームのリーチングタスクに提案手法を適用した。アームは < 本のリンクが関節を介して直列に接/

3025
Averaged Reward (1000 steps)

GOAL

Random rectangularcoarse coding 200x200
20Regular grid coding(2x2x2x2x2x2x2x2)x(2x2x2x2x2x2x2x2)

151050020000(  <'40000
60000
Learning Steps  100000*      )2

 <8       


80000

 

:      :  )222     (  =' $       

          :   8    8     :   :     

条件の一つとして特徴ベクトルが状態間で線形独立であることはすでに述べた。一般的な格子分割による離散化や，ラジアル基底関数による関数近似は，ほぼ全ての領域で単位ベクトルに近い線形独立な特徴ベクトルが生成されることが保障されるが，特徴ベクトルが単位ベクトルであることは収束の条件としては必要ではない。また，本タスクをみれば明らかなように，連続な状態行動空間におけるタスクは，本質的には複雑さが小さく，区別が必要な状態や行動の領域はあまり多くないと考えられる。提案手法であるランダムな矩形タイルによる特徴ベクトル生成法は，上記のような本質的に複雑さの小さい連続な状態行動空間におけるタスクにおいて，区別が必要な状態や行動の領域において線形独立な特徴量ベクトルを生成しやすいと考えられる。つまり，提案手法では特徴量ベクトルが単位ベクトルに制限されていないため，タスクに無関係にランダムに配置されたタイルでも，線形独立な特徴量ベクトルになりやすく，適切な関数近似が行えるのではないかと考えられる。また、行動選択については，離散   において一般的なボルツマン行動選択を     というテクニックによって高次元行動空間での実行を可能とした。さらに，ランダムな矩形タイルによる特徴ベクトル生成法は，    において計算処理を簡略化できるため，これらの組合せは効果的である。

 

続されており，, 次元平面上を動く。行動も < 次元で，目標とする関節角度を表す。行動により目標角度が与えられると，その方向へ < 次元状態空間中を直線的に移動し，途中で障害物あるいはゴール領域に触れるか，目標座標に到達すると，イベントが発生して次の意思決定を行う。問題設定の詳細は文献 031 を参照のこと。
強化学習エージェントは，< 次元の状態入力の各次元を)2 分割して離散化する。< 次元の行動についても同様に各次元を )2 分割して離散化する。この空間に対し，ランダムタイルを ,22 個生成して特徴ベクトルとする。ランダムタイルは，一様分布で入力が与えられたとき、タイルのヒット確率が 2) になるように    の次元とタイルの幅に関する統計量を計算し，これに従って確率的に生成する。  サンプリングの反復回数は 32 回，割引率  & 24，温度  & 23，学習率  & 2, である。参考までに，状態と行動空間を , & ,67 個のタイルへ均一にグリッド分割した場合と比較した。また、フラット行動選択を行った場合との行動選択時間の比較を試みたが、フラット行動選択におけるボルツマン分布の分母の値が大きくなり過ぎて計算に支障をきたすなど実装上の問題が発生し，実行不能であった。( < に学習の様子（)2 試行平均）を示す。

 

実験結果より，タスクの学習に必要なタイル数（特徴量）については，高い次元の問題が，多くのタイルを必要とするとは限らないことが考察される。本問題では，アームの移動コストを考えず，意思決定ステップ数だけで評価しているため，最適なパスが無数に存在するために，,22個という比較的少ないタイルでも最適解を容易に発見できたと考えられる。しかし，同じような分割数・タイル数でも均一にグリッド分割した場合には全く学習できなかった。
ランダムタイリングにおける細かい分割と粗い分割の混合や，全ての次元の変数を考慮するのではなく一部の次元の変数に注目した汎化が重要と考えられる。線形関数近似を用いた > 関数の強化学習では，学習が収束するための

0)1 - :  ;?; @ A B'  *  9   *  <
0,1 5 :A
0/1 FAB C '

,=4D,4, !)44,#  : B E $  F?C'EC

 "!)447#  F  5  $' E   *

' $  E $ 5 5:  9 

B !)44<#
031 木村 元：ランダムタイリングと    を用いた多次元状態行動空間における強化学習，計測自動制御学会論文集 >3, ), )//7D)/3/ !,227#3