ランダムタイリングを用いた多次元状態 行動の強化学習木村 元
九州大学 大学院工学研究院 海洋システム工学部門

                           

                                      



 

          





      !                                                 

 

 

                    "          はじめに

強化学習は，ロボットの制御規則を自ら発見し改善していくための学習制御方法とし て有望である  ．脚型移動ロ
ボットやヒューマノイド 型ロボットなど の多数のアクチュ
エータを有するロボットにおいて動作規則を学習する場
合、状態空間だけでなく行動空間についても高次元で膨大な空間であり、状態の評価方法だけでなく行動空間での行動選択方法および学習方法にも工夫が必要である．
代表的な強化学習法である   や #$#$
は離散的な状態・行動を対象とし ている．そのため連続な状態空間や行動空間における状態評価関数 %   

& や状態行動評価関数 %     
& を表現するために関数近似として '($' を用いる
方法  ，ファジィを用いる方法  ，過去の経験を用いて補間する方法  など が提案されている．特に状態空間の次元数が高い場合，次元の呪いを回避するための有望な手段としてタイルコーディングの一種であるハッシュを使うべきという主張がされている  ．これは，ランダ ムに選ばれたいくつかの状態変数で作られる空間中に大きさや位置がランダムなタイルを配置し，そのタイルを，状態価値関数を表現するための特徴ベクトル要素１つに対応させる．状態入力がそのタイル領域内に入ると対応する
特徴ベクトル要素の値が１になり，それ 以外の場合はゼロになる．このランダムタイルによる状態特徴ベクトル
生成は，タイルの初期配置が学習性能に大きな影響を与える問題点があるが，依存関係の考慮が必要な状態変数集合とそうでない状態変数を区別し たり，重要な状態変数値の組合せをエキスパートの知識から 予め与えておくことが 容易など 多くの利点を有する．このように，高次元空間において状態評価値や状態行動評価値の汎化については 多くの手法が提案されているが，高次元の行動空間における行動選択方法および 学習方法については，あまり注目されてこなかった．連続な行動空間を扱うための最も単純な接近法としては，行動空間を全てメッシュに区切り，状態入力に応じて各行動メッシュに対して  値に応じ た確率を割当てることが考えられるが，行動空間の次元が高くなると「 次元の呪い」によってたちまち空間爆発を起こし ，記憶容量的にも計算量的にも実行不能

     になってし まう．また，せっかく膨大な空間を「汎化」によって少ないパラメータで扱おうとしているのに，細かい離散化によってパラメータ数を爆発させては意味がない．
しかし ながら離散化を粗くし すぎ てもきめ細かな行動選
択ができないため制御の質が落ちるジレンマがあった．
本論文では，まずランダムタイリングを用いて状態行
動空間を汎化し ， 値や行動選択確率分布を表現する方法を提案する．次に，多次元で連続な行動空間を細かく離散化するが，  サンプリングによって空間爆発を回避しつつ行動選択を行う方法を提案する．  や#$#$ など ，これまで代表的強化学習手法だったにもかかわらず，行動選択の困難さから膨大な行動空間を持つ
強化学習問題への実装が困難だったが，本手法により容易に実装できることを示す．

 問題の定式化
状態空間を ，行動空間を ，上下界を持つ実数の集合を  と表す．各時刻 でエージェントは状態観測  に基づいて行動    を実行し ，状態遷移に伴う報酬
   を得る．本論文が環境のモデルとして仮定するマ
ルコフ決定過程 %()*& では，一般に次の状態や報酬は確率的で，その分布は  と  にのみ依存する．()* では
次の状態   は遷移確率  %    & に従って決まり，
報酬  も期待値 %  & によって与えられる．エージェン
トは予め  %    & や %  & についての知識を持っていない．強化学習の目的はエージェントのパフォーマ
ンスを最適化する政策を得ることである．無限期間のタ
スクにおける自然な評価規範とし て，以下のような割引報酬の合計がある．

½

 +




   %,&

割引率 -    , は未来に得るであろう報酬の現時点での重要度を表し， は時刻 の評価値 %& を表す．()*では評価関数は以下に定義される．




%& +

 ½ 

 







+ 



%.&

a2

が望ましい．そこで . 個の要素を持つ状態特徴量ベクト
ル  %& + %%&  %&     & および . 個の要素を持つ行動特徴量ベクトル %& + % %& %&     &を用いる．このとき，特徴量ベクトルの前半の要素はタ
イルのベクトルそのままで 、後半の要素は , から 各タイ
ルの値を引いた値とする。

T9
T5

T8

T7
T6
T3

 %& +T2
 %& +

T1
T4

a1

/  ,0 ２次元行動空間での 1 個のタイルによるランダ

ムタイリングの例．タイル 2 は部分空間 , の矢印で示される区間で定義されるタイルのため，それ以外の空間
. では全領域をカバーするタイルになる．タイル 3 も同様．
ただし  は期待値を表す．()* における学習の目的
は，各状態  において式 %.& で定義される評価値を最大化するような最適政策を見つけることである．本論文で扱う環境では，状態空間 および行動空間  は多次元空間で表されるものとする．

 ランダムタイリングによる高次元状
態行動空間の汎化方法の提案
高次元空間において関数を汎化する方法は多種多様であるが，本論文では多数のランダムタイルを用いる方法を提案する．これは状態空間における汎化のためのタイルコー
デ ィングの一種であるハッシュに基づいたアイデアだが，行動空間については計算手順が状態空間とはだいぶ異なる．ある , つのランダムタイル % & は，入力空間 を構成する次元のうち，任意の１次元以上の複数次元で定義される部分空間中のある矩形領域を表し，入力された座標 がその矩形領域である場合 % & + , を出力し ，それ以外の場合 % & + - である．矩形領域を構成する次元や矩形の範囲・大きさなど は，タイル毎にランダムに与える．このように，ある１つのタイルは空間を構成する次元の一部分で構成される空間の，とある領域として処理するが，このタイルを空間全体からみると，定義される部分空間中では範囲の限定された矩形だが，それ以外の空間では全領域をカバーするタイルと同義である．このようなランダムタイ
ルを多数用いて重み付け線形和することにより，空間全体に対して関数近似（汎化）を行う．本論文では，状態空間に対するランダムタイル  %&（ただし  , .      ）および 行動空間に 対するランダ ムタイル  %&（ ただし  , .      ）の２種類のタイル集合を用いて特徴量ベクトルを生成する．特徴量ベクトルを用いて関数近似を行う場合，絶対和ノルムが一定値（理想的には , ）であること




 %&

,

     %&    

 %&

  ,      %&

%4&

%2&

状態 ，行動  に対する状態行動評価値（  値）は，特徴量ベクトル  %& %& の各要素と . . コの重み
変数 （ただし + ,     .   + ,     . ）を用いて以下のように計算する：
% & +,  
 %&  %& %3&   

式 %3& の   は，  %&  %& の組合せで表される特徴量ベクトルのノルムを , にするための正規化定数である．
この  値を温度パラメータ  で除したボルツマン分布に従い，行動を確率的に選択する．各重み変数の値を調節することにより， 値および 行動選択確率分布が変化す
る．本手法には以下の特徴がある：
ランダムタイルが定義される行動空間の部分空間に
よって行動変数間の依存関係が表現できる．
定義されている行動部分空間が互いに干渉し ていな
いランダムタイルが存在することにより，互いの空間において独立に行動を出力することが必要なタスクを学習できる．例えば，ある行動変数の集合は固定された特定の値だけ，別の行動変数の集合では -〜, の値を一様に出力することが求められるような場合にも対処できる．
このように興味深い特徴が期待されるが，高次元の行動
空間全体に対して定義された重み関数のボルツマン分布に従う行動選択は，そのまま実行し ようとすると組合せ爆発を起こしてし まうため工夫が必要である．

 高次元空間での複雑な確率分布によるサンプリングと学習 従来手法：フラット な行動選択
ランダ ムタイリングによって高次元空間において複雑な状態行動評価関数（  関数）や行動選択確率分布関数が表現できるが，この分布に従って行動を選択するための最も原理的に単純な方法は，フラットな行動選択法である．
これは，行動空間を全て細かい格子状に離散化し，各超矩形領域に対して確率を割当て、ルーレット選択によっていずれかの超矩形領域に相当する行動を選択するものである．本論文では ，連続な行動空間を各次元毎に等し く P(a)selecta2

a1/  .0 ２次元行動空間を格子状に分割し ，各メッシュの持つ確率に応じてフラットに行動選択する様子．, .
は行動空間を表し ，たて軸は確率を表す．

分割して格子状に離散化する．よって行動空間を  次元と仮定すると  コの行動  % + ,      & へ離散化される．行動は，各行動  毎に定義された確率  %&に従って，どれか１つが選ばれる．/ . は . 次元の行動空間におけるフラット な行動選択の様子を示す．この例
では . 次元空間 , . で離散化された全ての格子について確率を計算し ，その比率に基づいて格子を一つ選択して行動出力とし ている．
本論文では，行動の確率  %& は，一般に状態  において行動  に割り当てられた  値 %  & に応じ た以
下のボルツマン分布とする：
 % & +

5 %%  & & 

5 %%  & &%6&

ただし  は正の値をとる温度パラメータであり，値が大
きいと全行動の確率が均一に近づき，ゼロに近づくと大きな  値を持つ行動の確率が大きくなる．このとき，各行動の % & はランダムタイルの値と重み変数の線形和から計算される．
このフラットな行動選択方法は，式 %6& の示すとおり
全行動空間の  値を調べる必要があるため，行動次元数が .〜4 次元程度ならばある程度実用になるが，次元数が高くなると離散化した行動空間が指数的に増大するため，
記憶容量的にも速度的にも実行不能になる．

  サンプリングによる行動選択
著者は高次元空間における確率分布に従って効率良くサンプリングするための方法の１つである   サンプリ
ングを用いる行動選択法と適正度の計算法を提案した  ．
 サンプリングとは，高次元の確率変数において，注目している次元以外の次元の変数の値を固定し，そのときの条件付確率分布を用いて , 次元ずつサンプルを行っていく処理を全ての次元に対し て十分な回数繰返し ，最終的に得た値をサンプルとする ("   ( '
法（ ('(' 法）の一種である  ．/ 4 は . 次元の行動空間における   サンプリングの様子を示す．. 次元
空間 , . で離散化された全ての格子における確率は/ . のフラット 選択の場合と同じだが，, 次元ずつサンプルを行っていくので，/ . のような全行動空間における確率を全て計算するような処理が不要であることが分
かる．/ 4 の右上 %,& は . を固定した条件付確率により , をサンプルし ，左下 %.& では %,& で選んだ , を固定した条件付確率により . をサンプルしている．これで反復 , 回分であり，さらに右下 %4& では %.& で選んだ . を固定した条件付確率により再び , を選んでいる．このような反復を十分な回数繰返し た結果得られた , . を最
終的な行動出力とする．  サンプリングでは，反復回数についての理論的な下限については明らかにはされておらず，実験的に決められているのが実情である．
/ 4 で示した例題のように . 次元程度の空間を 6 × 6に粗く分割した程度では ，フラットな行動選択との計算量的な差はあまりないが，行動次元数や分割数が増加す
ると，その差は顕著に現れる．例えば 行動空間が 7 次元
で各次元を ,- 分割する場合，フラットな行動選択においては各メッシュにおける重みの計算を ,- +, 千万回行わなければならないが，  サンプリングでは ,- 7
（ 反復回数）程度であり，反復回数を数十回程度に抑えればフラット な行動選択法に比べて１万分の１程度の計算量で済むことになる．
 サンプリングでは行動選択確率分布自体は式 6 と同じだが，各行動座標軸毎に処理を行うため，記法を以下のように対応させる．フラットな行動選択の場合同様，行動の次元数  で，行動空間は各次元毎に  分割により離散化されているものとする．ある多次元行動  について，各行動次元毎に分解して次のように表す： + %       & た
だし各次元の要素  %ただし   , .     & は   
ただし   , .     である．ある状態  行動  に対する  値は，% & + %      & と表す．この 値は，フラット選択における値と同一である．  サン
プ リングの 回目の反復においてサンプルされた行動要素を % & % &     % & と記する．このとき， 8 , 回目の反復における行動要素は以下の確率分布に従ってサンプルされる： % 8 ,& %

 % 8 ,&

 %






 % &  % &    

% &&



 % &  % &    

% &&






% 8 ,& %

 % &  % &    

ここで，条件付き確率  %      
ルツマン分布で与えられる： %        +

 % &&& は，以下のボ& 
5 %%            & &  5 %%            & &%9&

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



強化学習アルゴリズム

ランダムタイルによる空間汎化と   サンプリングによる行動選択を代表的な強化学習アルゴ リズムである   法と組み合わせる．第 4 章で説明したように，状態空間のランダムタイル  %&（ただし  , .      ）および 行動空間のランダ ムタイル  %&（ ただし  P(a)select

P(a)

a2
a2
a1
a1
(1)
selectselect

P(a)

P(a)

a2

a2

a1

a1

(2)

(3)

/  40 格子状に分割された２次元行動空間を  サンプリングする様子．左上の図は行動選択確率分布，右上 %,&は . を固定したときの条件付確率により , を選ぶ様子，左下 %.& は %,& で選んだ , を固定した条件付確率により . を選ぶ様子，右下 %4& は %.& で選んだ . を固定した条件付確率により再び , を選ぶ様子．, . は行動空間を表し，たて軸は確率を表す．

¼

, .      ）の２種類のタイル群を用いて，. 個の要素を持つ状態特徴量ベクトル  %& + % %&     &ここで 5 %  & を探す必要があるが，これはボルツ
マン分布の温度パラメータ  をゼロに近づけて   サンプリングによって得た行動の  値で代用したり，あるいは   サンプリングを行う過程で見つかった最大の 値を用いるなど ，大規模問題では近似的に与えざ るを得ないという問題点はあるが，真に最大の  値でなくても，選んだ行動の  値を充てれば #$#$ アルゴ リズムになるので，   学習をすることは保障される．

および . 個の要素を持つ行動特徴量ベクトル %& +    & を式 %4& %2& より生成する．状態 ，行動  に対する状態行動評価値（  値）は，特徴量ベクト
ル  %& %& の各要素と . . コの重み変数 （ただし + ,    .   + ,    . ）を用いて以下のように計算する：% %&

% & + 

, 

 %&  %& 

%7&

 実験

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

5 %%  & &%1&

  5 %%  & &ただし 行動は式 %9& の   サンプリングにより選択するため，全行動について  値を計算する必要は無い．行
動選択後，報酬  と遷移先の状態  を観測する．遷移先での状態  における  値を使い，もとの状態  で実行した行動  の  値を更新する：¼¼

%  &

¼
 %  & 8   8  5
%  &%  &%,-&ただし  は割引率， は学習率（ -    , ）である．ここで  値は式 %7& で表されているので，式 %,-& で示される  値の更新は，重みパラメータ  を以下のように更新することで実現する：
 %&  % & 8 

 





¼

 8  5 %  &%  &%,,&/ 2 に示す   ! 問題  に修正を加えた問題
へ本手法を適用する．状態空間  + %   & は 4 次元で，%  & は棒の下端の円の中心座標を表し ，- , -    , の矩形範囲になければ なら ない．  は 棒である．行と水平面のなす角度を表し ，-   
動  + %     & も 4 次元で，目標とする位置座標を表す．行動により目標座標が与えられると，その方向へ + %   & 空間中を直線的に移動し ，途中で障害物あるいはゴ ール領域に触れるか ，目標座標に 到達すると，イベントが発生し て次の意思決定を行う．ゴ ール領域は-7 
 -1 -6    -9 で，棒の長さは -2 である．障害物の座標は，障害物 ,0 %,- -,& %-3 -2&%,- -2& 障害物 .0 %-2 --& %-3 -.3& %-7 --& 障害
物 40 %-- -3& %-.3 -43& %-.3 -4& %-- -,& 障害物
20 %-- ,-& %-4 -7& %-43 -33& %-- -1& の領域で定義される．棒がゴ ール領域に到達すると ,-- の報酬が与えられて初期状態へ戻り，それ以外では報酬 - である．

強化学習エージェントは，4 次元の状態入力の各次元の変数を ,-- 分割して離散化する．4 次元の行動 %     &についても同様に各次元を ,-- 分割して離散化する．よっ

35

GOAL

Averaged Reward (1000 steps)

30

25

20

Randomtile-coding

15

10

5
Grid coding (5x5x5)x(5x5x5)
Grid coding (6x6x6)x(6x6x6)
0
0

20000

40000
60000
Learning Steps

80000

100000/  30   ! 問題（ 状態 4 次元，行動 4 次元）における学習の ,- 試行の平均と標準偏差を示す．横軸は学習ステップ，縦軸は ,--- ステップ期間の平均報酬．
/  20   ! 問題．学習主体は棒下部の円が黒く表示された時点毎に意思決定を行う．
GOALて離散空間の強化学習問題とし ては 状態数 ,-- + ,-，
行動数 ,-- + ,- ，状態行動空間は ,- という膨大な空間になる．この状態空間に対し，ランダムタイルを .-個生成して状態特徴ベクトル  %& とする．このタイル群
は，各状態次元についてタイル矩形領域の部分空間を構成する要素として選択する確率を -6 としてランダムに作成する．ただし 各次元の要素を１つも選択しなかったタ
イルは 除外し 再生成する．ランダムタイルの矩形領域については，離散化された空間の境界に合わせて一様な乱数で生成する．行動のランダムタイル  %& も同様に .-個生成する．  アルゴ リズムにおける 5  を探す部分は，  サンプ リングの過程で記録された最大の  値で代用した．  サンプリングの反復回数は,3 回，割引率  + -1，ボルツマン分布の温度パラメー
タ  + -2 で一定，学習率  + -3 に設定する．比較対象とし て，状態と行動空間を 3 3 3 + ,.3 個のタイル
へ均一にグ リッド 分割した場合と，6 6 6 + .,6 個のタイルに均一に分割した場合について調べる．
/ 3 に学習結果（ ,- 試行平均）を示す．この問題はスタートから 4 ステップでゴ ールする解が最良解だが，試行によっては提案手法は 2〜3 ステップを要する解しか見つからない場合がある．これは試行毎にランダ ムにタイ
ルを生成しているため，タイルの配置によっては 4 ステッ
プでゴ ールする解が見つからないためではないかと考えられる．これに対して，空間を均一にグリッド 分割した
場合，高々6 + .,6 個程度のタイルに分割した程度では全く解を見つけられないことが分かる．

さらに / 6 に示す冗長アームのリーチングタスク に修正を加えた問題へも適用した．アームは 7 本のリンクが関節を介して直列に接続されており，. 次元平面上を動く．状態空間  + %       & は 7 次元で， は根元のリンクが水平面となす角度で，  , のとき  は関節 と  , との間の角度である．アームを構成するリンクは，
全て -   , -    , の矩形範囲になければならな
い．行動  + %        & も 7 次元で，目標とする関/  60 7 関節冗長アームのリーチングタスク．学習主体は関節が黒丸で示された時点毎に意思決定を行う．

節角度を表す．行動により目標角度が与えられると，その方向へ  + %      & 空間中を直線的に移動し ，途中で障害物あるいはゴ ール領域に触れるか，目標座標に到達すると，イベントが発生して次の意思決定を行う．アームの台座の位置は %-93 -3&，アーム全長 -6，ゴ ール領域
-4
-3 -7-1，スタート状態 ,7- 8 23 度，
障害物 ,0 %-7 --& %-7 -.& %,- -4& %,- --&，障害物 .0 %-- -23& %-33 -23& %-33 -33& %-- -33& である．強化学習エージェントは，7 次元の状態入力の各次元を ,- 分割して離散化する．7 次元の行動 %      & についても同様に各次元を ,- 分割して離散化する．よって離散空間の強化学習問題としては状態数 ,- ，行動数 ,- ，状態行動空間は ,- という膨大な空間になる．この空間に対し ，ランダ ムタイルを .-- 個生成して特徴ベクトル  %&  %& とする．ランダムタイルは，各次元についてタイル矩形領域の部分空間を構成する要素とし て選択する確率を -4 とし てランダムに作成する．  サン

35

30

Averaged Reward (1000 steps)

Random tile-coding
25

20と思われる領域へ適応的に小さめのタイルを追加し てい
くことにより，関数近似の精度を上げていくことも考えられる．また，タイルを自由に追加できる点は，エキスパートが動作を教える場合において特定の領域に新し く
タイルを追加してより細やかな動作をさせることが 容易であるという利点がある．

15

 おわりに

10

Grid coding(2x2x2x2x2x2x2x2)x(2x2x2x2x2x2x2x2)

5

0
0

20000

40000
60000
Learning Steps

80000

100000/  90 7 関節冗長アームのリーチングタスク（ 状態 7

次元，行動 7 次元 ）での学習の様子．横軸は学習ステッ
プ，縦軸は ,--- ステップ期間の平均報酬を表す．
プリングの反復回数は 2- 回で，他の設定は   !問題と同じである．比較対象とし て，状態と行動空間を. + .36 個のタイルへ均一にグリッド 分割した場合について調べる．
/ 9 に学習の様子（ ,- 試行平均）を示す．この問題はスタートから 4 ステップでゴ ールする解が最良解であるが，提案手法では試行毎にランダムにタイルを生成しているにもかかわらず，全ての試行で最良解が見つかっている．しかし ，均一なグ リッド 分割では タイル数が多いにもかかわらず全く学習できなかった．

本論文では，高次元の状態行動空間における汎化および行動選択方法としてランダムタイリングと   サンプ
リングによる行動選択法を提案した．本手法を  
アルゴ リズムと組合せ，  ! 問題および冗長アー
ムのリーチング問題へ適用し ，高次元の状態行動空間において実時間で学習することを示し ，ランダ ムタイルが非常に有効に働くことを示した．状況に応じ 適応的にタイルを追加・削除する方法の検討は今後の課題である．

 :,; 深尾 隆則，稲山 典克，足立 紀彦：正則化理論を用いた連続的状態と行動を扱う強化学習，システム制御情報学会論文誌，<,, =,, 314>311 %,117&:.; 堀内 匡，藤野 昭典，片井 修，椹木 哲夫：連続値入出力を扱うファジィ内挿型   の提案，計測自動制御学会論文集 <43 =. .9,>.91 %,111&:4; ? ( 考察

0 @    ( (  * %,111&:2; 木村 元，宮崎 和光，小林 重信：強化学習システムの設計指針，計測と制御 <47 =,-
実験ではいくつかの種類のランダムタイリングを用いたが，ランダムタイルの生成パターンによって，学習性能が大きく変わることがあった．特に   ! 問題でその傾向が顕著に見られた．また，タスクの学習に必要なタイル数については ，高い次元の問題ほど 多くのタイ
ルを必要とするとは限らないことが 冗長アームの実験結果から考察される．冗長アームの問題では，アームの移動コストを考えず，意思決定ステップ 数だけで評価し ているため，最適なパスが無数に存在するために，.-- 個という比較的少ないタイルでも最適解を容易に発見できたと考えられる．しかし ，同じような分割数でも均一にグ
リッド 分割し た場合には，ど ちらの問題においても学習できない．ランダムタイリングによって生じ る細かい分
割と粗い分割や，全ての次元の変数を考慮するのではな
く一部の次元の変数に注目した汎化が重要と考えられる．
実験において，状態空間に対するランダムタイルの中には，全く使用されていないものが .〜4 割存在した．これは，定義された状態領域の中には 到達不可能な領域があるなど の事情による．本論文では 固定されたランダム
タイリングを用いているため上記のような問題が生じているが，新しい未知の状態入力があるたびに，それに対応して適応的に新しいランダ ムタイルを生成するなど の工夫が考えられる．また，学習初期は大きな領域を持つ
ランダ ムタイルによって学習し ，学習進行に応じて重要

6,7>6.4%,111&
:3; 木村 元：強化学習における高次元数の行動空間の扱いについて−ハッシュと  #   を用いた行動選択方法の提案 計測自動制御学会 第 4. 回知能シ
ステムシンポジウム 411>2-2 %.--3&:6; ( $  $ " '0 * 

$   <       

@   (    #     

,11>.44 %,113&

:9; #   ? ' #  # A  $0 B5        @   *   '  #    $   
:7; #



 #  

,64>.,7 %,117& #0  !      

0 #

 5      

         ! ! ,-47>,-22 %,116&:1; # # A C  $0   $  
%,117& 0

   "   (  *