多次元状態-行動空間での強化学習
ランダム矩形タイルによる汎化方法とＧｉｂｂｓサンプリングによる行動選択方法の提案
木村 元
九州大学 大学院工学研究院海洋システム工学部門

http://sysplan.nams.kyushu-u.ac.jp/gen/index.html

ロボットの知能化→ 強化学習： 試行錯誤を通じて制御規則を獲得
学習アルゴリズムに対する要請：
１） とにかく単純な計算処理
zプログラムコードが短いこと
z自然言語で簡潔に表現できるのが望ましい

２） 安定した学習動作
z問題に依存せずに実装可能であること
zパラメータ設定にセンシティブではないこと

Actor-Critic

Q-learning

アルゴリズム中に「微分記号」など
論外！

ロボットの知能化→ 強化学習： 試行錯誤を通じて制御規則を獲得
学習アルゴリズムに対する要請：
１） とにかく単純な計算処理
zプログラムコードが短いこと
z自然言語で簡潔に表現できるのが望ましい

２） 安定した学習動作
z問題に依存せずに実装可能であること
zパラメータ設定にセンシティブではないこと

Actor-Critic

Q-learning

アルゴリズム中に「微分記号」など
論外！

本研究の目的
高次元連続状態-行動空間のロボット強化学習
Q-learning

連続空間の関数近似

ボルツマン
行動選択

・これら基礎的な技術と知見をそのまま継承した実装
・数万ステップで学習させる （Actor-Criticの数倍程度以内）

解決すべき課題：
１）状態-行動の評価値（Q値）の表現 ←膨大な空間の汎化
２）高次元連続行動空間における行動選択は？

The proposed Learning method is applied to 4-legged real robot
to learn walking behavior.

0.5 sec/step
Penalty
State is the current anglesof the Joints (8 dimensional).
Action is destination anglesof the joints (8 dimensional)
RewardPenalty

The agent found a policy:“stopping” to avoid penalties.

対象とする学習問題： Multi-Joint Arm(Moore 1995)2次元平面中でスタート状態からゴール領域までアームを移動
領域中に固定障害物
アームは冗長自由度（８関節）ゴール領域

状態： 関節角度θ（8次元）
行動： 目標角度θ（8次元）

障害物

アームが目標角度へ到達する
か、途中で障害物へぶつかると意思決定のイベント発生

スタート
状態

ゴールへ到達すると報酬／再び初期状態へもどる
障害物

（１）

（2）

（3）

動作例
意思決定３
ゴール：スタート状態へ

スタート状態：
意思決定１

８次元状態×８次元行動の強化学習問題

意思決定２

連続空間の関数近似

Q-learning[ボルツマン
行動選択

Qˆ ( st , at ) ← Qˆ ( st , at ) + α rt + γ max Qˆ ( st +1 , a ) − Qˆ ( st , at )a∈ A

状態Stで実行した行動のQ値を更新

γは割引率 （0≦γ≦1）αは学習率 （0＜α≦1）αの割合で近づけるよう
TD-errorに更新

α =1γ maxQˆ (st +1, a)Qˆ (st , at )st

遷移先の状態の行動中で最大のQ値を探す

報酬 rt

α =0

状態]

a∈A

状態遷移状態

maxQˆ (st +1, a)a∈A

st +1r

報酬 t
行動別の行動Q-learning

連続空間の関数近似

ボルツマン
行動選択

Q-learningの収束定理（Watkins92）
行動選択において全行動を十分な回数選択し，かつ学習率αが∞∞∑ α' (t ) → ∞
t =0

and

2α(t)<∞∑
t =0を満たす時間 t の関数になっているとき，アルゴリズムで得るＱ値は確率１で最適政策の評価値に概収束する。
ただし環境はエルゴート性を有するＭＤＰタイルコーディング（グリッド分割）による特徴ベクトル生成
状態空間の定義域

s2x1x2x3x4x5x6x7x8x9x10 x11 x12２次元状態空間 (s1,s2)の例
特徴ベクトル X=(x1,x2, … x16)状態が対応する要素xiのタイル内にあるとき xi = 1 , それ以外の要素は全て 0x13 x14 x15 x16s1
この特徴ベクトルを用いたvalue表現と学習における更新規則は離散テーブルを用いた場合と同一になる

線形アーキテクチャにおける更新処理（Q-learning）
強化学習アルゴリズムQ-learning: 以下の式で逐次更新[Qˆ ( st , at ) ← Qˆ ( st , at ) + α rt + γ max Qˆ ( st +1 , a ) − Qˆ ( st , at )状態Stで実行した行動のQ値を更新

a∈ A

TD-errorγは割引率 （0≦γ≦1）αは学習率 （0＜α≦1）

線形アーキテクチャでは特徴ベクトルxと重みwで表される

Qˆ ( S , a ) = x1w1 + x2 w2 + x3 w3以下の式で重みwを更新する：∂Qˆ ( S , a )wi ← wi + α TDerror
∂wi]

xi

線形アーキテクチャの更新法では真のvalueに対して二乗誤差最小の近似へ収束することが証明されている(Bertsekas & Tsitsiklis 96) ただしα→0線形アーキテクチャによる汎化と関数近似
望ましい特徴ベクトル x1 x2 x3 の性質：
絶対和ノルム＝１ （ただし収束の必要条件ではない）
異なる状態間では互いに線形独立
特徴ベクトルの個数を増やす→ 近似性能〈精度）向上
特徴量のカバーする領域を広げる→ 汎化（補間）性能向上
特徴ベクトルの生成方法には数多くのバリエーションがある
z離散状態表現（タイルコーディング）＝線形アーキテクチャの一種
zＣＭＡＣ（Sutton98）：タイルコーディングを複数組み合わせ
z高次元の空間：ＣＭＡＣ＋ハッシュ

なぜ強化学習では線形アーキテクチャなのか？
非線形の関数近似（ニューラルネット等）を用いると，収束は保証されず，学習が発散する例も示されている（Baird95）

Q-learning

状態入力（センサ入力）

連続空間の関数近似

ボルツマン
行動選択

固定変換

高次元の特徴量ベクトル( f1 , f 2 ,L f n )e.g., grid coding,tile coding CMAC, etc.

それぞれが基底関数の値に対応

線形アーキテクチャQ( s, a ) = ∑i =1 f i wi

Q-learning 更新規則

∂Qˆ ( S , a )wi ← wi + α TDerror∂wi

収束定理が存在 (Tsitsiklis and Van Roy, 1997)n等しい

各特徴量に対応する重み変数

Q-learning

状態入力（センサ入力）

連続空間の関数近似

ボルツマン
行動選択

固定変換

高次元の特徴量ベクトル( f1 , f 2 ,L f n )e.g., grid coding,tile coding CMAC, etc.

状態間で線形独立な特徴ベクトルをどのように生成するか？

線形アーキテクチャ

それぞれが基底関数の値に対応

Q( s, a ) = ∑i =1 f i win

各特徴量に対応する重み変数

Q-learning

状態入力（センサ入力）

連続空間の関数近似

ボルツマン
行動選択

固定変換

高次元の特徴量ベクトル( f1 , f 2 ,L f n )e.g., grid coding,tile coding CMAC, etc.

それぞれが基底関数の値に対応

線形アーキテクチャQ( s, a ) = ∑i =1 f i wi

多様な非線形変換を用いて膨大な特徴量ベクトルを生成すると良い例） サポートベクターマシンn各特徴量に対応する重み変数
ランダムな特徴は効果的!

高次元状態・行動空間の汎化：
ランダムタイリングによるＱ関数表現
基底関数

a2

様々な大きさ・次元の超矩形タイルをランダムに配置して特徴量ベクトルを生成

T9T5
T8
T7

各タイルが特徴量ベクトルの各要素に対応

T6T3
T2

( f1 , f 2 , f 3 , f 4 , f 5 , f 6 , f 7 , f8 , f 9 )

T1
T4a1

実験では、一様分布入力に対してヒットする確率が0.16になるよう領域を設定

高次元状態・行動空間の汎化：
ランダムタイリングによるＱ関数表現
基底関数

a2

様々な大きさ・次元の超矩形タイルをランダムに配置して特徴量ベクトルを生成

T9T5T8T7ある値が入力されたとき
T6T3T2( f1 , f 2 , f 3 , f 4 , f 5 , f 6 , f 7 , f8 , f 9 )

T1
T4a1

高次元状態・行動空間の汎化：
ランダムタイリングによるＱ関数表現
基底関数

a2

様々な大きさ・次元の超矩形タイルをランダムに配置して特徴量ベクトルを生成

T9T5T8T7ある値が入力されたとき
T6T3T2( 0, 0, 1, 0, 0, 1, 0, 0, 0)

T1
T4a1

該当するタイルの特徴量のみ１

高次元空間における汎化:
Random-rectangular Coarse Coding
入力ベクトルランダムに生成された超矩形(x1 , x2 , x3 , x4 , x5 , x6 , x7 , x8 )様々なサイズと次元で定義

各超矩形においては、矩形を定義するベクトル要素の位置と数はランダムに決められる.

x5
超矩形 Tj.
においては無視される要素

x2

A basis
Function

Tjx6

この例では入力ベクトルは８次元、しかし特徴量を表す基底となる
超矩形は x2 , x5 , x6 のみで定義され、他の要素は無視される

ある状態 s, 行動 aにおけるＱ値の求め方

f1
状態
タイル
Ts コ

状態
特徴量

Fii = 1,2,L 2Ts

fi = 1 − fi

反転状態
タイル
Ts コ

12Ta
2Ts
Q ( s, a ) =F G j Wij∑j =1 ∑i =1 i
Ts Ta
重み変数 Wij

g1

f2

g2

M
fTs

M
gTa

f1

g1

f2
M
fn

g2
M
gTa

行動
タイル
Ta コ

行動
特徴量Gj

反転行動
タイル
Ta コ

j = 1,2,L 2Ta

gi = 1 − gi

Q-learning

連続空間の関数近似

ボルツマン
行動選択

T9

ランダムタイリングによる高次元連続空間の汎化

a2

T5
T8
T7

特長

T6
T3

・実装が簡単・空間爆発を回避
・足りなければタイルを増やすだけ・実装が問題に依存しない

T2

T1
T4

a1

シミュレーションによる関数近似性能の定量的評価

Q-関数で２つの入力を区別可能

２～８次元
入力ベクトル=

２つの入力に対応する特徴量ベクトルが互いに線形独立

Random RectangularCoarse Coding

任意に２つランダムに発生１０００種類のランダムな入力ベクトルペアを生成し、提案手法にて特徴量ベクトルを生成させ、それらが線形独立になっているかどうかの割合を調べる

高次元

特徴量ベクトル( f1 , f 2 ,L f n )入力に対応する２つの特徴量ベクトルが互いに独立か？

Condition of input vector:x3
Two input vectors areindependently sampledfrom Uniform distribution.

x1x2
Input SpaceLinearly Independent Rate of Feature Vectors
between two Random Vectors in 2-dimensional Input Space
Regular grid

100 different patternsof random rectangularcoarse coding are tested.

Reverse point
7x7

Random Rectangles

100 features:
Random Rectangles 0.998
Regular grid
0.980

Almost all arbitrary two states
can be distinguished!
Number of Random Rectangular Features

Linearly Independent Rate of Feature Vectors
between two Random Vectors in 8-dimensional Input Space

Regular gridRandom Rectangles

100 different patternsof random rectangularcoarse coding are tested.

256 features:
Random Rectangles 0.992
Regular grid
0.996

Not so different
in 256 features.

Number of Random Rectangular Features

Another condition of input vector:x3

One input vector issampled fromUniform distribution.

1

The other is sampledfrom normal distribution
where the center is tothe former selected point.

x1x2

1

Deviation of the normaldistribution is 0.1,
And covariance is 0.

01

Input SpaceThis condition is quite often
encountered in RL in Robotics.

Linearly Independent Rate of Feature Vectors
between two Random Vectors in 2-dimensional Input Space
100 different patternsof random rectangularcoarse coding are tested.

Random Rectangles

Regular grid

Number of Random Rectangular Features

Linearly Independent Rate of Feature Vectors
between two Random Vectors in 8-dimensional Input Space
100 different patternsof random rectangularcoarse coding are tested.

Random Rectangles

256 features:
Random Rectangles 0.997
Regular grid
0.488

Regular grid
256 features

Random Rectangularcoding works excellently!
Number of Random Rectangular Features
256

Linearly Independent Rate of Feature Vectors
between two Random Vectors in 8-dimensional Input Space
100 different patternsof random rectangularcoarse coding are tested.

Random Rectangles

256 features:
Random Rectangles 0.997
grid
0.488
Random Rectangular CoarseRegularcodingseems ad hoc,
Regular gridbut it is quite suited for approximating
256 featureshigh-dimensional state-action valuesin Robotics.

Random Rectangularcoding works excellently!

Number of Random Rectangular Features256

Q-learning

連続空間の関数近似

ボルツマン
行動選択

T9

ランダムタイリングによる高次元連続空間の汎化

a2

T5
T8
T7

特長

T6
T3

・実装が簡単・空間爆発を回避
・足りなければタイルを増やすだけ・実装が問題に依存しない

T2

T1
T4

a1

Q-learning

連続空間の関数近似

ボルツマン
行動選択

ある状態ＳにおいてＱ値のボルツマン分布に従って確率的に行動aを選ぶ

行動選択確率：⎛ Q( s, ai ) ⎞exp⎜⎟T ⎠⎝P(ai ) =⎛ Q ( s, a j ) ⎞A
∑ j =1 exp⎜⎜ T ⎟⎟⎝⎠

しかし！
全行動空間の exp(Ｑ) の合計が必要！

高次元行動空間の扱いの難しさ：行動選択
関節１（a1）関節２（a2）

行動空間の各次元を10分割で離散化

a2

8関節 → 離散行動 1000万通り
a1

Q-learningにおける行動選択やＱ値の更新の際に最大のＱ値を探す計算に多大な計算コストを要する
従来の計算コストは「次元の呪い」に直面

高次元行動空間の扱いの難しさ：行動選択
関節１（a1）関節２（a2）a2

ランダムタイリングで行動空間の各次元を10分割で離散化空間を汎化しても意味がない!?

8関節 → 離散行動 1000万通り
a1

Q-learningにおける行動選択やＱ値の更新の際に最大のＱ値を探す計算に多大な計算コストを要する
従来の計算コストは「次元の呪い」に直面

Q-learning

連続空間の関数近似

ボルツマン
行動選択

⎛ Q( s, ai ) ⎞exp⎜⎟T ⎠⎝P(ai ) =⎛ Q ( s, a j ) ⎞A
∑ j =1 exp⎜⎜ T ⎟⎟⎝⎠

Q-learning

連続空間の関数近似

全行動空間の exp(Ｑ)の合計が必要！

ボルツマン
行動選択

⎛ Q( s, ai ) ⎞exp⎜⎟T ⎠⎝P(ai ) =⎛ Q ( s, a j ) ⎞A
∑ j =1 exp⎜⎜ T ⎟⎟⎝⎠Q-learning

連続空間の関数近似

全行動空間の exp(Ｑ)の合計が必要！

ボルツマン
行動選択

⎛ Q( s, ai ) ⎞exp⎜⎟T ⎠⎝P(ai ) =⎛ Q ( s, a j ) ⎞A
∑ j =1 exp⎜⎜ T ⎟⎟⎝⎠Q-learning

連続空間の関数近似

ボルツマン
行動選択

高次元空間における確率分布に従ったサンプルを効率よく得るには？ → 統計学的な一般問題
Markov chain Monte-Carlo （MCMC）法の一種

Gibbsサンプリング

計算が簡単な１次元の条件付確率分布

a1 (t + 1) ≈ P(a1 | a 2 (t ), a 3 (t ),L a N (t ))a 2 (t + 1) ≈ P(a 2 | a1 (t ), a 3 (t ),L a N (t ))Ma N (t + 1) ≈ P(a N | a1 (t ), a 2 (t ),L a N −1 (t ))このような反復 t を十分な回数繰返し、最終的に得たa(t)をサンプルとする

Q-learning

連続空間の関数近似

ボルツマン
行動選択

先ほどのボルツマン選択を Gibbsサンプリングしてみる

Q-learning

連続空間の関数近似

ボルツマン
行動選択

a2軸を固定し、a1軸についてのみボルツマン選択

Q-learning

連続空間の関数近似

ボルツマン
行動選択

a1軸を先に選択された値に固定し、今度はa２軸についてのみボルツマン選択

Q-learning

連続空間の関数近似

ボルツマン
行動選択

a2軸を先に選択された値に固定し、再びa1軸についてのみボルツマン選択 これを繰返すQ-learning連続空間の関数近似

ボルツマン
行動選択

⎛ Q( s, ai ) ⎞exp⎜⎟T ⎠⎝P(ai ) =Gibbsサンプリング：⎛ Q ( s, a j ) ⎞A
全行動空間の exp(Ｑ) の合計を⎟⎟exp⎜⎜∑
j =1
計算せずに右式に従うサンプルを得る！
⎝ T⎠

Q-learning

連続空間の関数近似

ボルツマン
行動選択

⎛ Q( s, ai ) ⎞exp⎜⎟T ⎠⎝P(ai ) =Gibbsサンプリング：⎛ Q ( s, a j ) ⎞A
全行動空間の exp(Ｑ) の合計を⎟⎟exp⎜⎜∑
j =1計算せずに右式に従うサンプルを得る！
⎝ T⎠

Q-learning

連続空間の関数近似

ただし、MaxQ を求める計算が「近似」にSARSAアルゴリズムなら問題ない

ボルツマン
行動選択
Gibbsサンプリングによる行動選択処理

特長・実装が簡単・空間爆発を回避
・足りなければ計算反復の回数を増やすだけ・分割を細かくしても、計算はあまり変わらないQ-learning

連続空間の関数近似

ただし、MaxQ を求める計算が「近似」にSARSAアルゴリズムなら問題ない

ランダム矩形タイリングによる関数近似法との計算処理の相性が良い

ボルツマン
行動選択
Gibbsサンプリングによる行動選択処理

特長
・実装が簡単・空間爆発を回避
・足りなければ計算反復の回数を増やすだけ・分割を細かくしても、計算はあまり変わらない

シミュレーション： Multi-Joint Arm

状態８次元
行動８次元

特徴ベクトルの設定
１）ランダムタイリング
８次元空間を10＾8 の格子状とし、タイルの境界をこの格子に合わせたランダムな大きさのタイルを200個生成
各次元要素をタイルに選択する確率=0.3２）等間隔グリッドタイリング
８次元空間を 2^8 の等間隔グリッドで分割し、2^8=256個のタイル生成

Q-learning の設定

Gibbs-Sampling の設定

割引率 γ=0.9
温 度 T=0.4
学習率 α=0.5反復回数：40回×8次元

タイル修正のためのデータエピソード：
学習初期 2000 step

状態８次元
行動８次元

シミュレーション結果： Multi-Joint Arm
ランダムタイリング
200タイル

１０試行の平均
ランダムタイリングはそれぞれ異なる

等間隔グリッドタイリング2^8=256タイル

割引率 γ=0.9
温 度 T=0.4
学習率 α=0.2

学習で得られた動作の一例

意思決定３
ゴール：
スタート状態へスタート状態：
意思決定１

意思決定２

まとめ
Q-learning「ランダム矩形タイルによる汎化方法とＧｉｂｂｓサンプリングによる行動選択方法」

連続空間の関数近似

ランダムタイリングによる高次元連続空間の汎化
MaxQ を求める
計算が近似に

ボルツマン
行動選択
Gibbsサンプリングによる行動選択処理

相性が良い

・実装が簡単・空間爆発を回避
・足りなければタイルを増やすだけ・実装が問題に依存しない・実装が簡単・空間爆発を回避
・足りなければ計算反復の回数を増やすだけ
・分割を細かくしても、計算はあまり変わらない

高次元連続状態-行動空間の強化学習問題へ実装