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

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

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

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

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

Actor-Critic

Q-learning

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

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

連続空間の関数近似

ボルツマン
行動選択

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

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

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

連続空間の関数近似

ボルツマン
行動選択

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

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

対象とする学習問題１：ほふくロボット問題
２本足：
状態６次元
行動４次元

関節を動かして、這って進む動作を獲得する
２本足と３本足の問題
状態： 各関節角度とセンサ
行動： 動作関節角度

３本足：
状態９次元
行動６次元

足が目標角度へ到達するか、途中で足先タッチセンサの値が変化すると意思決定のイベント発生
毎ステップ前進した距離に比例して報酬

足先にタッチセンサ

対象とする学習問題２：Rod in Maze (Moore 1995)
2次元平面中でスタート状態
からゴール領域まで棒を移動
ゴール
領域領域中に固定障害物
棒の傾き ０～180度のみ

障害物

状態： X, Y座標と角度θ
行動： 動作目標X,Y,θ座標
棒が目標座標へ到達するか、途中で障害物へぶつかると意思決定のイベント発生
障害物

障害物

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

スタート状態

（１）

（３）

（２）

（４）

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

意思決定４

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

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

対象とする学習問題３：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 の関数になっているとき，アルゴリズムで得るＱ値は確率１で最適政策の評価値に概収束する。
ただし環境はエルゴート性を有するＭＤＰQ-learning

V (S )

連続空間の関数近似

ボルツマン
行動選択

真の価値関数１次元の連続な状態空間ＳS

このような離散ではない状態空間のvalueを学習するには？

離散状態表現による近似
粗い近似

V (S )Vˆ ( S1 )Vˆ ( S 2 )Vˆ ( S3 )１次元の連続な状態空間Ｓ

S

細かい近似

V (S )
ˆVˆ ( S1 ) V ( S 2 )Vˆ ( S3 )Vˆ ( S 4 ) Vˆ ( S5 )Vˆ ( S 6 ) ˆV (S7 )S

離散状態表現による近似の問題点
粗い近似： z価値関数の学習は早い
z非マルコフ性が生じる → 最適政策が得られない
細かい近似 z価値関数の学習は指数関数的に遅くなる
z特に高次元環境において膨大なメモリーが必要
学習途中において、未訪問の状態の評価値は初期値のまま

V (S )
ˆVˆ ( S1 ) V ( S 2 )Vˆ ( S3 )Vˆ ( S 4 ) Vˆ ( S5 )Vˆ ( S 6 ) ˆV (S7 )S線形アーキテクチャによる汎化と関数近似

x1 ( S )基底関数

x2 ( S )基底関数

未訪問の状態の評価値は周囲の値より適当に補間x3 ( S )基底関数

Sx1 x2 x3
特徴ベクトルV (S )

w1 w2 w3Vˆ ( S ) = x1w1 + x2 w2 + x3 w3

重みベクトルS

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

状態入力（センサ入力）

線形アーキテクチャ

高次元の特徴量ベクトル固定変換( f1 , f 2 ,L f n )Q( s, a ) = ∑i =1 f i win

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

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

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

状態入力（センサ入力）

線形アーキテクチャ

高次元の特徴量ベクトル固定変換( f1 , f 2 ,L f n )Q( s, a ) = ∑i =1 f i wi

多様な非線形変換を用いて膨大な特徴量ベクトルを生成すると良い例） サポートベクターマシンnそれぞれが基底関数の値に対応

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

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

a2

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

T9T5
T8T7

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

T6
T3
T2

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

T1
T4

a1

実験では、各軸あたり0.3～0.6の確率で区域を設定

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

該当するタイルの特徴量のみ１ある状態 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
fng2
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-learning

連続空間の関数近似

ボルツマン
行動選択

T9

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

a2

T5
T8
T7

特長

T6
T3

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

T2

T1
T4

a1

連続空間の関数近似

Q-learning

ボルツマン
行動選択

a2
T9

ランダム矩形タイルの改善

T5
T8
T7T6T3
T2

・エピソードデータにおいて一度も反応しないタイルを新しく作り直す（スコアゼロ）
・エピソードデータに対してスコアの低いタイルを新しく作り直す

T1
T4

a1

Q-learning

連続空間の関数近似

ボルツマン
行動選択

矩形タイルのスコア

1
H ( f i ) = − p ( f i , D) log p ( f i , D)
矩形f iの体積エピソードデータに対する矩形タイル反応の情報量（エントロピー）
データに対し、５０％の確率で反応すると最大値体積の小さいタイルほど高く評価Q-learning

連続空間の関数近似

ボルツマン
行動選択

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

行動選択確率：⎛ Q( s, ai ) ⎞exp⎜⎟T ⎠⎝P(ai ) =⎛ Q ( s, a j ) ⎞A
∑ j =1 exp⎜⎜ T ⎟⎟⎝⎠しかし！
全行動空間の exp(Ｑ) の合計が必要！

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）

行動空間の各次元を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サンプリング

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サンプリングによる行動選択処理

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

連続空間の関数近似

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

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

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

シミュレーション１： ほふくロボット
特徴ベクトルの設定
ランダムタイリング
6次元空間10x10x10x10x2x2 の格子状
タイルの境界をこの格子に合わせたランダムな大きさのタイルを200個生成
各次元要素をタイルに選択する確率=0.6

２本足： 状態６次元・行動４次元
３本足： 状態９次元・行動６次元

9次元空間10x10x10x10x10x10x2x2x2
タイルの境界をこの格子に合わせたランダムな大きさのタイルを200個生成
各次元要素をタイルに選択する確率=0.6

Q-learning の設定

Gibbs-Sampling の設定

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

反復回数：30回×4 or 6次元

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

ランダムタイルの生成

各次元要素をタイルに選択する確率=0.6

a2
選択された次元 a2
生成された
ランダムタイル

タイルの区間がランダムに設定

生成された
ランダムタイルa1
3次元空間を10x10x10 の格子状とし、タイルの境界をこの格子に合わせた
ランダムな大きさのタイルを生成

a1
選択されなかった次元：
タイルはその次元の全区間の大きさに設定

シミュレーション１： ２本足ロボットの結果
ランダムタイリング＋修正200タイル

ランダムタイリング
200タイルシミュレーション１： ３本足ロボットの結果
ランダムタイリング＋修正200タイル

ランダムタイリング
200タイルシミュレーション１： ３本足ロボットの結果
ランダムタイリング＋修正200タイル●ランダムタイルの修正と、オフライン学習が非常に効果的

ランダムタイリング
200タイルシミュレーション２： Rod in Maze

状態3次元
行動3次元

特徴ベクトルの設定
１）ランダムタイリング
3次元空間を10x10x10 の格子状とし、タイルの境界をこの格子に合わせた
ランダムな大きさのタイルを200個生成
各次元要素をタイルに選択する確率=0.6２）等間隔グリッドタイリング
３次元空間を 5x5x5 の等間隔グリッドで分割し、5x5x5=125個のタイル生成
３次元空間を 6x6x6 の等間隔グリッドで分割し、6x6x6=216個のタイル生成

Q-learning の設定

Gibbs-Sampling の設定

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

反復回数：15回×3次元

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

シミュレーション２結果： Rod in Maze
１０試行の平均
ランダムタイリングはそれぞれ異なる

状態3次元
行動3次元ランダムタイリング＋修正200タイル

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

ランダムタイリング
200タイル

等間隔グリッドタイリング
5x5x5=125タイル
6x6x6=216タイル

学習ステップシミュレーション２結果： Rod in Maze
１０試行の平均
ランダムタイリングはそれぞれ異なる

状態3次元
行動3次元ランダムタイリング＋修正200タイル

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

ランダムタイリング
200タイル

等間隔グリッドタイリング
5x5x5=125タイル
6x6x6=216タイル●ランダムタイルを修正しても、あまり効果が無い
学習ステップ学習で得られた動作の一例
ゴール：
スタート状態へ
意思決定３

意思決定４

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

シミュレーション３： 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タイル
１０試行の平均ランダムタイリングはそれぞれ異なる

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

ランダムタイリング＋修正200タイル

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

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

状態８次元
行動８次元

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

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

ランダムタイリング＋修正200タイル●ランダムタイルを修正すると、逆に性能悪化●ランダム動作時のエピソードでタイルを評価するとゴール付近のタイルが生成されない？

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

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

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

意思決定２

考察とまとめQ-learning

連続空間の関数近似

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

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

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

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

考察とまとめ
個別ランダムタイルの評価法と修正アルゴリズム評価に用いるエピソードにおいてランダムな試行を用いる場合、状態訪問頻度がスタート状態などに偏るときには性能悪化

ランダムタイル群を評価する方法の確立とタイル群修正アルゴリズムの構築「強化学習ロボット：スタディアス」
愛・地球博
ＮＥＤＯプロトタイプロボット展