1
論
文
Technical Papers
Actor に適正度の履歴を用いた
Actor-Critic アルゴリズム:
不完全な
Value-Function
のもとでの強化学習
An Analysis of Actor-Critic Algorithms using Eligibility Traces:
Reinforcement Learning with Imperfect Value Functions
木村 元
Hajime Kimura
東京工業大学大学院総合理工学研究科
小林 重信
Shigenobu Kobayashi
東京工業大学大学院総合理工学研究科
Keywords:
Graduate School of Interdisciplinary Science and Engineering, Tokyo Institute of Technology
[email protected]
Graduate School of Interdisciplinary Science and Engineering, Tokyo Institute of Technology
kobayasi@.dis.titech.ac.jp
reinforcement learning, actor-critic, eligibility trace, value function approximation
Summary
We present an analysis of actor-critic algorithms, in which the actor updates its policy using eligibility
traces of the policy parameters. Most of the theoretical results for eligibility traces have been for only critic's
value iteration algorithms. This paper investigates what the actor's eligibility trace does. The results show
that the algorithm is an extension of Williams' REINFORCE algorithms for innite horizon reinforcement
tasks, and then the critic provides an appropriate reinforcement baseline for the actor. Thanks to the actor's
eligibility trace, the actor improves its policy by using a gradient of actual return, not by using a gradient
of the estimated return in the critic. It enables the agent to learn a fairly good policy under the condition
that the approximated value function in the critic is hopelessly inaccurate for conventional actor-critic algorithms. Also, if an accurate value function is estimated by the critic, the actor's learning is dramatically
accelerated in our test cases. The behavior of the algorithm is demonstrated through simulations of a linear
quadratic control problem and a pole balancing problem.
1.
は じ
め
に
Actor-critic 強化学習アルゴリズムは,政策反復法 (policy iteration) の一種であると言われている [8].政策反復
法は状態評価と政策改善を交互に繰り返す.Actor は,状
態から行動への確率分布である“ 確率的政策 (stochastic
policy) ”に従って行動を実行する.Critic は,actor の政
策下における各状態の“ 価値 (value) ”(利得 (return) の
期待値) を推定する.Critic で計算される TD (temporal
dierence) または TD-error と呼ばれる値を手がかりに
して actor は政策を改善する.Critic による状態の評価
を待っていては時間がかかりすぎ るので,actor の政策
改善と critic の政策評価は同時に実行される場合が多い.
Actor-critic アルゴ リズムは今 まで様々な強化学習
タス クへ適 用され ,有用性が 示され てきた .例えば
ASE/ACE[2][6] による倒立振子制御や RFALCON[13]
[5] に
よる倒立振子の振上げ制御などがある.Actor-critic ア
による倒立振子および梁上を転がるボールの制御,
[25] や [6] など があるが,
Q-learning [24] に代表される value-iteration 法ほど 多
くはなされていない.しかし Q-learning 等と比較すると
ルゴ リズムの解析については
以下の実用的利点がある.
状態の value だけについて推定すればよいため,連
続値を含むような行動出力への拡張が
比較して非常に容易である
Actor
[23].
Q-learning と
に おい て 確 率 的 政 策 を 用 い る こ とか ら ,
POMDP の環境 [18][7] やマルチプレイヤーゲーム
[14] などへの適用も可能である.
Actor の部分では状態観測に対する行動出力を学習
の環境
するため,従来の教師付き学習との組み合わせが容
易である.エキスパートの知識は,状態観測に対す
る行動出力である場合が多い.そのためエキスパー
トの知識との統合が容易である
適正度の履歴
[3].
(eligibility trace) は,報酬の遅れに対処
するための基本的メカニズムとして広く用いられて来た
[19].また,適正度の履歴は非マルコフ性に対処するため
2
人工知能学会誌
[22], [16].ASE/ACE [2] では actor と
critic の両方において適正度の履歴を用いている.Critic
における適正度の履歴に関する理論は, TD() [20] の
解析として多くの研究結果が示されてきた.だが actorcritic アルゴ リズムにおける actor の適正度の履歴につ
いての解析は皆無であった.本論文では actor が政策パ
ラメータの適正度の履歴を用いて政策を改善する actorcritic アルゴ リズムを提案し,その政策改善の方向につ
にも用いられる
いて考察する.
2.
(MDP) でモデル化できると仮定する.MDP は,状態集合
S ,選択可能な行動の集合 A,状態遷移関数 T : S A !
(S ) ただし (S ) は状態空間 Sにおいて定義される確率
分布,報酬関数 R : S A ! R より構成される.MDP
の状態,行動,報酬は各時刻 t 2 f0; 1; 2; g において
Prfat = ajst = s;g と表す.MDP では利得の期待値は
全状態 s について以下に定義される.
V (s) = E
=
X
2A
a
(A) を定義する.これは状態空間から行動空間 A に定
義される確率分布への写像関数である.エ−ジェントの意
志決定は,各時刻 t ごとに定義される政策関数
(t) に従っ
(a;s;t) = Prfat = ajst = s;(t)g で行動 atを選
強化学習の目的は,エージェントの利得
に改善し,再び同様の
れる
[23].
X
0
2S
(2)
k rt+k
0 < 1 は時間 t に対する未来の報酬
の重み付けを行うパラメータである.
エージェントの政策が時間とともに 変化しない場合,
(t) = ただし (t = 0; 1; 2 ) のとき,は定常
政策と呼ばれる.このときの行動選択確率を(a;s) =
value の計算と政策改善を繰り返
(Policy Iteration) と呼ば
0
(3)
(s;a;s0) や報酬 R(s;a) が既知ならば,最
適政策への収束が保証されるが,強化学習ではこれらは
予め知ることはできないため,次に紹介する
actor-critic
によって政策改善が行われる.
エージェント
Actor
st
-
確率的政策
at
行動 at の強化信号
6
rt + V^ (st+1 ) V^ (st )
TD-error
Critic V^ (s)
rt
st
-
状態観測
報酬
行動
?
(return) を最
(1)
[15].
n+1 (a;s) R(s;a)
状態遷移規則 T
環境
大化すること,およびそのための政策を見つけることで
つまり
s0
T (s;a;s0 )V (s0 )
2A
X
+ T (s;a;s0)V n (s0 ) V n (s)
s 2A
a
図1
ある.利得の評価方法として,次式の割引報酬の合計を
ただし,割引率
X
していく手法は,政策反復法
観測し,政策関数(a;s;t) の確率分布に従って行動
atを実行する.
(2) 行動 atにより,環境は T (st ;at;s0) の状態遷移確
率に従って st+1へ状態遷移し,期待値 R(st ;at) に
従い報酬 rtをエ−ジェントへ与える.
(3) 時刻 t を t + 1 に進めてステップ 1 へ戻る.
エ−ジェントは一般に,環境の状態遷移規則 T (s;a;s0)
や報酬 R(s;a) に関する知識をあらかじめ持っていない.
k =0
(a;s) R(s;a) + V n (s) を求めた
後,全状態 s について式 (3)を満たすように政策nをn+1
時刻 t において,エ−ジェントは環境の状態 stを
1
X
rtjs0 = s;
ある政策nにおいて全状態について
択する.エ−ジェントと環境は以下のやりとりを行う.
Vt =
t=0
)
t
とも一つ存在し,これが最適政策である
2 S ,at 2 A,rt 2 R で表される.状態遷移
T によって確率分布 T (s;a;s0) =
Prfst+1 = s0 jst = s;at = ag で表され,報酬は報酬関数
Rによって期待値 R(s;a) = E frtjst = s;at = ag で表さ
れる.ただし rtは全時刻において有界であるものとする.
学習の主体“エ−ジェント ”について,政策関数 : S !
用いる.
(
1
X
V (s) は value 関数と呼ばれ,状態 s の評価値を示す.全
ての状態 s 2 Sにおいて, V (s) V (s) となるとき,
定常政策0はより優れているという.MDP では,他の
規則は,状態遷移関数
(1)
号( 1996 年 1 月)
どんな政策よりも優れた,あるいは同等な政策が少なく
制御対象である“ 環境 ”は 下記のマルコフ決定過程
た確率
1
0
準備:割引報酬による状態評価
それぞれ st
巻
11
3.
一般的な
actor-critic アルゴ リズムの構成
Actor-Critic
1
アルゴリズム
2
actor-critic アルゴ リズムの概要
を示す [21] [4].Actor-critic アルゴ リズムは,政策反復
法における value の計算を critic による value の推定に
置き換え,さらに式 (3) による政策改善の判定を,TDerror という確率変数を用いた判定に置き換えたものと
図 と図 に一般的な
Actor に適正度の履歴を用いた Actor-Critic
(1) エージェントは環境において状態 stを観測する.
Actor は,確率的政策(t) に従って行動 atを実行する.
(2) Critic は報酬 rtを受け取り,次の状態 st+1 を観測し
Actor への強化信号とし て以下の TD-error
を計算する.
(TD-error) = rt + V^ (st+1 ) V^ (st )
(0 1) は割引率,
V^ (s) は Critic が推定した割引報酬の期待値を表す.
(3) TD error を用いて actor の行動選択確率を更新する.
(TD-error) > 0 ならば ,実行した行動 atは比較的好ましいと
考えられるので,この選択確率を増やす.
逆に (TD-error) < 0 ならば ,実行した行動 at は比較的好まし
くないと考えられるので,この選択確率を減らす.
(4) TD 法等を用いて critic の value の推定値を更新する.
例えば TD(0) ならば以下のように計算する.
V^ (st ) V^ (st ) + (TD-error), ただし は学習率である.
(5) ステップ (1) から繰り返す.
図2
一般的な
3
アルゴ リズム:
actor-critic アルゴ リズムの処理手続き
critic のV^ = V のとき,TD-
考えられる.その根拠は,
error の期待値は式 (3)の左辺に等しいことによる.よっ
actor-critic アルゴ リズムは,critic によって推定され
た value 関数を用いて,value を増加させる方向へ政策
て
(1) エージェントは環境において状態 stを観測する.
Actor は確率的政策(at ;st ;W (t)) により行動 atを実行
(2) Critic は報酬 rtを受け取り,次の状態 st+1 を観測し
actor への強化信号として以下の
TD-error
を計算する.
(TD-error) = rt + V^t(st+1 ) V^t 1 (st ) (4)
(0 1) は割引率,
V^t(s) は Critic が推定した割引報酬の期待値を表す.
(3) TD-error を用いて actor の行動選択確率を更新する.
ei (t) = @ ln (at ;st ;W (t))
@wi (t)
Di (t) = ei (t)+ Di(t 1) ,
wi (t) = (TD-error) Di (t)
W (t + 1) W (t) + p W (t)
(5)
ただし,ei (t) は適正度,Di (t) は適正度の履歴,
W (t) = (w1 (t);w2 (t); ;w` (t)) は政策パラ メータ,
(0 < 1) は適正度の履歴の割引率,
pは actor の学習定数を表す.
(4) TD 法等を用いて critic の value の推定値を更新する.
例えば TD(0) ならば以下のように計算する.
V^t+1 (st ) V^t(st ) + (TD-error), ただし は学習率.
V^t+1 (s) V^t(s), 8s 6= st
(5) 時刻 t を1つ進めてステップ (1) から繰り返す.
図3
Actor に適正度の履歴を用いた actor-critic アルゴ リズム
を改善するものと考えられる.
Actor の政策表現と政策改善方法にはバリエーション
critic のアルゴリズムとしては多くの場合 TD
法が用いられる.Actor-critic は以下の 2 点に特徴があ
る:第一に actor は確率的政策を用いる,第二に actor
は TD-error を用いて政策を改善する点である.本論文
では特に actor のアルゴリズムに注目する.
があるが,
4.
4・1
Actor
へ適正度の履歴を付加
3
actor-critic の詳細を示す.
ASE/ACE [2] はこのアルゴ リズムの具体例の一つと考
えられる.処理ステップ (3) に示されている actor の適正
度は,REINFORCE アルゴ リズム [26] で定義されてい
る物と同一である.適正度 ei (t) は政策関数のパラメー
タ wi (t) と実行した行動 atの相関を表している.Di (t)
は適正度の履歴 (eligibility trace) を表し,適正度を割引
図 に本論文が対象とする
率で割引きながら足し合わせることにより,今まで実
行してきた行動の履歴に関する情報を圧縮して保持する.
確率的政策のパラメータ表現
W 2 R`を定義する.これは各時
刻 t 2 f0; 1; 2; g において値 W (t) をとるものとする.
本論文では,W (t) を用いて政策関数(t) を(a;s;t) =
(a;s;W (t)) のようにパラメータ表現する.エージェン
トは W を調節することにより政策を変えることができ
パラメータベクトル
る.エージェントの行動選択確率を表す機構が,例えば
ニューラルネットならば,W はリンクの重み変数に相当
し,重み付きのルールベースシステムならば,W はルー
ルの重みに相当する.
(a;s;W ) の具体的な関数形につ
Actor は正の TD-error を受けとると,図 3手順 (3) の
処理によって,今まで実行してきた全行動の選択確率を
高めるように W を更新する.ただし過去に実行した行動
ほど 強化の大きさは割引率によって割引かれる.従来
actor-critic(図 2) では,時間 t の TD-error は行動 at
だけの強化に用いられていたのに対し,図 3の手法では,
時間 t の TD-error が行動 atの強化だけでなく,今まで
の
実行してきた行動全て at
1
;at 2; の強化に用いられて
2 actor-critic を式 (3)の代わり
TD-error を用いた政策反復法の一種とする考え方か
いる.このことは,図 の
に
いては,エージェントに実装できる計算資源の制限など ,
らは無意味に思えるが,非常に興味深い特徴を持つこと
一般に個別の問題ごとに制約が存在する.すなわちエー
を後に示す.
ジェントの構造および制約条件は (a;s;W ) の関数形で
規定される.W をパラメータとした分布関数として政策
を記述することの利点は,上記のように様々な行動選択
機構を持つエージェント全てに対して共通の理論的基礎
を与えられることである.また行動 a の集合が連続値の
場合は分布関数
(a;s;W ) を確率密度関数とすれば,行
動が離散の場合と全く同様に扱える.
4・2
= 0 の場合,本手法は完全に
図 2の actor-critic の一種になる.また, = で,かつ
critic が出力する割引報酬の推定値V^ (s) が全ての状態 s
について任意の定数 b のとき,図 3のアルゴ リズムは確
率的傾斜法 [10],[11] と同一になる.
Actor は,政策を表現するための実数パラメータベク
適正度の履歴の割引率
トル
W および適正度の履歴を保持するための Diに相当
するメモリ容量を必要とする.Diに要するメモリ量は W
アルゴリズムの詳細
のそれと同一である.
4
人工知能学会誌
4・3
8
Actor の割引率 = すなわち value 関数の割引率に等
3
wi(t) の合計は以下のように計
とき,V st
していれば,
しい場合,図 における
算できる.
t=0
=
=
=
=
=
rt + V^t (st+1 ) V^t
t=0
1
(st)
1
(st)
1
X
rt + V^t (st+1 ) V^t
t=0
t=0
t=0
1
X
t=0
t<0
ei (t)
1
X
=t
ei (t)
t
1
X
=t
ei (t) Vt
t
X
=0
t ei ( )
r + V^ (s ) V^ (s )
+1
!
Di (t)
t
r
V^t
1
(st)
1
!
V^t (st )
(6)
(7)
1
のとき
1
ように表されるシステムにおいて,評価値 rが
てE
1
2
1
きる.ところが
Di (t) = 0,かつV^tは 任意の有界
^
な定数とする.Vt (s) は 全ての t;s において有界とす
る.式 (7)は式 (6)へ式 (1)を適用して得る.式 (7)中の
ei (t)(Vt V^t (st )) は,時刻 t に実行した行動 atをどの
ように強化するのかを示している.REINFORCE アル
ゴリズムの定理 [26] によれば,行動 atの選択確率が wを
パラメータとし た関数 gにより Prfatjwg = g(at ;w) の
ただし
号( 1996 年 1 月)
どちらの行動をとっても確実に正しい方の行動を強化で
1
X
1
X
1
2
wi(t)
1
X
巻
(a ;st) = (a ;st) = 0:5 の
( ) = 9 となる.もし critic がV^ (st) = 9 を獲得
actor が a をとるなら式 (8)中の Vt V^ (st )
すなわち r b は 10 9 = 1 で必ずプラス,a をとるな
ら Vt V^ (st ) = 8 9 = 1 で必ずマイナスの値をとり,
酬 である場合を考える.
提案手法の解釈
1
X
11
wによっ
frjwg のように与えられる場合,以下が成り立つ.
@
@
ln g(at;w)g = @w
E frjwg (8)
@w
ただし b は atおよび rとは条件付き独立な値なら (定数
でも確率変数でも ) なんでも良く,評価値 rは直接報酬以
E f(r b)
(7)の
^
ei (t)(Vt Vt (st )) は,行動 atの適正度 ei (t) を式 (8)の
@
@w ln g (at ;w ) に,割引報酬合計 Vt を式 (8)の評価値 rに,
critic の推定値V^t (st) を式 (8)の b に対応させることが
できる.なぜなら critic の推定値V^t (st ) はアルゴリズム
外の割引報酬や平均報酬でも成り立つ.すると式
1
1
1
の処理手順上,行動 atや割引報酬合計 Vtを求めるより前
に確定しているので,明らかに atや Vtとは条件付独立だ
3
からである.よって図 のアルゴリズムは
= のとき実
際の利得 Vtの増加が最大となる方向へ,時刻 t に実行した
(t) を更新している
と考えられる.注目すべき点は,critic が明示的に推定し
た value 関数V^ は更新の期待値に対して影響を与えていな
行動 atを確率的に強化するように W
いが,更新の分散の大きさに対して影響を与えている点で
critic が value 関数を学習できるかど う
かに依存せずに,actor は政策を改善できると考えられる.
Critic が actor の政策更新の分散に影響を与える根拠を
ある.そのため,
以下の例で説明する.状態 stで行動 a1 または a2を選択で
き,a1を実行すると割引報酬
10,a2 を実行すると割引報
critic が value の推定に失敗し,例えば
V^ (st ) = 0 の場合,actor が a1 ,a2ど ちらの行動をとっ
ても Vt V^ (st ) は必ずプラスの値になるので,正しい行
動を強化する確率は 0:5 になる.このように V^ の値によっ
て重み更新の分散は大きく異なり,学習速度に影響する
が,重み更新の期待値は同じなのでど ちらの場合も学習
^
^
value に近付くと,式 (8)の Vt V (st) も期待値がゼロに
近付く.以上より critic は actor の政策更新のステップ
は可能である.また政策が最適に近付き,かつV も最適
幅を適応的に制御する役割を果たしていると考えられる.
上記の考察は,割引率が = の場合だけだが, を
(0 ) とすることにより,政策の更新をす
る際に critic の推定した value 関数の勾配を登るか,そ
別の値
れともトレーニング系列の割引報酬の勾配を登るのかの
= 0 のときは図 2に示した一般的
actor-critic と同じなので,critic の推定した value 関
数の勾配を登る.0 < < のときは,おおよそ中間的
度合を調節できる.
な
な登りかたをすると考えられる.
5.
実
験
本章では,解析から予想された適正度の履歴の効果を
確認するため,提案手法を単純な線形制御問題に適用し
た計算機シミュレーションを示す.
5・1
実験設定: 線形 2 次形式制御問題
ベンチマークとして以下の線形
える
2 次形式制御問題を考
[1].ある時間ステップ t において,環境の状態はあ
る連続値の実数 xtにある.エージェントは同じく連続値
の実数 atで表される行動を選択する.環境の状態遷移は
以下で与える.
xt+1 = xt + at + noise
(9)
ただし noise は標準偏差 0:5 平均 0 の正規分布で与える.
直接報酬は以下のように与える.
rt
=
x2t a2t
(10)
エージェントの学習目標は,初期状態より計算される以
下の割引報酬合計を最大化することである.
1
X
t=0
t rt
本問題は線形
(11)
2 次形式制御問題であることより,最適な
Riccati 方程式
制御規則を解析的に求めることができる.
より,最適レギュレータは以下の状態フィード バックで
Actor に適正度の履歴を用いた Actor-Critic
5
アルゴ リズム:
e2
与えられる.
at
=
k1 xt
, ただし
2p
(12)
1 + 2 + 4 + 1
最適な value 関数は V (xt) = k xt ただし k は何らか
k1 = 1
2
2
2
2
の正の定数の形式で与えられる.本実験では,遷移可能
な状態空間は
[ 4; 4] に制限する.式 (9)で示される状態
遷移が上記の範囲を超える場合は,制限範囲までしか移
動できないものとする.エージェントの行動についても
同様に
[ 4; 4] の範囲外の行動を実行しても,環境では制
限の範囲でしか実行されないとした.
5・2 エージェント の実装
x 1 Actor の実装
行動が連続値の場合,政策
41
)2 2 )(1 )
= 0:001, w の
1
0:35 0:15 の範囲内でランダムに初期化,w
は 0 すなわち = 0:5 に初期化した.
初期値は
x2
2
Critic の実装
Critic では状態観測の空間を格子状に分割離散化し,そ
value を学習する.本実験で
は 4 x 4 の状態空間を 3 等分した場合と 10 等分し
た場合について示す.Critic は TD(0) 法を用いて value
関数を推定する.Critic では観測入力 xtに対する V (xt)
を推定する.TD(0) の学習率は 0:2 とした.
れぞれのグリッドに対して
実験結果
4, 図 5, 図 6, 図 7, 図 8は LQR 問題において割引率
= 0:9 の場合における各アルゴリズムで得られたフィー
ドバックゲインの 100 試行の結果を示す.
図 4は状態空間を 3 等分した critic と = 0 つまり適正
度の履歴を用いない actor による学習の様子を示す.図
6は状態空間を 10 等分した critic と = 0 つまり適正度
の履歴を用いない actor による学習の様子を示す.図 6
図
(a;s;W ) は確率密度関数
2 つのパラメータを持つ.政策が式
(13)に示す正規分布で与えられた場合,パラメータと
に関する適正度は以下のように計算される.
1
(a )
(a;s;W ) = p exp(
22
2
a e = t 2
(a )2 2
e = t 3
2
このような行動選択メカニズムは
)
(13)
のアルゴリズムは最適なフィード バックゲイン付近に収
4
3 分割して value を表現する critic
束している.ところが,図 では全く学習できない.こ
(14)
れより,状態空間を
(15)
能力が不十分であるためであることは明らかである.
Gaussian unit と呼ば
れ,ランダムな探査の度合いを自ら制御する特徴を有す
る
2
エージェントのパラメータは,学習係数
x3
となることは ・ 節にてすでに述べた.正規分布は平均
値と標準偏差の
@
= e @w
= ((at
[26].ここで式 (14),(15)においてパラメータが分母
0 へ近付くと適正度が発散
となっていることより,が
では,適正度の履歴なしで政策を学習するには関数近似
5
3 等分した critic と = = 0:9 つま
り適正度の履歴を使った actor による学習の様子を示す.
学習の速さと収束した解の質の両方において,図 4や図
5 より良い結果を示している.この性能向上には actor
図 は状態空間を
の適正度の履歴が関与していることは明らかである.学
することに注意しなければならない.適正度の発散はア
習が速くなった理由は,適正度の履歴が情報の伝搬を加
ルゴリズムの動作に悪い影響を及ぼす.この問題に対処
速しているためと考えられる.解の質が向上した理由は,
するための一つの方法として,
の値に応じて政策パラ
メータの更新のステップ幅を制御することが考えられる.
更新のステップ幅を2に比例させると,適正度は以下の
ように計算される.
e = at , e = (at
(16)
Actor はまずとを計算し,正規分布に従って行動出力
2 つの内部変数 w ;w を持
1
ち,これを用いてとを以下のように計算する.
= w1 xt
1
, = 1 + exp(
w2)
2
(17)
このとき,w1はフィードバックゲインとして見ることが
できる.を上記のように計算するのは,の値が負にな
るのを防ぐためである.エージェント内部変数 w1と w2
に対応する適正度をそれぞれ e1
適正度 e1
e1
, e と表す.式 (16)より,
2
, e は以下に与えられる.
@
= e @w
= (at )xt
2
1
ため,得られた政策の平均値に関して,
actor に適正度
critic の性能には依存しない.こ
8
9
は式 (10), で定義される value 関数をと で張られるパ
の履歴を用いた場合は
)2 2
を決定する.エージェントは
4・3 節の解析で示したように actor が実際の利得の勾配
を用いて政策を改善しているためだと考えられる.その
の特徴は解の分散が大きい図 からも観察できる.図
ラメータ空間で表示したものである.最適解周辺ではほ
8
とんど 平らになっている.よって図 で得た政策の分散
が大きい理由は,政策更新のステップ幅のコントロール
を行っていないために最適解周辺で政策が収束できずに
critic
浮遊しているためであることが分かる.これより,
が局所解周辺において
actor の政策更新ステップ幅を小
さくするようにコントロールしていることが分かる.
7
図 のアルゴ リズムは政策の平均値と分散において最
も良い解を得ている.これは
critic が少ない誤差で value
関数を学習したためだと考えられる.
critic を用いて actorcritic を比較した場合,適正度の履歴を使用する actor の
この実験では,同じ性能を持つ
6
人工知能学会誌
方が,使用しない
11
巻
1
号( 1996 年 1 月)
actor よりも良い性能を示した.
0.2
6.
倒立振子制御問題への適用
0
提案手法の有用性について示すため,多次元の状態観
らは行動を離散値としていたので,いくつか修正を加え,
-0.2
Feedback gain
2 次形式の倒立振子制御問題
(図 10) へ適用する.[2] の実験設定を参考にしたが,彼
測を必要とする非線形・非
gamma = 0.9
Critic’s Grid = 3
beta = 0.0
-0.4
-0.6
行動を連続値として計算機実験を行った.
-0.8
optimum
6・1
倒立振子問題の定式化
= 1:0(kg),ポールの質量 m = 0:1(kg),
ポールの長さ 2` = 1(m),重力加速度 g = 9:8(m=sec ),
台車に加えられる力 F (N),台車の摩擦係数c = 0:0005,
ポールの摩擦係数p = 0:000002 とすると,図 10のダ イ
-1
台車の質量 M
0
2
図4
500
1000
1500
2000 2500 3000
Learning steps
3500
4000
4500
5000
= 0:9, Critic は 3 分割グリッド の関数近似,Actor に適正
度の履歴を用いない場合の
100 試行の平均と分散.
ナミクスは以下で表される.
F m`_ 2 sin )
M +m
m cos2 M +m
cos (c sgn(x
_)
`
4
3
p _
m`
0.2
F + m` _2 sin cos c sgn(x_ )
x =
M +m
本実験では t = 0:02sec の離散時間システムとして近似
した.エージェントは (x; x_ ;; _) を観測し,行動として台
車に加える力 F を出力する.エージェントは行動出力と
して任意の連続値をとることができるが,F = 20(N)
0
の範囲を超える場合には,環境はこの制限を超える分を
_ _) = (0; 0; 0; 0)
無視して行動を実行する.環境は (x; x;;
の初期状態から始まる.ポールの角度が 12 度を超え
るか,または台車の中心 x が 2:4 の範囲からはみ出す
と,環境からエージェントへ 1 の報酬が与えられ,環境
は初期状態へ戻る.
6・2
gamma = 0.9
Critic’s Grid = 3
beta = 0.9
-0.2
Feedback gain
g sin +
 =
-0.4
-0.6
-0.8
optimum
-1
0
図5
500
1000
1500
2000 2500 3000
Learning steps
3500
4000
4500
5000
= 0:9, Critic は 3 分割グリッド の関数近似,Actor に適正
度の履歴を使用した場合の
100 試行の平均と分散.
エージェント の実装
actor は,式 (13),(16)で示したのと同様の実
(x; x_ ;; _) = (2:4 m; 2 m/sec;
12=180 rad; 1:5 rad/sec) の 範 囲に 限 定し た .
エージェントは 5 つの内部変数 w w を持ち,これ
本実験の
0.2
装である.状態空間は
を用いてと を以下のように計算する.
_
= w 2x:t4 + w x2_t + w 12=t180 + w 1:t5
1
= 0:1+
(18)
1 + exp( w )
1
2
3
4
5
LQR の例題の場合と同様にして,適正度 e ; ;e は以
1
-0.2
-0.4
-0.6
-0.8
optimum
5
-1
下に与えられる.
e1
e3
e5
gamma = 0.9
Critic’s Grid = 10
beta = 0.0
5
Feedback gain
1
0
= (at ) xt , e = (at ) x_t
= (at ) t , e = (at ) _t
= ((at ) )(1 + 0:1 )
0
2
4
2
2
Critic は状態観測の空間を格子状に分割して離散化し,
図6
500
1000
1500
= 0 9, Critic 10
2000 2500 3000
Learning steps
3500
4000
5000
Actor に適
.
:
は
分割グリッド の関数近似,
正度の履歴を用いない場合の
試行の平均と分散
100
4500
Actor に適正度の履歴を用いた Actor-Critic
7
アルゴ リズム:
0.2
0
-0.2
Feedback gain
gamma = 0.9
Critic’s Grid = 10
beta = 0.9
F
-0.4
x=0
-0.6
図 10
-0.8
j j
-
x
-
倒立振子制御問題.
optimum
-1
それぞれのグリッドに対して
0
500
1000
1500
= 0 9, Critic 10
2000 2500 3000
Learning steps
3500
4000
4500
5000
3 等分,つまり 3 = 81 個の矩形に分割した.割引
率 = 0:95, = 0:5, p = 0:001 に設定した.
Actor に適
.
100
4
して
:
は
分割グリッド の関数近似,
正度の履歴を用いた場合の
試行の平均と分散
図7
TD(0) 法を用いて value を
推定する.本実験では正規化された状態空間を各軸に対
6・3
実
験
結 果
-0.4
11は異なる 3 種類のアルゴリズムによる学習の様子
を示す.1 trial は初期状態からポールや台車が許容範囲
をはみ出すまでを表す.Actor に適正度の履歴を用いた
actor-critic が最も良い結果を得たのに対し,適正度の履
歴を用いていない actor-critic では全く学習できなかっ
た. Critic を用いずに actor と適正度の履歴だけを用い
-0.6
おいて,政策を保持するための関数近似が全く同じであ
図
0.2
0
gamma = 0.9
beta = 0.9
Learning without critic
Feedback gain
-0.2
た確率的傾斜法では学習できた.全てのアルゴ リズムに
actor に適正度の履歴を用いるかど
るにもかかわらず,
-0.8
うかで大きな差が生じた.
optimum
-1
3000
0
1000
1500
2000 2500 3000
Learning steps
3500
4000
4500
5000
^ ( ) = 0 for all
100
= 0 9, Critic
actor
:
を用いないで,つまりV x
xと
して
の適正度の履歴だけで学習した場合の
試行の
平均と分散.確率的傾斜法で学習することと等価.
Actor/Critic
using actor’s
eligibility trace
2500
Time steps until failure
図8
500
2000
Optimum
1500
0
-50
-100
-150
-200
-250
-300
-350
1000
Actor/Critic without
actor’s eligibility trace
500
0
-2 -1.5
-1 -0.5
0
Feedback gain
図9
Actor only
using actor’s
eligibility trace
割引率γ
= 0.
0.5
0
0.5
Deviation
1 1.5
2
0
=0.9 の場合の value function の形状. = 0:5884,
50
100
150
200
250
300
350
400
450
500
Trials
1
図 11
連続値行動の倒立振子制御問題への適用結果. = 0:95,
Critic は 3 × 3 × 3 × 3 分割グリッド の関数近似,Actor
は線形関数を用いた.それぞれ 100 試行の平均
8
人工知能学会誌
7.
考
察
政策の表現:
11
巻
1
号( 1996 年 1 月)
actor に適正度の
actor-critic と比較を行い,解析
および 倒立振子制御問題を取り上げ,
Actor-critic アルゴ リズムでは,まず政策
履歴を用いない従来の
結果より予想された性質について実験的に確認した.非
の関数近似能力が十分であることが要求される.その上
マルコフな環境における本手法の挙動についての解析は
で,十分な学習を行うためには
今後の課題である.
上げるよりも
critic の関数近似能力を
actor に適正度の履歴を用いた方が、本実
験では安いコストで学習させることができた.
政策更新ステップ幅のコント ロール:
4・3 節において,
critic は actor の政策更新ステップ幅をコントロールし,
局所解の頂上付近では幅を小さくすることを示した.実
験を通して
critic が学習途中の効率の改善と,収束時の
政策パラメータのド リフトを抑える効果のあることを観
察した.
Critic へ適用するアル
TD() は非マルコフ環境に
対して頑健であると言われている [17] [22].また actor
非マルコフ環境における頑健性:
ゴリズムには任意性がある.
に適正度の履歴を用いた場合も非マルコフ環境に対して
頑健である
[11].Critic に TD() を用いれば 、本アルゴ
リズムは非マルコフ環境においてさらに頑健となること
が期待できる.
DP ベースの手法と確率的傾斜法の並列学習:Actor に
おける政策学習アルゴ リズムの基礎となる確率的傾斜法
value 関数の勾配を求めて政
DP 手法である.そのため確率
は,モンテカルロ法により
策改善を行っており,非
的傾斜法単体では,
DP を基礎とする強化学習手法に比
較し,マルコフ決定過程の環境では学習の効率は悪いが,
TD(0) を始めとした
非マルコフの環境では頑健である.
DP を基礎とする手法は,逆にマルコフ決定過程の環境
では学習の効率は良いが,非マルコフの環境では頑健性
critic における value 関数の学習に
DP を基礎とする TD(0) 法を用い,actor における政策
の学習には非 DP 手法である確率的傾斜法を用いて,高
に欠ける.本手法は
い独立性を保ちながらそれぞれ並列に進行することによ
り,マルコフ決定過程の環境における学習の効率性と非
マルコフ環境における頑健性を両立させることができる.
8.
お わ
り に
actor に適正度の履歴を用いた actor-critic
Actor
の適正度の履歴の割引率と value 関数の割引率が等しい
場合,actor の政策更新は critic の推定した value 関数
本論文では
アルゴリズムを示し,その動作について考察した.
の勾配の方向ではなく,実際のトレーニング系列の割引
(actual return) の勾配の方向へ行われる.そのた
め critic での value の推定が致命的に不正確であっても
actor は政策を学習可能である.Critic が推定する value
は actor の政策更新のステップ幅をコントロールする役
割を持つ.Critic での value 関数の推定が正確ならば,学
報酬
習途中の性能が改善され,最適政策付近ではステップ幅
1
が自動的に小さくなる. 次元の線形
2 次形式制御問題
}
参
考 文
献}
[1] Baird, L.C.: ReinforcementLearning in Continuous Time:
Advantage Updating, Proceedings of IEEE International
Conference on Neural Networks , Vol.IV, pp.2448{2453
(1994).
[2] Barto, A.G., Sutton, R.S. & Anderson, C.W.: Neuronlike
Adaptive Elements That Can Solve DiÆcult Learning Control Problems, IEEE Transactions on Systems, Man, and
Cybernetics , vol.SMC-13, no.5, September/October 1983,
pp.834{846.
[3] Clouse, J.A. & Utogo, P.E.: A Teaching Method for Reinforcement Learning, Proc. of the 9th International Conference on Machine Learning , pp.93{101 (1992).
[4] Crites, R.H. & Barto, A.G.: An Actor/Critic Algorithm
that is Equivalent to Q-Learning, Advances in Neural Information Processing Systems 7 , pp.401{408 (1994).
[5] Doya, K. : EÆcient Nonlinear Control with Actor-Tutor
Architecture, Advances in Neural Information Processing
Systems 9 , pp.1012{1018 (1996).
[6] Gullapalli, V.: Reinforcement Learning and Its Application to Control, PhD Thesis , University of Massachusetts,
Amherst, COINS Technical Report 92{10 (1992).
[7] Jaakkola, T., Singh, S.P., & Jordan, M.I.: Reinforcement
Learning Algorithm for Partially Observable Markov Decision Problems, Advances in Neural Information Processing
Systems 7 , pp.345{352 (1994).
[8] Kaelbling, L. P., & Littman, M.L., & Moore, A.W.: Reinforcement Learning: A Survey, Journal of Articial Intelligence Research , Vol.4, pp.237{277 (1996).
[9] Kimura, H., Yamamura, M. & Kobayashi, S.: Reinforcement Learning by Stochastic Hill Climbing on Discounted
Reward, Proceedings of the 12th International Conference
on Machine Learning , pp.295{303 (1995).
[10] 木村 元,山村 雅幸,小林 重信: 部分観測マルコフ決定過
程下での強化学習:確率的傾斜法による接近,人工知能学会誌,
Vol.11, No.5, pp.761{768 (1996).
[11] Kimura, H., Miyazaki, K. & Kobayashi, S.: Reinforcement Learning in POMDPs with Function Approximation,
Proceedings of the 14th International Conference on Machine Learning , pp.152{160 (1997).
[12] Kimura, H. & Kobayashi, S.: An Analysis of Actor/Critic Algorithms using Eligibility Traces: Reinforcement Learning with Imperfect Value Function, 15th International Conference on Machine Learning , pp.278{286
(1998).
[13] Lin, C.J. & Lin, C.T.: Reinforcement Learning for
An ART-Based Fuzzy Adaptive Learning Control Network, IEEE Transactions on Neural Networks , Vol.7, No.3,
pp.709{731 (1996).
[14] Littman, M.L.: Markov games as a framework for multiagent reinforcement learning, Proc. of 11th International
Conference on Machine Learning , pp.157{163 (1994).
[15] 小笠原正巳,坂本武司 著,北川 敏男 編: 情報科学講座 (全
62 巻)A・5・1 マルコフ過程,共立出版 (1967).
[16] Pendrith, M.D. & Ryan, M.R.K.: Actual return reinforcementlearning versus Temporal Dierences: Some theoretical and experimental results, Proceedings of the 13th International Conference on Machine Learning , pp.373{381
(1996).
[17] Peng, J. & Williams, R.J.: Incremental Multi-Step QLearning, Proceedings of the 11th International Conference
Actor に適正度の履歴を用いた Actor-Critic
アルゴ リズム:
on Machine Learning , pp.226{232 (1994).
[18] Singh, S.P., Jaakkola, T. & Jordan, M.I.: Learning
Without State-Estimation in Partially Observable Markovian Decision Processes, Proceedings of the 11th International Conference on Machine Learning , pp.284{292
(1994).
[19] Singh, S.P., & Sutton, R.S.: Reinforcement Learning
with Replacing Eligibility Traces, Machine Learning 22 ,
pp.123{158 (1996).
[20] Sutton, R.S.: Learning to Predict by the Methods of
Temporal Dierences, Machine Learning 3 , pp.9{44 (1988).
[21] Sutton, R.S.: Reinforcement Learning Architectures for
Animats, Proceedings of the 1st International Conference
on Simulation of Adaptive Behavior , pp.288{295 (1990).
[22] Sutton, R.S.: TD Models: Modeling the world at a Mixture of Time Scales, Proceedings of the 12th International
Conference on Machine Learning , pp.531{539 (1995).
[23] Sutton, R.S. & Barto, A.: Reinforcement Learning: An
Introduction, A Bradford Book , The MIT Press (1998).
[24] Watkins, C.J.C.H., & Dayan, P.: Technical Note: QLearning, Machine Learning 8 , pp.55{68 (1992).
[25] Williams, R. J. & Baird, L. C.: A Mathematical Analysis of Actor-Critic Architectures for Learning Optimal Controls through Incremental Dynamic Programming, Proceedings of the Sixth Yale Workshop on Adaptive and Learning
Systems , pp.96{101. Center for Systems Science, Dunham
Laboratory, Yale University, New Haven (1990).
[26] Williams, R. J.: Simple Statistical Gradient Following
Algorithms for Connectionist Reinforcement Learning, Machine Learning 8 , pp.229{256 (1992).
〔担当委員:××○○〕
19YY 年 MM 月 DD 日
著
者 紹
木村
受理
介
元
( 正会員)
[email protected]
1992
1994
1997
1998
年東京工業大学工学部制御工学科卒業.
年同大学大学院総合
理工 学 研究 科 知能 科 学専 攻 修 士課 程 修了 .
年同 大 学大 学 院博 士 課 程
月日 本 学 術 振興 会
研究員,
年
月,東 京 工 業大
修了 ,同年
学大 学院総 合理 工学 研究科 助手 ,現 在に 至る.人工 知能 ,特に強 化学習に
関 す る 研 究 を 行って い る .計 測 自 動 制 御 学 会 ,日 本 ロボット 学 会 各 会 員 .
4
PD
小林
4
重信
( 正会員)
[email protected]
1974 年東京工業大学大学院博士課程経営工学専攻修了.同年 4 月,同大学工学部
制御工学科助手.1981 年 8 月,同大学大学院総合理工学研究科助教授.1990 年
8 月,教授.現在に至る.問題解決と推論制御,知識獲得と学習などの研究に従
事.計測自動制御学会,情報処理学会各会員.
9
ダウンロード

PDF file, paper8A8. in Japanese.