情報処理学会創立50周年記念（第72回）全国大会

1E-3

ニュートン法による強化学習ステップサイズパラメータの調整法
野田 五十樹 †(独) 産業技術総合研究所 情報技術研究部門
この REMA を用いると、推定値 x̃t の α による偏微1

まえがき分について、以下の公式が成立する。
hki

強化学習による行動価値学習でよく用いられる以下∂ξt∂α∂ k x̃t∂αkの式において、ステップサイズパラメータ α は学習を通じて 0 に漸近させることが多い。[1]。

Qt+1 (st , at )=k hkihk+1i(ξ − ξt)
α t

=

hk+1i

= (−α)−k k!(ξt(3)hki− ξt )(4)(1 − α)Qt (st , at )+α(rt + γ max
Qt (st+1 , a0 )) (1)03a

平均 2 乗誤差の指数移動平均与えられた時系列 {xt } と、それの EMA の系列{x̃t } の誤差 εt = x̃t − xt と 2 乗誤差 Et = (1/2)ε2t を考える。この時、以下の定理が成り立つ。

しかし、実際の強化学習の適用場面では、期待報酬や状態遷移は時間を通じて変化することが多く、その場合、上記のステップサイズパラメータを単純に 0 に漸近させることはできなくなる。

定理 1

この問題に対し、筆者はこれまで再帰的ステップサイ2 乗誤差、Et の α による k 次偏微分は次のように求ズパラメータ適応法 (Recursive Adaptation of Stepsize

めることができる。

Parameters, RASP) を提案し、これにより予測誤差を∂ k Et
∂αk

漸近的に最小化する手法を構築してきた [2]。しかしこの方法ではステップサイズが大きく変動する際に収束に時間がかかるという問題があった。本稿ではこの=k−1∑(k − 1)! ∂ i εt ∂ k−i εt(k − 1 − i)!i! ∂αi ∂αk−ii=0(5)0

ただし、 ∂∂αε0t = εt とする。

問題を解決するために、Newton 法を用いて最適なス

次に、各時刻における 2 乗誤差 Et の指数的移動平テップサイズパラメータを求める方法を提案する。

均 Ẽt = (1 − β)Ẽt + βEt を考える。ただし、β は 2 乗2誤差のためのステップサイズパラメータである。この再帰的指数移動平均法

Ẽt は、[3] において提案されている期待報酬値の分散の予測値と同じである。

式 (1) にあげたような強化学習の更新式を一般化す

この Ẽt について、もとのステップサイズパラメーると、以下の指数移動平均 x̃t+1 = (1 − α)x̃t + αxt とタ α により微分を求めると、以下のようになる。

見做すことができる。ここで、xt および x̃t は経験に∂ Ẽt+1∂α∂ 2 Ẽt+1∂α2k∂ Ẽt+1∂αkよって実際に観測された値 (報酬 rt など) およびその推定値であり、時刻 t によって更新されていく。
これに対し、再帰的指数移動平均法では、以下のよhki

うな再帰的な指数移動平均 (REMA) ξth0iを導入する。

ξt= xtξt+1h1i= x̃t+1 = (1 − α)x̃t + αxt

hki= (1 − α)ξt

ξt+1hkihk−1i+ αξt

===

∂ Ẽt
∂Et+β∂α∂α∂ 2 Ẽt∂ 2 Et(1 − β) 2 + β∂α∂α2k∂ Ẽt∂ k Et
(1 − β) k + β∂α∂αk(1 − β)(6)(7)(8)これらの式から、次のことが分かる。
式 (6)∼ (8) より、2 乗誤差の EMA Ẽt の α による(2)

高次の偏微分は、2 乗誤差 Et の高次偏微分を用いてAdaptation of Stepsize Parameters in Reinforcement
Learning by Newton Method† Itsuki Noda, ITRI, AIST <i.noda@aist.go.jp>

EMA により逐次的に求めることができる。また、Ethkiの高次偏微分も定理 1 により REMA ξt

12-95から求める

情報処理学会創立50周年記念（第72回）全国大会

changes of alpha [gamma=3.333333, best alpha = 0.923280]

このような観測値 xt を用いて、RRASP-N 法およchanges of alpha [gamma=3.333333, best alpha = 0.923280]

0.60.6び GDASS 法により α を適応させた結果を図 1 に示

Alpha10.8Alpha10.80.4す。これらのグラフは各々、異なる σ² 毎に α の適応

0.40.20.2

alpha
best_alpha0

alpha
best_alphaの様子を示したものである。また各グラフのなかの水

0020040060080010000200400

Cycle

600

8001000

Cycle

changes of alpha [gamma=1.250000, best alpha = 0.692810]
1

changes of alpha [gamma=1.250000, best alpha = 0.692810]
1alphabest_alpha0.6

平線は、最適ステップパラメータの理論値である。この図から分かるように、RRASP-N 法により α は理Alpha0.80.6

Alpha0.8

alpha
best_alpha0.40.40.20.20002004006008001000

論的最適値に急速に適応していることが分かる。
0200400

Cycle

6008001000

Cycle

changes of alpha [gamma=0.333333, best alpha = 0.282376]
1changes of alpha [gamma=0.333333, best alpha = 0.282376]
1alphabest_alpha

0.6

0.4

おわりに

5

Alpha

0.8

0.6

Alpha

0.8

alpha
best_alpha0.40.2

本稿では、RASP の手法を拡張して、Newton 法

0.2000200400

600

8001000

0200400

Cycle

600

8001000を用いて 2 乗誤差の指数時間平均を最小化する手法、

Cycle

changes of alpha [gamma=0.050000, best alpha = 0.048766]1changes of alpha [gamma=0.050000, best alpha = 0.048766]1alphabest_alpha0.60.6alphabest_alphaRRASP-N を提案した。この手法の特徴は、RASP にAlpha

0.8

Alpha

0.8

0.4

0.4

0.20.20より求めることができる高次の偏微分の値を用いて、2乗誤差の指数時間平均のステップサイズパラメータに

00200

40060080010000200

Cycle

400600

800

1000

Cycle

(a) RRASP-N 法よる高次偏微分を逐次的に求め、それをもとに Newton(b)GDASS 法

法で最適なステップサイズの値を決めるというものである。

図 1: 実験 1b

実験による動作確認では、提案手法が従来手法のことができることがわかる。よって、Ẽt の高次偏微分

GDASS よりも迅速に最適なステップサイズに到達できると同時に、真の信号の周期性などの性質を安定しは REMA から逐次的に求めることができる。て抽出できる機能を持っていることが示された。

この高次偏微分を用いれば、2 次の Taylor 展開Ẽt (∆α) = Ẽt (0) +∂ Ẽt1 ∂ 2 Ẽt∆α +∆α2∂α2 ∂α2

謝辞である。

を用いて、以下の式のように、Ẽt を最小化する α を

Newton 法で推定することができるようになる。
() ()∂ Ẽt∂ 2 Ẽt∗∆α =/(9)∂α∂α2α∗= α − ∆α∗

参考文献[1] Even-dar, E. and Mansour, Y. Learning rates(10)

for Q-learning, Journal of Machine Learning Research, 5 (Dec. 2003), 2003.

この方法を Rapid Recursive Adaption of Stepsize Pa-[2] Noda, I. Recursive Adaptation of Stepsize Parameter for Non-stationary Environments, Prin-rameter by Newton’s method (RRASP-N) と呼ぶ。

4

本研究は科研費 21500153 の助成を受けたもの

ciples of Practice in Multi-Agent Systems (Proc.
of 12th International Conference, PRIMA 2009)(eds.Yang, J.-J., Yokoo, M., Takayuki Ito, Z. J.

実験
RRASP-N 法によりステップパラメータ α を効果

and Scerri, P.), Heidelberg (December 2009),
Springer.

的に修正できるかを確認するための実験を行った。この実験では、α が適切な値に修正されることを示すた
め、ランダムウォーク vt+1 = vt + ∆vt で変化する値[3] 佐藤誠, 木村元, 小林重信 報酬の分散を推定する
TD アルゴリズムと Mean Variance 強化学習法の提案, 人工知能学会論文誌, 16 巻, 3 号 F (2001),

vt に雑音 ²t が重畳した観測値 xt = vt + ²t を入力として学習・適応させた。ただし ²t および ∆vt は平均0、標準偏差 σ² 、σv の乱数とする。

353–362.
22-96