強化学習における高次元数の行動空間の扱いについて−ハッシュと   を用いた行動選択方法の提案−○木村 元
九州大学 大学院工学研究院 海洋システム工学部門

              ○                                                               !        
            !               !                             
   "      !                !
#            $                  
はじめに「 次元の呪い」によってたちまち空間爆発を起こし ，記憶容量的にも計算量的にも実行不能になってし まう．また，せっかく膨大な空間を「汎化」によって少ないパラメータ
強化学習は，ロボットの制御規則を自ら発見し改善していくための学習制御方法とし て有望である ．脚型移動ロ で扱おうとし ているのに，細かい離散化によってパラメーボットやヒューマノイド 型ロボットなど の多数のアクチュ タ数を爆発させては意味がない．だからといって離散化をエータを有するロボットにおいて動作規則を学習する場 粗くしすぎてもきめ細かな行動選択ができないため制御の合、状態空間だけでなく行動空間についても高次元で膨大 質が落ちるというジレンマがあった．

%&'な空間であり、状態の評価方法だけでなく行動空間での行動選択方法および 学習方法にも工夫が必要である．

#%(' )*)%+'

本論文では ，まずハッシュの一種であるランダ ムタイ
リングを用いて状態 行動空間を汎化し ， 値や行動選択確率分布を表現する方法を提案する．次に，多次元で連続サンプリングにな行動空間を細かく離散化するが，よって空間爆発を回避しつつ行動選択を行う方法を提案すやなど ，これまで代表的強化学習る．
手法だったにもかかわらず，行動選択の困難さから膨大な行動空間を持つロボットへ実装することが困難だったが，本論文の手法により，容易に実装できることを示す．

#

代表的な強化学習法であるやは離散的な状態・行動を対象とし ている．そのため連続な状態空間や行動空間における状態評価関数や状態 行動評価関数を表現するために 関数近似とし てを用いる
方法 ，ファジィを用いる方法 ，過去の経験を用いてなど が提案されている．特に状態空間補間する方法の次元数が高い場合，次元の呪いを回避するための有望な手段としてタイルコーデ ィングの一種であるハッシュを使問題の定式化うべきという主張がされている ．これは，ランダムに選ばれたいくつかの状態変数で作られる空間中に大きさや位置がランダムなタイルを配置し ，そのタイルを，状態 状態空間を ，行動空間を ，上下界を持つ実数の集合を価値関数を表現するための特徴ベクトル要素１つに対応  と表す．各時刻 でエージェントは状態観測   に基させる．状態入力がそのタイル領域内に入ると対応する特 づいて行動    を実行し ，状態遷移に伴う報酬   
徴ベクトル要素の値が１になり，それ以外の場合はゼロに を得る．本論文が環境のモデルとして仮定するマルコフ決
では，一般に次の状態や報酬は確率的で，なる．このハッシュコーデ ィングによる状態特徴ベクトル 定過程
では次の状態生成は，タイルの初期配置が学習性能に大きな影響を与え その分布は  と  にのみ依存する．
る問題点があるが，依存関係の考慮が必要な状態変数集合   は遷移確率       に従って決まり，報酬  もとそうでない状態変数を区別したり，重要な状態変数値の 期待値     によって与えられる．エージェントは予め組合せをエキスパートの知識から予め与えておくことが容       や     についての知識を持っていない．
易など 多くの利点を有する．このように，高次元空間にお 強化学習の目的はエージェントのパフォーマンスを最適化いて状態評価値や状態 行動評価値の汎化については多く する政策を得ることである．無限期間のタスクにおける自の手法が提案されているが，高次元の行動空間における行 然な評価規範として，以下のような割引報酬の合計がある．
動選択方法および学習方法については，あまり注目されてこなかった．連続な行動空間を扱うための最も単純な接近  
法とし ては，行動空間を全てメッシュに区切り，状態入力
 に応じ て各行動メッシュに対して 値に応じた確率を割当てることが考えられるが，行動空間の次元が高くなると 割引率    は未来に得るであろう報酬の現時点でのを表す．
重要度を表し， は時刻 の評価値

    %+', ,    .).
%/'

%0'%1'%+' #)*), 2,,-,-,

 2--

3

#

40

½



,0-,-

 2

,-a2
T5

T800/

T7
T6T30/  ）に対するランダムタイル   （ただし     の２種類のタイル集合による特徴量ベクトルを生成する．
特徴量ベクトルを用いて関数近似を行う場合，絶対和ノルムが一定値（ 理想的には ）であることが望まし いので，から各タイルの値を引いた値を要素とするベクトルを生成し，これを付加する．すなわち，特徴量ベクトルはタイル数の 倍の要素になる．さらに，特徴量ベクトルは絶対和ノルムが１になるよう正規化する．状態に対するタイル
特徴量   と行動に対するタイル   の間は重み変数 で接続する．状態 ，行動  に対する状態 行動評価値（ 値）は以下のように計算する：

T9,-T2,-

#, -3T1

   T4a1

 , -  ,-  ,8-#5   06 ２次元行動空間での ( 個のタイルによるランダムタイリングの例．タイル "& および "7 はそれぞれ部分空間 0 / の矢印で示される区間で定義されるタイルの

この 値を温度パラメータ  で除したボルツマン分布に従い，行動を確率的に選択する．各重み変数の値を調節することにより， 値および 行動選択確率分布が変化する．
本手法には以下の特徴がある：#

ため，それ以外の空間では 全領域をカバーするタイルになる．

 ランダムタイルが定義される行動空間の部分空間に ½  , -3  3  定義されている行動部分空間が互いに干渉していな

よって行動変数間の依存関係が表現できる．

では評価関数は以下に定義される．




 



いランダムタイルが存在することにより，互いの空間において独立に行動を出力することが必要なタスクを学習できる．例えば，ある行動変数の集合は固定された特定の値だけ，別の行動変数の集合では〜 の値を一様に出力することが求められるような場合にも対処できる．

,/-

 2

ただし   は期待値を表す．
における学習の目的は，各状態  において式 で定義される評価値を最大化するような最適政策を見つけることである．本論文で扱う環
境では，状態空間 および 行動空間  は多次元空間で表されるものとする．

/40

 ある状態入力において，行動空間中のある特定の領域と，別の特定の領域の行動のど ちらかを半々くらいの確率で出力することが求められる場合，それぞれに対応するタイルの重みを大きくすることで対応できる．

 ランダムタイリングによる高次元状
このように興味深い特徴が期待されるが，高次元の行動空態行動空間の汎化方法の提案
間全体に対して定義された重み関数のボルツマン分布に従う行動選択は，そのまま実行しようとすると組合せ爆発を
高次元空間において関数を汎化する方法は多種多様であ 起こし てし まうため工夫が必要である．
るが，本論文では多数のランダムタイルを用いる方法を提案する．これは状態空間における汎化のためのタイルコーディングの一種であるハッシュに基づいたアイデアだが，行高次元空間での複雑な確率分布によ
動空間については情報の流れ方が逆方向になっている．あるサンプリングと学習
は，入力空間 を構成する次元のうるランダムタイル
ち，任意の１次元以上の複数次元で定義される部分空間中のある矩形領域を表し，入力された座標 がその矩形領域
 従来手法：フラット な行動選択を出力し，それ以外の場合である場合である．矩形領域を構成する次元や矩形の範囲・大きさな ランダムタイリングによって高次元空間において複雑な状
どは，タイル毎にランダムに与える．このように，ある１ 態 行動評価関数（ 関数）や行動選択確率分布関数が表つのタイルは空間を構成する次元の一部分で構成される空 現できるが，この分布に従って行動を選択するための最も間の，とある領域とし て処理するが，このタイルを空間全 原理的に単純な方法は，フラットな行動選択法である．こ体からみると，定義される部分空間中では範囲の限定され れは，行動空間を全て細かい格子状に離散化し，各超矩形た矩形だが，それ以外の空間では全領域をカバーするタイ 領域に対して確率を割当て、ルーレット選択によっていずルと同義である．このようなランダムタイルを多数用いて れかの超矩形領域に相当する行動を選択するものである．
重み付け線形和することにより，空間全体に対して関数近 本論文では ，連続な行動空間を各次元毎に等し く  分割似（ 汎化）を行う．本論文では，状態空間に対するランダ して格子状に離散化する．よって行動空間を  次元と仮  ）および行動空間 定すると   コの行動          へ離散化さムタイル   （ただし    ,-, -30, -34



,-0/

#, 3 0-,8-,/-/

ではで選んだ  を固定した条件付確率
らに右下により再び  を選んでいる．このような反復を十分な回数繰返し た結果得られた    を最終的な行動出力とす
サンプリングでは，反復回数についての理論的る．
な下限についてはまだ明らかにはされておらず，実験的に決められているのが実情である．

P(a)select00 / 

a25 8a1/

1 1で示した例題のように 次元程度の空間を ×に粗く分割した程度では，フラットな行動選択との計算量２次元行動空間を格子状に分割し ，各メッシュ 的な差はあまりないが，行動次元数や分割数が増加すると，その差は顕著に現れる．例えば行動空間が 次元での持つ確率に応じてフラットに行動選択する様子．
分割する場合，フラットな行動選択において各次元をは行動空間を表し ，たて軸は確率を表す．
千万回行わなは各メッシュにおける重みの計算を 
サンプリングでは（反ければならないが，れる．行動は，各行動  毎に定義された確率   に従っ 復回数）程度であり，反復回数を数十回程度に抑えればフは 次元の行動空間に ラットな行動選択法に比べて１万分の１程度の計算量で済て，どれか１つが選ばれる．
おけるフラットな行動選択の様子を示す．この例では 次 むことになる．
 で離散化された全ての格子について確率を元空間 
サンプリングでは行動選択確率分布自体は式 と計算し，その比率に基づいて格子を一つ選択して行動出力同じだが，各行動座標軸毎に処理を行うため，記法を以下とし ている．のように対応させる．フラットな行動選択の場合同様，行動本論文では，行動の確率   は，一般に状態  にお の次元数  で，行動空間は各次元毎に  分割により離散化いて行動  に割り当てられた 値    に応じた以下 されているものとする．ある多次元行動  について，各行のボルツマン分布とする：
   
 た動次元毎に分解して次のように表す：
だし各次元の要素  ただし           は       
ただし          である．ある状態  行動  に対す          と表す．このる 値は，  
値は，フラット 選択における値と同一である．
サン
ただし  は正の値をとる温度パラ メータであり，値が大プリングの 回目の反復においてサンプルされた行動要素
きいと全行動の確率が均一に近づき，ゼロに近づくと大きと記する．このとき，回目のを    な 値を持つ行動の確率が大きくなる．このとき，各行反復における行動要素は以下の確率分布に従ってサンプル動の    はランダムタイルの値と重み変数の線形和かされる：ら計算される．

5   /6

0, # ,#,,&-/ 8&0/, -3 ,

#-



-

 

#;0,  , - , -  ,  , -  , -
  




--,-

 , ; 0
 , ; 0-& サンプリングによる行動選択法の3,0/,,- ,-このフラットな行動選択方法は，式 の示すとおり全行動空間の 値を調べる必要があるため，行動次元数が〜 次元程度ならばある程度実用になるが，次元数が高くなると離散化した行動空間が指数的に増大するため，記憶容量的にも速度的にも実行不能になる．

04 + - 9,9,, , - -- -#04 30 

//, -3+04, -5 / /0/, -, --,  , - , -   , -ここで，条件付き確率  ,   - は，以下のボ
, ; 0- 

ルツマン分布で与えられる：

提案,3 

9, ,
9, ,      
高次元空間における確率分布に従って効率良くサンプリン      
サンプリングを用グ するための方法の１つである
       サンいる行動選択法と適正度の計算法を提案する．
プリングとは，高次元の確率変数において，注目している よってフラットな行動選択と比べると，考慮すべき行動が次元以外の次元の変数の値を固定し ，そのときの条件付確 １次元ずつになっただけで式 と同じような処理を繰り返率分布を用いて 次元ずつサンプルを行っていく処理を し行うようになっただけである．このとき，全行動空間に全ての次元に対して十分な回数繰返し，最終的に得た値を ついて 値を調べる必要がないのが大きな利点である．
法（サンプルとする法）の一種である ．
は 次元の行動空間における 強化学習アルゴリズム
サンプリングの様子を示す． 次元空間  でのフラット離散化された全ての格子における確率はサンプ リングに選択の場合と同じだが， 次元ずつサンプルを行っていく ランダムタイルによる空間汎化とよる行動選択を強化学習アルゴリズムと組み合わせる．このような全行動空間における確率を全て計算ので，
法とアルゴ リズムを取り上げる．の右上 こではするような処理が不要であることが分かる．
状態空間に対するランダ ムタイル   （ ただし は  を固定した条件付確率により  をサンプルし ，ではで選んだ  を固定した条件付確率によ     ）および行動空間に対するランダムタイル  左下  ）の２種類のタイル集合によりり  をサンプルしている．これで反復 回分であり，さ （ただし       &0 

5 /,0-/,//#

 :   .  ..
%8' 5 8 //0 /5 /
0,0-- ,7- -000 #

5 80/

 0/

,-,-

P(a)
select

P(a)

a2
a2
a1
a1
(1)
selectselect

P(a)

P(a)

a2

a2

a1

a1(2)

(3)

5   86 格子状に分割された２次元行動空間を   サンプリング する様子．左上の図は行動選択確率分布，右上,0- は / を固定したときの条件付確率により 0 を選ぶ様子，左下 ,/- は ,0- で選んだ 0 を固定した条件付確率により / を選ぶ様子，右下 ,8- は ,/- で選んだ / を固定した条件付確率により再び 0 を選ぶ様子．0 / は行動空間を表し ，たて軸は確率を表す．

,- 

##

特徴量ベクトルを生成する．状態に対するタイル   とアルゴ リズムだが， 値の更新方法が異なる
次に同様ボルツマン
行動に対するタイル   の間は重み変数  で接続し ， だけである：状態  において状態 ，行動  に対する状態 行動評価値（ 値 ）は以下 分布で行動  を選択後，遷移先での状態  において行動 を選択し，以下のように値を更新する：のように計算する：,-, -3   #, -  ,-  ¼¼#¼ ¼ ,  -- ,04,  ,  - ;  , ; ,   ,1ここで # 値は式 1 で表されているので，式 04 で示される# 値の更新は，重みパラメータ  を以下のように更新

エージェントは状態  を観測し，以下のボルツマン分布に従って行動  を選択し 実行する：

することで行う：;  ,-  , -  , ; ,¼  ¼-,  -9,,  - ,00 , - 3,<
このように遷移先の状態で最大の#値を探索する必要が  9,,  - よりも実ないため，  アルゴ リズムの方が #
ただし 行動は式 7 の   サンプ リングにより選択する 装が簡単である．
ため，全行動について # 値を計算する必要は無い．行動
選択後，報酬  と遷移先の状態 ¼ を観測する．遷移先での状態 ¼ における # 値を使い，もとの状態  で実行した 
実験行動  の # 値を更新する：
5 & に示す仮想的なほふくロボットに本手法を適用する．
¼
,  ,  - ;   ;  9 ,  ,  学習目標は，ロボットを前進させるために ，アームを足,+- のように作用させる動作の獲得である．関節は位置制御
ただし  は割引率， は学習率（ 4    0 ）である．こ のサーボ モーターによって角度を制御される．各時間ス
こで # 値は式 1 で表されているので，式 + で示される # テップにおいて，エージェントは + つの関節モータの角値の更新は，重みパラメータ  を以下のように更新す 度および & つの足先のタッチセンサの状態という 0/ 個の状態量を要素とし た 0/ 次元ベクトルを観測する：関節角ることで実現する：
 は + 次元連続空間で定義され，タッチセンサ度 ¼  は 4 または 0 の / 値である．
 ;  ,-  , -   ;  9 ,  ,  ,(- 行動は，関節角度の目標値を指示し ，+ 次元ベクトルここで 9 ,¼  - を探す必要があるが，これはボルツ ,  - の各要素がそれぞれ関節角度を表す．行動ベク
マン分布の温度パラメータ  をゼロに近づけて   サ トルの各要素は %4 0' の範囲に限定される．行動が選ばれンプリングによって得た行動の # 値で代用する．
ると，モータは指示された目標位置へ動きはじめる．関節10.8100x100 trial 1
100x100 trial 2200x200

averaged reward

0.6

0.4

0.2

0-0.2

5   &6 多自由度ほふくロボットシミュレータ．右側が前方．足は & 本で，各足にはモータ / 個ずつ計 + 個取り

-0.4
05000

10000

15000

20000

25000

30000

35000

40000

45000

50000

learning steps

5   760/+

付けられている．各足の先端にはタッチセンサが付いていほふくロボット（ 状態入力 次元，行動出力る．状態は 関節の角度と 個のタッチセンサの値の計 次元）における学習の様子．横軸は学習ステップ，縦軸は次元で，行動は 個の関節の目標値で計 次元である．
ステップ毎の平均報酬を表す．

+0/&++0444

角度が指示された位置まで動くか，あるいはタッチセンサ る．これらの学習により得られた動作規則や，その評価値の値が変化すると，状態遷移の結果として報酬が与えられ， については，従来のガ ウス分布を用いた法次の時刻へ進む．関節のモータが目標位置まで動く途中でには及ばなかったが，ランダムタイルの配置を工夫しセンサの値が変化すると，そこで意思決定イベントが発生 たり，学習率やボルツマン分布温度パラメータを適切にスして動きが打ち切られるため，次のステップでの関節角度 ケジューリングすることにより，性能向上が期待できる．
は行動として出力された目標角度には一致しない．よって状態遷移には不確実性が存在する．報酬は，ボディが前進した距離与えられる．ロボットが後退した場合，報酬の値
考察は負値になる．

) .  %7'

0/

強化学習エージェントは， 次元の状態入力のうち関 については連続値を持つ各要素を分割
節角度  
 についてはそのして離散化する．タッチセンサ  にまま離散値として扱う．また 次元の行動  
分割して離散化する．よって離散ついては，各要素を億 千
空間の強化学習問題とし ては 状態数  とい千万，状態 行動空間は万，行動数う膨大な空間になる．この状態空間に対し ，ランダムタイ個生成して状態特徴ベクトル   とする．状態ルをのランダムタイルは，各状態次元についてタイル矩形領域としの部分空間を構成する要素とし て選択する確率をてランダムに作成する．ただし 要素を１つも選択しなかったタイルは除外する．ランダ ムタイルの矩形領域については，離散化された空間の境界に合わせて一様な乱数で生個生成成する．行動のランダムタイル   も同様にアルゴ リズムを適用する．
する．強化学習法として，サンプリングの反復回数は回，割引率 ，で一定，学習ボルツマン分布の温度パラメータ に設定する．
率

0404 3004+,04

044-/ 30 1/ 04,-48

  ,&4044

3 4 4/34(34&5 7 に学習の様子を示す．ここでは比較的学習に成功した例と失敗例を示している．成功例 ,5 7 中の   0においては，行動出力する際，およそ 8〜+ 個の行動空間のランダムタイルがアクティブになっている．ランダムタ
中
イルの設定によっては，ほとんど 学習しない場合もあり，その時アクティブになる行動空間のラのンダムタイルは 〜 個程度だった．状態 行動ランダムタに増やした場合が中のイリングをである．タイルを増やすと学習が安定する傾向が見られ  /-,5 7

4 0/449/44


5 7/449/44

 実験ではいくつかの種類のランダムタイリングを用いて実験したが，ランダムタイルの生成パターンによって，学習性能が大きく変わることがあった．こ次元という高次元の状態に対してたった
れは個のタイルにて特徴量を抽出するのでは少な過ぎ るものと考えられる．あまりに少ないタイルで状態 行動空間を表現することは，不完全観測問題に類似した問題を引き起こし てし まうため，学習不安定の要因になる．もっと十分な個数のランダムタイルを生成すれば，性能は安定するものと考えられる．

0/044


 実験において，状態空間に対するランダムタイルの/ 8中には，全く使用されていないものが 〜 割存在した．これは，実験で用いたシミュレータでは足先のタッチセンサが同時に 個以上反応する状態が存在しなかったり，タッチセンサが反応し ，かつ対応する足が上に持ち上げられている状態が存在しないな
ど の事情による．本論文では固定されたランダムタイリングを用いているため上記のような問題が生じているが，新しい未知の状態入力があるたびに，それに対応して適応的に新しいランダムタイルを生成するなど の工夫が考えられる．また，学習初期は大きな領域を持つランダムタイルによって学習し ，学習進行に応じて重要と思われる領域へ適応的に小さめのタイルを追加していくことにより，関数近似の精度を上げていくことも考えられる．

/

 ランダムタイリングによる状態行動空間の汎化法および  サンプリングによる行動選択方法は，ど%1'    @ .   *  B * )6 9   !  *    A2 !  .      )   
 ボルツマン分布に従って行動選択は可能であるが，
   018?/0+ ,0((+-
本提案手法を用いて最大の # 値を探すような計算を%<'   *6    C       
厳密に行うことは困難であり，温度パラメータ  を
6  9       
ゼロに近づけて近似的に行っている．しかし あまり         
 をゼロに近づけ過ぎ ると，単なるローカルサーチ
   048+?04&& ,0((1-になるが，今度は局所解に陥る可能性が出てくる．
6   サンプリングによって行動を選んだとし ても %+'   * B D  )6 *    )           " " 2 
式 & のボルツマン分布に従った選択になっている．
,0((+-本方法は ) .   法にも使えるが，式 & のボルツマン分布について適正度（     ）を計算する%(' $:  . @ .  B   26 " には，やはり全行動空間の重みを調べて合計する必>6 A    !    /<(?/(/要があるため，適正度の計算において空間爆発を起,0((/-こし てしまう問題がある．そこで，  サンプリ
ちらも計算処理が軽く，リアルタイム動作に向いた方法である．

ングによって行動要素を選択していく過程で適正度を計算して合計していくことにより，この計算を近似することが考えられる．

 状態行動空間の汎化方法としてランダムタイリングを提案したが，この部分は別の汎化手法に置き換えることも可能である．

 おわりに

本論文では，高次元の状態 行動空間における汎化および行動選択方法としてハッシュの一種であるランダムタイリサンプリングによる行動選択法を提案した．
ングと，アルゴ リズムと組合せ， 次元の状態およ
本手法をび 次元の行動空間を持つロボット学習問題へ適用し，高次元の状態 行動空間において学習することを示し ，学習はランダムタイルの初期配置に大きく依存する問題があることを示した．学習状況に応じて適応的にタイルを追加・削除する方法の検討は今後の課題である．

+  0/

%0' 深尾 隆則，稲山 典克，足立 紀彦：正則化理論を用いた連続的状態と行動を扱う強化学習，システム制御情報学会論文誌，=00 >00 7(8?7(( ,0((+-%/' 堀内 匡，藤野 昭典，片井 修，椹木 哲夫：連続値入出の提案，計測自力を扱うファジ ィ内挿型 #
動制御学会論文集 =87 >/ /<0?/<( ,0(((-%8' @    6 A    "" 2  ,0(((-%&' 木村 元，宮崎 和光，小林 重信：強化学習システムの設計指針，計測と制御 =8+ >04 10+?1/8,0(((-%7' 木村 元，山下 透，小林 重信：強化学習による４足ロボットの歩行動作獲得，電気学会 電子情報システム
部門誌

 =0//. >8 884?88< ,/44/-