353✞
✝論 文 ✆

Technical Papers

報酬の分散を推定する TD アルゴリズムと MeanVariance 強化学習法の提案
TD Algorithm for the Variance of Return and Mean-Variance Reinforcement Learning
佐藤 誠

Makoto Sato

東京工業大学 総合理工学研究科
Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology

satom@fe.dis.titech.ac.jp

木村 元

（同

小林 重信

（同

Hajime Kimura

Shibenobu Kobayashi

上）gen@fe.dis.titech.ac.jp

上）kobayashi@dis.titech.ac.jp

keywords: reinforcement learning, Markov decision processes, variance penalized criteria, gradient-based learning, machine mainenance problem, TD-method
Summary
Estimating probability distributions on returns provides various sophisticated decision making
schemes for control problems in Markov environments, including risk-sensitive control, eﬃcient explorationof environments and so on. Many reinforcement learning algorithms, however, have simply relied on the
expected return. This paper provides a scheme of decision making using mean and variance of returndistributions. This paper presents a TD algorithm for estimating the variance of return in MDP(Markov
decision processes) environments and a gradient-based reinforcement learning algorithm on the variancepenalized criterion, which is a typical criterion in risk-avoiding control. Empirical results demonstrate
behaviors of the algorithms and validates of the criterion for risk-avoiding sequential decision tasks.

1. は じ め に
近年の強化学習における最も重要な進歩は動的計画法(DP) の理論と統合されたことである．その結果，政策の最適性，関数近似と組み合わせた場合の収束先，観測の不完全性のモデル化など実問題を扱う上で必要となる問題を理論的に扱うことが可能となった [Sutton 98, Tsitsiklis

96]．DP 理論に基づく強化学習の枠組では，行動決定の主体であるエージェントはマルコフ決定過程 (MDPs) な
どの確率モデルで表現された環境中を遷移し，その結果得た経験を利用して政策の学習を行う．政策の善し悪しを決める政策評価規範 (policy criteria) は，定義された利得 (return) に基づき与えられる．そして，各状態の各行動について，定義された政策評価規範に関連するなんらかの価値を推定し政策学習に利用する．例えば，代表的動価値を如何に効率的に推定するかという問題である．

Temporal Diﬀerence(TD) 法 [Sutton 88] は行動価値を推定する代表的な方法である．TD 法は環境モデル用いず，行動価値をその状態からの遷移先の状態の価値と直接報酬のサンプルのみからを推定する (bootstrap) する
単純な推定方式であり，1 ステップあたりの時間計算量と環境モデルパラメータを保持する空間計算量に関して効率的であるといえる。そのため，ニューラルネット，線形回帰などさまざまな関数近似と組み合わせることが可能であり，TD 法を用いることにより，強化学習を状態数が非常に多い実問題へ適用することが可能となった．実際，強化学習の応用研究の多くは TD 法を関数近似と組み合わせて利用している [Crites 96, Zhang 96, Neuneier97, Singh 97, Brown 98]．

な強化学習法である Q-learning [Watkins 89] は，無限ところで，これまで提案された多くの強化学習手法は期間の総割引報酬を利得として定義し，初期状態からあ

政策評価規範として何らかの利得の期待値を採用している政策に従い状態遷移した場合の期待利得を政策評価規るが，これらは常に有効とは限らない．一般にマルコフ範としている．そして各状態の各行動について Q-value

決定過程において得られる利得は確率変数であり，何らと呼ばれる行動価値 (action value) を推定し政策学習にかの確率分布に従い発生する．ところが，利得の期待値利用する．そこでこの枠組において重要となるのは，行が同じだが異なる分布をした 2 つの政策を，従来の強化

354

人工知能学会論文誌

学習手法は同じ価値の政策と見なしてしまう．例えば，大16 巻 3 号 F（2001 年）

2・1 利得の確率分布を推定する既存研究について

きな利得と同じ大きさの損失 (負の利得) が 50%ずつの確

多くの強化学習手法では，各状態，各行動についてそ率で生じる政策と，全く利得が得られない政策を同じ価の時点の政策下での利得の期待値のみが推定されるが，値と見なす．現実世界では，期待値のみに基づいた評価

利得の確率分布を明示的に推定し利用する手法もいくつ

方法ではなく，それぞれの政策に従った結果生じる利得

か提案されている．

の確率分布の情報を最大限に利用し，より洗練された行[McCallum 95] は部分観測マルコフ決定過程 (POMDPs)

動選択を行う政策が求められている．そこで，金融工学

下での強化学習手法のなかで，利得のサンプルを全て保や OR の分野では，利得の期待値だけでなく分布も考慮存しておくことで利得の分布を得ている．そして，部分した政策評価規範をはじめ，さまざまな規範に関する研観測マルコフ決定過程下で部分観測性を解消するために究が行われている [Fernandez 95, Marcus 97, Kadota

行う状態表現変更の際に，ノンパラメトリック統計を用

98]. 特に金融工学が扱う問題領域では，利得の期待値はいてその変更の必要性を判断している．しかし，このア最適値よりも劣るが大きな損失を被る可能性が低い政策

プローチは全てのサンプルを保持する必要がある．

が最も高く評価されることが多い．
利得のリスクを考慮した政策という観点から従来研究を概観する．Q-learning や Average Reward Learning(ARL) [Mahadevan 96, Schwartz 93] の政策評価規範
は利得の期待値に基づいているため，利得のリスクを考慮した政策の学習を行うことはできない．そこで，最悪ケースを比較したミニマックス規範に基づく強化学習法[Heger 94] や利得のばらつきが多い行動に負のバイアスをかけて評価する Risk-Sensitive Q-learning [Neuneier98] が提案されている．これまで，利得の確率分布を明示的に推定し，推定された確率分布に基づきリスクの低い政策を学習する手法は提案されていない．これは，利得の確率分布を推定する効率的な方法が存在しなかったためと考えられる．

[Dearden 98] は利得の正規分布を求めるために，正規γ分布とベイズ推定によってパラメータ推定を行っている．
そして，それぞれの行動に関する利得分布を利用して，強化学習でしばしば問題となる exploration と exploitationのトレードオフの問題を解消するための状態空間の効率的な探索方法を提案している．しかし，この方法は各状
態・行動について 4 つの変数を保持する必要があり，数値積分など複雑な計算が必要になる．

[Munos 99] はマルコフ連鎖 (Markov Chain) における利得の分散を求めるベルマン方程式を導出し，連続な状態空間の分割の問題を扱っている．しかし，この方法
は環境のモデルパラメータを必要とし動的計画法 (Value

Iteration) によって値を求めている.
これらの例のように，利得の確率分布を得ることで環境に関して利用できる情報が増え，高度な意志決定を行

本論文では，利得の確率分布の期待値と分散という統うことが可能になる。しかし上で述べた方法は，報酬を計量に注目し，利得の分散を推定する TD アルゴリズム(本論文では TD 法に属するアルゴリズムを TD アルゴ
リズムと呼ぶ) を提案する．そして，リスクを考慮した規範として良く知られた variance penalized 規範 (meanvariance 規範とも呼ばれる)[Elon 91, White 88] に基づ
く新しい強化学習アルゴリズムを提案する．2 章におい

すべてサンプルする必要があったり，環境に関して状態遷移確率などのモデルパラメータが必要という問題点がある。

2・2 マルコフ決定過程下での利得分散
本論文では，[Munos 99] と同様に利得の分散を明示的て利得の期待値と分散を効率的に推定する方法を提案すに推定する。ただし，1) 環境としてマルコフ連鎖ではな

る．3 章では推定された利得の期待値と分散に基づきリくマルコフ決定過程 (Markov Decision Processes) を対

スクを考慮した政策を学習する variance penalized 強化

象とする，2) 直接報酬に関しては，通常用いられる決定

学習法を提案する．4 章では提案した学習アルゴリズムを的なものではなくノイズを含む確率的な関数を扱う，3)

単純な機械メンテナンス問題に適用し有効性を示す．最分散値の推定方法として，環境モデルを必要としない TD

後に 5 章において本論文の成果と今後の課題についてまアルゴリズムを開発する，という 3 つの拡張を行う。

とめる．

本論文で扱うのは，無限期間の離散時間・離散状態のマ
ルコフ決定過程であり，強化学習の標準的な枠組みに従い，学習を行うエージェントはマルコフ決定過程で表現される

2. 利得の分散を推定する TD アルゴリズムの提案

環境と相互作用を行うものとする．各時刻 t ∈ {0, 1, 2, . . .}において，状態，行動，報酬が決まり，それぞれ，st ∈ S,

at ∈ A, rt ∈ R と表す．
a

環境の状態遷移は状態遷移確率 Pss
 = Pr{st+1 = s |st =本章では，利得の分布を推定する既存研究を概観した
後，利得の分散を推定するための TD アルゴリズムを提案しその収束を証明する．

s, at = a} によって決まり，報酬は期待値に関する関数
Rass = E{rt+1 |st = s, at = a, st+1 = s }，および分散に関する関数 rass = V ar{rt+1 |st = s, at = a, st+1 = s } に

報酬の分散を推定する TD アルゴリズムと Mean-Variance 強化学習法の提案
a
よって決まる．なお，Rass ，rss
 および直接報酬に加わるノイズはすべて有界と仮定する．エージェントは l 次

355

ズムは，マルコフ決定過程におけるベルマン方程式を利用した確率的近似アルゴリズムである．

元の政策パラメータベクトル θ ∈ Rl を基に各状態，各

さて，前節で導出したベルマン方程式に基づいて，利行動について政策 π(s, a, θ) = Pr{at = a|st = s, θ} に従得の分散を推定するための TD アルゴリズムを提案する．

い行動を選択する．

このアルゴリズムは状態 i から状態 j に遷移した場合，

ここで利得を，時刻 t から無限時刻先までの総割引報∞kk=0 γ rt+k+1 と定義する．ただし γ ∈ [0, 1)
は割引率である．そして，時刻 t において状態 s におり，
政策 π に従ったときの利得の期待値と分散をそれぞれ以酬 Rt =

以下の更新式に従う．ただし，βt ，εt は正のステップサ
イズパラメータである.

Vt+1 (i) = (1 − βt )Vt (i) + βt (rt+1 + γVt (j)),(6)

下のように表す．

V π (s) = E{Rt |st = s, π},(1)v π (s) = V ar{Rt |st = s, π}.

(2)

なお今後，式 (1)，式 (2) をそれぞれ状態 s の期待価
値，分散価値と呼ぶ．式 (2) の v π (s) に関して，以下のベルマン方程式が得られる (証明：付録 A 参照)．

v π (s) =π(s, a)

a



a
a
π 
Pss
(s ) − V π (s))2 {(Rss + γVs

vt+1 (i) = (1 − εt )vt (i) + εt {(rt+1 + γVt (j)−Vt (i))2 + γ 2 vt (j)}.
ここで以下の定理が成立する．
［定理 2.1］（TD アルゴリズムの収束） すべての s について, Vt (s) と vt (s) はそれぞれ式 (6) と式 (7) の TD
アルゴリズムによって生じた乱数系列とする．このとき，
ステップサイズパラメータ βt ，εt が共に条件，
∞


a
2 π 
+rss
(3)
 + γ v (s )}

π
π
π 
π
Pss
(s ) − V π (s))2 + rss=
 {(Rss + γVs

+γ 2 v π (s )}(4)Rπss =
π
rss
 =


a


a


a

βt = ∞,

∞


t=0

t=0

∞


∞


εt = ∞,

t=0

βt2 < ∞,
ε2t < ∞.

t=0を満たすならば，すべての s ∈ S について, 系列 Vt (s)

ただし，
π
Pss
 =

(7)

と vt (s) はそれぞれ V π (s) と v π (s) に概収束する．

aπ(s, a)Pss,《証明》 付録 B 参照.

aaππ(s, a)Pss
 Rss /Pss ,この TD アルゴリズムの利点の一つは, 様々な線形近似手法やニューラルネットワークなどの関数近似と組み

a
a
π 2
a
π
π(s, a)Pss {(Rss − Rss ) + rss }/Pss .

合わせが容易なことである．この特徴は，状態数の多い
マルコフ決定過程における効率的・現実的な利得の分散式 (3), (4) は状態 s から政策 π によって得られる利得の分散が，状態 s と次の状態 s に関連する利得の期待推定を可能にする．
また，TD 法は価値の推定のために遷移先の状態の価値と分散および s と s に関連するマルコフモデルの部分

値の推定値を使うが，これは，3 章で述べるような評価的なモデルパラメータのみから求められることを意味し関数の勾配に従って政策を少しずつ更新する学習アルゴπている．この式を利用して v (s) を求める方法として，

リズムと組み合わせた場合には収束速度の点で効率的とπππすべての s, a, s に関して V π (s)，Pss
 ，Rss ，rss をなる．なぜなら，少しずつ政策変更を繰り返すアルゴリ

推定し行列計算によって求めるアプローチと，確率的近ズムでは，変更前の政策における価値の推定値は，変更

似アルゴリズムと呼ばれる方法によって求めるアプロー

後の政策における価値の推定を行う際の有望な初期推定

チがある．我々はモデルを必要としない後者のアプロー値となるからである．

チを採用する．

上で述べた方法によって利得の分散を得ることの利点の一つとして，利得のリスクを考慮した政策の学習が可

2・3 TD アルゴリズムによる推定
確率的近似 (stochastic approximation, stochastic iterative) アルゴリズムの更新式は以下のように表される[Tsitsiklis 96].
v ← (1 − β)v + β(Hv + w)

(5)

能になることが挙げられる．そこで，次章において代表的な政策評価規範である variance penalized 規範に注目する．

3. Variance Penalized 強化学習法の提案

ただし，v は推定対象となっている変数のベクトル，β

特に金融工学の分野では，利得の期待値が最大で分散

はステップサイズパラメータ，w はノイズ要素，Hv はが大きな政策よりも，利得の期待値がほどほどで分散が推定量 v を用いた推定オペレータである．TD アルゴリ

小さな政策の方が好まれる場合が多い．無限回の意志決356

人工知能学会論文誌

16 巻 3 号 F（2001 年）

定を行うことが可能ならば前者の政策も合理的と考えら

q π (s, a) = E{(Rt − V π (s))2 |st = s, at = a, π}

れるが，もし短期間に連続して失敗すると倒産してしま(10)うといった状況下では後者の政策が好まれる．良く知られる規範としては，最悪ケースのみを考慮したミニマッ
クス規範が存在するが，多くの確率的なシステムにおいては悲観的な政策しか学習できない．
本章では，与えられたリスクレベルに応じた政策の価値を定義可能な variance penalized 政策評価規範 [Elon91, White 88] に着目し，新しい強化学習アルゴリズム
である VPD-GPI(Gradient-based Policy Iteration for
Variance Penalized Discounted MDPs) アルゴリズムを提案する.

ここで，π(s, a) は政策であり，状態 s において行動 a を選択する確率を表す。V π (s) =よび，v π (s) =般的な無限期間で割引のある場合を扱う．標準的なマル
コフ決定過程の政策規範と同様に初期状態分布ベクトルs0 を用い，学習の目的は以下の π を得ることとする．
max f π , f π = s 0 (Vπ − αvπ ).
π(8)

ここで，Vπ ，vπ はそれぞれ，前節で定義された利得の期待値，分散を表す V π (s)，v π (s) のベクトルを表す．
また，x はベクトル x の転置ベクトルを表す．α は正a π(s, a)qπ

a π(s, a)Qπ(s, a)，お(s, a) という関係が成り立つ．そして，政策 π の式 (8) における評価値を f π と表したとき，政策を保持するための近似パラメータ θ に対する f π の勾配に関して以下の定理が成立する．
［定理 3.1］（variance penalized 勾配式） 任意のマルコフ決定過程について，
∞ 

∂f π
=
Pr(st = s|s0 , π){γ t ∂Qπ (s, θ)
∂θ
t=0 s

− α(γ 2t ∂q π (s, θ) + 2e(s, t)∂Qπ (s, θ))},3・1 政策評価規範に基づくアプローチ
variance penalized 政策評価規範には，どの程度の期
間 (horizon) の報酬を考慮するか，報酬の割り引きを考慮するかによるバリエーションがあるが，我々は最も一





(11)
ただし，

∂Qπ (s, θ) =Qπ (s, a)a∂q π (s, θ) =q π (s, a)a∂π(s, a),∂θ∂π(s, a),∂θ(t = 0)
 0 
t
t+τ
π
e(s, t) =E{ τ =1 γ (rτ + γV (sτ )−V π (sτ −1 ))|st = s}(t = 0).

の実数パラメータであり，リスクと利益水準の好みを調《証明》 付録 C 参照.

節する．

ここで e(s, t) はスタート時刻 0 から時刻 t までのことが知られている [White 88]. すなわち，この評価関TD 誤差を割り引いて足し合わせたものであり，e(s, t) =E{γ 2t (rt + γV (st ) − V (st−1 )) + γe(st−1 , t − 1)|st = s}

数は非マルコフ決定問題を生じさせるので，最適な政策という関係が成立する．

この規範の下では定常な最適政策は一般に存在しないを求めようとすると非定常な政策空間を探索せねばならず，非常に小さな問題を除いて実現は不可能である．
そこで，我々は評価式 (8) の準最適解の一つを効率的に求めることを目指す．このような非マルコフ問題を解くための強化学習法として，部分観測マルコフ決定過
程 (POMDPs) における強化学習のアプローチがある[Jaakkola 95, Baird 98, Sutton 99]. それらの手法では，
まず政策評価関数の勾配を求め, その勾配方向に確率的

3・3 Policy Iteration 型学習アルゴリズム
式 (11) の勾配式により推定された Qπ (s, a) と q π (s, a)，
各時刻での状態占有確率 Pr(st = s| . . .) のサンプルおよび累積 TD 誤差のサンプルを用いて，政策評価関数式 (8)の政策保持パラメータ θ に対する勾配を近似的に求めることができる．ここではパラメータベクトルの更新量 ∆θ
を以下のように求める．

政策を少しずつ変更する．環境の部分観測性に因する非マルコフ性と政策評価規範に因する非マルコフ性の違いはあるものの，本章が対象とする問題においてもこのアプローチは有効である．この考えに基づき，我々は勾配法ベースの variance penalized 強化学習アルゴリズムを提案する．

∆θ = κk

∂f π
,
∂θ

(12)

ただし，κk は k 回目の政策更新のためのステップサイ
ズパラメータであり，k の増加と共に減少するという性質を持つ．
式 (6) と式 (7) の TD アルゴリズムによる推定，式 (11)に基づく勾配推定および式 (12) の更新式から，図 1 の

3・2 Variance Penalized 勾配式
まず，状態 s で行動 a を行い，その後政策 π に従って

このアルゴリズムを VPD-GPI と呼ぶ．VPD-GPI はモ

行動する場合の利得の期待値と分散を以下のように定義

デルの推定を行わない非逐次型の学習アルゴリズムであする．

る．政策評価ステップにおいて様々な関数近似システム

Qπ (s, a) = E{Rt |st = s, at = a, π},(9)Policy Iteration アルゴリズムを構成することができる．

と組み合わせることにより，大規模問題への適用も可能

報酬の分散を推定する TD アルゴリズムと Mean-Variance 強化学習法の提案(1) 初期化: すべての s, a について Q(s, a) = q(s, a) = 0 とし，
θ = θ0 , κ = κ0 , k = 0 とする．
(2) 政策評価: 全ての s, a について，政策 π(θ) 下での状態遷移に基づいて，式 (6) と (7) の TD アルゴリズムを用いて Q(s, a)と q(s, a) を推定する．
(3) 政策改善:∂fを推定する．具• 勾配定理を用いてすべての l に関して ∂θl

体的には，政策 π(θ) 下での状態遷移に基づいて，Q(s, a)と q(s, a)，占有確率 Pr(st = s| . . .) のサンプル，割り引
き累積 TD 誤差 (e(s, t)) のサンプルを用いる．

• θ ← θ + κk ∂f∂θ

という式に従い政策保持パラメータベクトル θ を更新する．
• もし k が十分大きい，あるいは，更新ベクトル ∆θ のノルムが十分に小さいならば，ループを出る．そうでないな
らばステップサイズ κ をスケジュールに基づき減少させ,
k を 1 増やし，(2) へ．

図 1 VPD-GPI アルゴリズム

357

である．
∞ 

∂f
≈
Pr(st = s){γ t ∂Qπ (s) − αγ 2t ∂q π (s)}
∂θ
t=0 s

(14)
ただし ∂Qπ (s), ∂q π (s) はそれぞれ ∂Qπ (s, θ), ∂q π (s, θ)を表す．分散が大きな環境においてはこのような近似を用いることも可能と考えられる．

• Lookup tables：今まで政策がパラメータベクトル
θ によって保持される一般的な場合を扱ってきたが，
ここでは特殊ケースとして，すべての状態 s ∈ S, 行
動 a ∈ A について独立のパラメータ p(s, a) (即ちlookup table) を保持する場合を考える．これらは，
a p(s, a) = 1 という制約条件を持つパラメータ変数と考えればよい．このとき，

と考えられる．VPD-GPI は variance penalized 規範下Q(s, a)aで効率的に準最適政策を探索する初めてのアルゴリズム



である．

q(s, a)a∂π(s, a)∝ Q(s, a) − V (s),∂p(s, a)∂π(s, a)∝ q(s, a) − v(s)∂p(s, a)という関係がそれぞれ成立するので，例えば上の近3・4 発 展 的 考 察
本節では，3.1. 節で提示した variance penalized 規範と提案した VPD-GPI に関して，工学的応用という観点から重要ないくつかのアルゴリズムについて考察する．

• 決定的政策: variance penalized 規範を用いた場合
でも，前節のように確率的政策を用いず，単に以下の決定的政策 µ(s) を選択することもできる．

µ(s) = arg max(Qπ (s, a) − αq π (s, a)) ∀s ∈ S
a(13)

似勾配式は以下の式になる．
∞ 

∂f
≈
Pr(st = s){γ t (Q(s, a) − V (s))∂p(s, a)t=0 s−αγ 2t (q(s, a) − v(s))}(15)

この式から，ある状態 s の行動の中で V π (s) よりも大きな Qπ (s, a) をもつ行動の確率を増やす要求とv π (s) よりも大きな q π (s, a) をもつ行動の確率を減らす要求が α によって足し合わされていることが分かる．

関数近似を用いるような大規模な問題では，政策を少しずつ変更せず最善の評価の行動のみを選ぶ政策は，

4. 実

験

学習速度の面で有効と考えられる．ただし，variancepenalized 規範下ではマルコフ的政策は最適という保証はないことおよび学習により政策の質が劇的に変化するため，場合によっては推定値が不安定になることに留意する必要がある．

• 勾配式の近似：前節で導出した勾配定理には，e(s, t)という TD エラーを割り引いて足し合わせた項が含まれていた．TD エラーの和は現在の状態 s に遷移

3 章において利得のリスクを考慮した variance penalized 政策評価規範を示し，その評価規範に基づいた効率的な学習アルゴリズムを提案した. 本章では，提案した学
習アルゴリズムを単純な機械メンテナンス問題 [Mahadevan 97] に適用し，理論値と比較することにより提案したアルゴリズムの正しさを示す．また，variance penalized
規範の妥当性と提案アルゴリズムの有効性を示す．

する以前のエピソードにおいて，平均よりも良い状
態遷移が連続して起これば大きな正の値になり，逆4・1 機 械 整 備 問 題に平均よりも悪い状態遷移が連続して起これば大き

政策学習の対象となるシステムは図 2-(a) の機械整備な負の値になる．もし多くの状態において平均より問題である. このシステムは，3 状態 (0:正常, 1:不調, 2:

も良い状態遷移と悪い状態遷移がエピソード中に同

故障)，2 行動 (0:使用, 1:整備)，3 種類の報酬 (機械を整程度に起こると仮定すると，e(s, t) の値は q π (s, a)

備するコスト，機械を使用する利益，故障した機械を修と比較して十分小さいと期待できる．すると近似勾理するコスト) のマルコフ決定過程としてモデル化でき配式は以下の式になる．e(s, t) の推定には多くのサる．ただし，故障状態 (状態 2) では整備 (修理) 以外のンプルが必要となるのでこのアルゴリズムは効率的

行動選択の余地はないため，実際には最適な 2 次元政策

358

16 巻 3 号 F（2001 年）

人工知能学会論文誌
ππ1.damaged

0.normal

V (0)

15

200
150

10

100

5

50

0

2.broken

1-5
action:reward:0.use,
maint. = -1,
1.maint. use
= 5,

0
1

-10
0

0

repair = -25.

Pr(a=0|s=0)

(a)
図 2

v (0)

Pr(a=0|s=1)

Pr(a=0|s=1)
1

Pr(a=0|s=0)

0

(b)

1

0

(c)

(a) 機械整備問題の状態遷移図, 初期状態における利得の期待値 (b) と分散 (c)(a)

Reward

(d)

5
-1
1

-25

0

100

200

Time

200

Time

RewardPr(a=0|s=1)

(b)
5
-1

-25

100

(c)

Reward

0

5
-1

-25
0

(b) Q-learning
Min-max(ergodic)
Variance penalized( α<0.02)(c)Variance penalized(0.08<α <0.16)(a) Min-max(non-ergodic)
Variance penalized(0.26< α)
α
00

100

200

Time

Pr(a=0|s=0)1

図 3 代表的政策下 (a:整整-政策，b:使使-政策, c:使整-政策) の報酬のスナップショット と様々な α における最適政策

パラメータ p(0) = Pr(使用 | 正常)(正常状態における使分散が非常に高いが故障の確率も大きい．一方，(c) の使用行動の選択確率)，および，p(1) = Pr(使用 | 不調)(不整-政策は中間的な報酬水準と，故障の確率をとる．

調状態における使用行動の選択確率) を求める問題とな

報酬の最悪値のみ状態価値として保持し，最悪値を最大る．このシステムの状態遷移関数と報酬関数を付録.D に示す値に設定し，割り引き係数 γ を 0.8 に，正常状態を化する政策を学習するミニマックス強化学習 [Heger 94]
では，整備行動を選ぶと必ず修理が可能な環境 (即ち非エ唯一の初期状態とすると，各政策に対する初期状態の期

ルゴード的環境) では常に修理をする (a) を学習する。し待価値と分散価値 (V (0),v(0)) の値は，図 2-(b),(c) の 3

かし，少しでも失敗の可能性がある環境 (エルゴード的環次元グラフで表示される．図の x-y 平面は政策を表し，z境) では逆に全く修理をしない政策 (b) を学習する。代表

軸はそれぞれ状態 0 における利得の期待値と分散を，x-y

的な Q-learning は任意の γ ∈ [0, 1) において政策政策を

平面上の点線はそれぞれ状態 0 における利得の期待値と学習する．割り引き係数 γ によって，時間軸方向への利分散の等高線を表す。

得のリスクに関する嗜好を反映させることができること

図 2 によると，例えば p(0) = p(1) = 1.0 (以下，使使-は知られているが，各時刻での利得のばらつきは考慮さ政策と呼ぶ）などの利得の期待値が高い政策は利得の分れない．一方，variance penalized 規範を用いると，適散も高く，例えば p(0) = p(1) = 0.0 (以下，整整-政策と切なリスク嗜好パラメータ α のもとで，(a) から (c) の政呼ぶ）などの利得の分散が低い政策は利得の期待値も低策を学習する。図 3-(d) に α を変化させた時の最適政策

くなっている．これは利得の期待値を大きくしたいといの変化を示す．この図から，α の値によっては確率的政策

う要請と利得の分散を小さくしたいという要請の間のトが最善となる場合もあり得る (例えば，α = 0.20 の場合

レードオフが存在することを意味する．この問題は単純な問題であるが，利得のリスクを考慮した学習法についp(0) = 0.75, p(1) = 0.0 付近が最善となる). よって，この問題においては確率的政策空間を対象とする VPD-GPIて調べる目的には適している．

のアプローチは有効と考えられる．

4・2 各種規範下での政策の挙動

4・3 利得の分散推定

図 3-(a),(b),(c) は 3 種類の代表的な決定的政策におけ2.3 節で提案した TD アルゴリズムを用いて，4.1 節でる報酬の 250 時刻分のスナップショットである. (a) の述べた機械整備システムにおける利得の期待値と分散を

整整-政策は報酬の分散は非常に低く故障の確率が小さい

推定する．ここで政策を固定しなければならないが，最が，全く正の報酬は得られない．(b) の使使-政策は報酬も分散が大きくなる使使-政策を選択した．ステップサイ

報酬の分散を推定する TD アルゴリズムと Mean-Variance 強化学習法の提案

300

state1, variance:50%noise (287)250

state1, variance:5%noise (271)359

における各政策の評価理論値である．図の x-y 平面は政策を表し，z 軸は式 ((8)) の政策評価関数 f π の値を表している。また，x-y 平面上の点線は f π の等高線を表す。
上下の図を比較することにより，政策の学習が勾配方

Estimates

向に適切に行われていることが確認された．また，評価200

state0, variance:50%noise (180)150

state0, variance:5%noise (168)値の勾配が急でない高台部分では政策が安定しないことも観察されている．これを避けるためには，慣性項を導入するなどより高度なパラメータ変更が必要と考えられる．
これらの結果から，提案した利得の期待値と分散を推定する TD アルゴリズムおよび VPD-GPI の妥当性と有100効性が示されたといえる．
50
state0, mean (11)
0

図 4

0

1000

state1, mean (7)

2000
3000
Trajectories

4000

5. お わ り に
5000

利得の統計量の TD アルゴリズムによる推定結果

本論文では，マルコフ決定過程における利得の確率分
布を得ることは有用であるという考えのもとに，利得の分散を効率的に得る方法を提案した．利得の分散に関す
るベルマン方程式を拡張し，分散のための TD アルゴリ

ズパラメータは全ての状態について，期待値，分散ともズムの収束性を証明した．本論文で扱った利得は無限期に以下の式 [Boyan 99] で計算した．

間の総割り引き報酬という最も一般的な設定である．まn0 + 1βn = β0n0 + nn = 1, 2, . . .

(16)た，利得の平均と分散を明示的に利用する方法として，プサイズを，β0 は初期ステップサイズ (実際には 0.01 にリスクを考慮した政策に関する評価規範である variancepenalized (variance penalised) 規範に基づく新しい強化学習アルゴリズム VPD-GPI を提案した．VPD-GPI

設定) を，n0 はステップサイズ減少用パラメータ (実際は政策の評価と政策の改善のフェーズを繰り返すことにには 1000 に設定) を表しており，収束定理の条件を満た

より，確率的政策空間の準最適解を学習する，この学習している．直接報酬にかかるノイズに関しては，各報酬

アルゴリズムは variance penalized 規範に基づく初めての絶対値の 5%と 50%の 2 種類について調べた．図 4 はの効率的なアルゴリズムである．機械整備問題において，その結果であり，提案した TD アルゴリズムによって理提案した TD アルゴリズムと VPD-GPI の学習結果と理論値 (() の中が理論値) とほぼ同じ推定値が得られている論値と比較することで有効性を示した．

ここで，βn は n エピソード (trajectory) 目のステッことが確認された. なお，数値は 10 試行の平均値である．

このアルゴリズムを関数近似と組み合わせることにより大規模問題において利得の平均と分散を推定し，リス

4・4 VPD-GPI の学習結果
図 1 に示した VPD-GPI をこの機械整備問題に適用した．各状態 s，各行動 a について利得の期待値 Q(s, a)，利得の分散 q(s, a) および政策 π(s, a) を保持しなければクを考慮した政策を学習することが可能になると期待でならないが，この問題は状態数が少ないことと，関数近

題や，思考ゲームなど様々な場面で利用できると考えら似による準最適政策への収束を避ける目的で，独立なパれる．

ラメータ (lookup table) を用いた．そして，k 回目の政策更新時における政策パラメータ更新用ステップサイズ
kパラメータは κk = 0.02(0.99) という値を用いた. また，きる．推定された利得の分散は，本論文で扱ったリスクを考慮した政策の学習の他にも強化学習でしばしば課題となる exploration と exploitation のトレードオフの問上で述べた新しい意志決定の枠組を提供するのに加え，本論文の理論を部分観測マルコフ決定過程 (POMDPs)
やセミマルコフ決定過程 (SMDPs) に拡張すること，関政策更新回数の最大値を 100 回とした．図 5-上は学習

数近似と組み合わせた際の性質について調べることが今結果である．α = 0.0, 0.1, 0.2, 0.3 のそれぞれの場合につ後の課題である．

いて，様々な初期政策から学習を行った場合の政策の変化である．図の点線の違いは初期政策の違いを表してい♦ 参 考 文 献 ♦る。この結果から，α を変化させることにより，使使-政策(α = 0.0, Q-learning の最適政策)，使整-政策 (α = 0.1)，
確率的政策 (α = 0.2)，整整-政策 (α = 0.3, ミニマック
ス学習の最適政策) が最終的に得られていることが確認できる．また，図 5-下はそれぞれ，上の図と対応した α[Baird 98] Baird, L., Moore, A.: Gradient descent for general reinforcement learning., Advances in Neural Information Processing Systems 11, (1998).
[Boyan 99] Boyan, J. A.: Least-Squares Temporal Diﬀerence
Learning., Proceedings of the 16th International Conference
on Machine Learning, pp.49-56, (1999).

360

人工知能学会論文誌(a) α =0.0(b)α =0.1(c) α =0.2

0Pr(a=0|s=0)10Pr(a=0|s=1)

Pr(a=0|s=1)

Pr(a=0|s=1)0(d) α =0.3
11

1
Pr(a=0|s=1)

1

0

Pr(a=0|s=0)

1

0

16 巻 3 号 F（2001 年）

0Pr(a=0|s=0)

1

0

0

Pr(a=0|s=0)

1

0

15
1
0
-1
-2
-3
-4
-5
-6
-7

10
5
0
-5

-5
-10
-15
-20
-25

-5
-10
-15
-20
-25
-30
-35
-40

-10
z
y

x:Pr(a=0|s=0), y:Pr(a=0|s=1),z:f π,:optimal policyx

図 5

様々な α における政策の変化 (上) と理論値 (下)[Brown 98] Brown, T. X., Tong, H., Singh, S.: Optimizing admission control while ensuring quality of service inmultimedia networks via reinforcement learning., Advancesin Neural Information Processing Systems 11, pp.982-988,(1998).
[Crites 96] Crites, R. H., Barto, A. G.: Improving elevator performance using reinforcement learning, Advances in
Neural Information Processing Systems 9, pp.1017-1024,(1996).
[Dearden 98] Dearden, R., Friedman, N., Russell, S.:
Bayesian q-learning, In Proceedings of the 15th National
Conference on Artiﬁcial Intelligence, pp.761-768, (1998).
[Elon 91] Elon, E., Gruber, M.: Modern Portfolio Theory and Investment Analysis., John Wiley and Sons, Inc,
(1991).
[Fernandez 95] Fernandez, E., Marcus, M. I.: Non-standard
optimality criteria for stochastic control problems, Technical Reports on ISR-TR, pp.95-101, (1995).
[Heger 94] Heger, M.: Consideration of risk and reinforcement learning. Proceedings of the 11th International Conference on Machine Learning, pp.105-111, (1994).
[Jaakkola 95] Jaakkola, T., Singh, S. P., Jordan, M.I.:
Reinforcement learning algorithm for partially observable
Markov decision problems., NIPS ’95, pp.345-352, (1995).
[Kadota 98] Kadota, Y., Kurano, M., Yasuda, M.: On thegeneral utility of diccounted Markov decision processes,
IFORS96 Pepar No.115, vol.22, (1998).
[McCallum 95] McCallum, R.A.: Instance-based utile distinctions for reinforcement learning with hidden state, Proceedings of the 12th International Conference on Machine
Learning, pp.387-395, (1995).
[Mahadevan 96] Mahadevan, S.: Average reward reinforcement learning: Fundations, algorithms, and empirical results. Machine Learning, vol.22, pp.159-196, (1996).
[Mahadevan 97] Mahadevan, S., Marchalleck, N., Das, T.K.,
Gosavi, A.: Self-Improving Factory Simulation using
Continuous-time Average-Reward Reinforcement Learning.
Proceedings of the 14th International Conference on Machine Learning, pp.202-210, (1997).
[Marcus 97] Marcus, S. I., Fernandez, E., Hernandez, D.,
Coraluppi, S., Fard, P.: Risk Sensitive Markov Decision
Processes. Systems and Control in the Twenty-First Century, Boston Birkhauser, pp.263-279, (1997).
[Munos 99] Munos, R., Moore, A.: Variable resolution dis-cretization for high-accuracy solutions of optimal control
problems. 16th International Joint Conference on Artiﬁcial
Intelligence, pp.1348-1355, (1999).
[Neuneier 97] Neuneier, R.: Enhancing Q-Learning for Optimal Asset Allocation., Advances in Neural Information Processing Systems 10, pp.936-942, (1997).
[Neuneier 98] Neuneier, R., Mihatsch, O.: Risk Sensitive
Reinforcement Learning., Advances in Neural Information
Processing Systems 11, pp.1031-1037, (1998).
[Schwartz 93] Schwartz, A.:
A reinforcement learning
method for maximizing undiscounted rewards ., Proceedingsof the 10th International Conference on Machine Learning,pp.298-305, (1993).
[Singh 97] Singh, S., Bertsekas, D.: Reinforcement learning for dynamic channel allocation in cellular telephon systems, Advances in Neural Information Processing Systems
10, pp.974-980.
[Sutton 88] Sutton, R. S.: Learning to predict by the methods of temporal diﬀerences., Machine Learning 3, pp.9-44(1998).
[Sutton 98] Sutton, R. S., Barto, A. G.: Reinforcement
learning: An Introduction., MIT Press (1998).
[Sutton 99] Sutton, R. S., McAllester, D., Singh, S., Mansour, Y.: Policy gradient methods for reinforcement learning with function approximation., Advances in Neural Information Processing Systems 12,(1999).
[Tsitsiklis 96] Tsitsiklis, J. N.: Neuro-Dynamic Programming., Athena Scientiﬁc (1996).
[Watkins 89] Watkins, C.: Learning from Delayed Rewards.,
PhD thesis, King’s College, England (1989).
[White 88] White, D. J.: Mean, variance, and probabilistic
criteria in ﬁnite Markov decision processes: A review. Journal of Optimization Theory and Applicatoins, vol.56(1),pp.1-29, (1988).
[Zhang 96] Zhang, W., Dietterich, T. G.: High performance job-shop scheduling with a time-delay TD(λ) network., Advances in Neural Information Processing Systems
9, pp.1024-1030.

〔担当委員：櫻井彰人〕

2000 年 6 月 28 日 受理

報酬の分散を推定する TD アルゴリズムと Mean-Variance 強化学習法の提案

♦ 付

361

録 ♦

(1) H は weighted maximum ノルムに関して縮小写像である．
(2) 全ての i, t について E{wt (i)|Ft } = 0 である (推定ノイズ項の平均が 0)．
A. 利得の分散に関する Bellman 方程式(3) 全ての i, t, 任意のノルム ・ について E{wt2 (i)|Ft } ≤ A +状態 s において行動 a を選択し状態 s に遷移したのちに，政策B  vt 2 である (推定ノイズ項の分散が有界)．
π に従い行動選択する時の利得 Rt の分散は以下のように求まる．
(4) 全ての i, t についてバイアス項の絶対値が 0 に概収束する正の乱数系列 θt よりも大きくならない (バイアス項が 0 に収束)．
E{(Rt − V π (s))2 |st = s, at = a, st+1 = s , π}
ただし，Ft は時刻 t までの状態遷移の履歴を表す．
∞
まず，詳細は省略するが，(1) に関しては利得の期待値を推定= E{(rt+1 + γ
γ k rt+k+1 − V π (s))2 | . . .}する通常の TD アルゴリズムと同様の方法で示すことができる
k=1([Tsitsiklis 96] の p.249 参照)．(2) に関しては wt (i) の定義式と，∞

E{n} = 0 から明らかである．
k
π
π 
π  2
= E{(rt+1 + γ
γ rt+k+2 − V (s) + γV (s ) − γV (s )) | . . .}(3) に関しては，
k=0


2
2
 2
E[wt2 |Ft ] ≤ E[{(Rπss + n + γV∞ (s ) − V∞ (s)) + γ vt (s )} ]= E{(rt+1 + γV π (s ) − V π (s))2 | . . .}

∞

+2γE{(≤ (((1 + γ)K1 + K2 + K3 )2 + γ 2 max |vt |)2

γ k rt+k+2 − V π (s ))(rt+1 + γV π (s ) − V π (s))| . . .}s

≤ 2γ 4  vt 2 +2((1 + γ)K1 + K2 + K3 )4

k=0
∞


ただし ・ は maximum ノルム，K1 = maxs |V∞ (s)|, K2 =|, K3 は直接ノイズの上限である．よって (3) は成立
maxss |Rπ
ss
k=0
する．
π 
π
2
= E{(Ra
さらに，Gt = maxi |Vt − V∞ | とすると，全ての i について Vt (i)ss + w + γV (s ) − V (s)) | . . .}∞はV∞ (i) に概収束するので，Gt は 0 に概収束する正の乱数系列
+2γE{(
γ k rt+k+2 − V π (s ))|}E{(rt+1 + γV π (s ) − V π (s))|} である．ここで，+γ 2 E{(γ k rt+k+2 − V π (s ))2 | . . .}

k=0
∞


+γ E{(
2|ut (i)| ≤ (1 + γ)Gt {(1 + γ)Gt + 4K1 + 2K2 }kπγ rt+k+2 − V (s )) | . . .}2という関係が成立するので，(4) が成立する．
以上から，もしステップサイズが定理中で述べた条件を満たすならば，全ての i について vt (i) は vπ (i) に概収束する．
Q.E.D.

k=0
π 
π
2
2 π 
= E{(Rass + w + γV (s ) − V (s)) | . . .} + γ v (s )
π 
π
2
= (Ra
ss + γV (s ) − V (s))
π 
π
2
2 π 
+2(Ra
ss + γV (s ) − V (s))E{w| . . .} + E{w | . . .} + γ v (s )
π 
π
2
a
2 π 
= (Ra
ss + γV (s ) − V (s)) + rss + γ v (s )ここで，w は直接報酬に加わるノイズであり，環境モデルの定義より，
a である．このような関係がすべての s, s ∈ S, a ∈ A
平均 0，分散 rss
について成立するので，以下の関係が成り立つ．

C. Variance Penalized 政策勾配定理
全ての s ∈ S, a ∈ A について政策 π(s, a) が ∆π(s, a) だけ変化したとする．この時，平均価値に関するベルマン方程式を用いると，
状態 s の平均価値の変化量 ∆V (s) は以下の条件を満たす．

∆V (s) =π(s, a)

a
π
2

Pss
 E{(Rt − V (s)) |st = s, at = a, st+1 = s , π}= ∆Q(s) + γ

s

a





∆π(s, a)Qπ (s, a) + γavπ (s) = E{(Rt − V π (s))2 |st = s, π}π(s, a)

a



a
a
π 
π
2
a
2 π 
Pss
 {(Rss + γV (s ) − V (s)) + rss + γ v (s )}.

s

ここで，∆Q(s) =∆v(s) =


a



+ 2γ

vt+1 (i) = (1 − εt )vt (i) + εt ((Ht vt )(i) + wt (i) + ut (i)), ∀i ∈ S,

= ∆q(s) + γ(Ht vt )(i) =



π
2
π
2
Pij
{(Rπ
ij + γV∞ (j) − V∞ (i)) + rij + γ vt (j)},j∈S22
wt (i) = (Rπij + n + γV∞ (j) − V∞ (i)) + γ vt (j) − (Ht vt )(i),ut (i)p= {γ(Vt (j) − V∞ (j)) − (Vt (i) − V∞ (i))}{γ(Vt (j) − V∞ (j))−(Vt (i) − V∞ (i)) + 2(Rπij + γV∞ (j) − V∞ (s))}.
であり，n は直接報酬にかかるノイズを表す．また，wt (i) は推定
ノイズ項を，ut (i) はバイアス項を表す．ここで，もしこのアルゴリズムが以下の 4 つの性質を満たしステップサイズパラメータが定理のなかで述べた条件を満たすならば，[Tsitsiklis 96] における(Prop.4.5 の) 収束定理を適用ることができ，推定値は真の値に概
収束する．



a

Pss
 ∆V (s )

s

a
π

Pss
 ∆V (s )

(C.1)

s
a

∆π(s, a)Qπ (s, a) である．同様に分散価∆π(s, a)qπ (s, a) + γ 2

全ての i ∈ S について，V (i) が式 (6) の TD アルゴリズによって推定されると仮定する．このとき，式 (7) の TD アルゴリズム
は以下のように変換できる．

ただし，

π(s, a)値に関するベルマン方程式を用いると，状態 s の分散価値の変化
量 ∆v(s) は以下の条件を満たす．

Q.E.D

B. TD アルゴリズムの収束





2

π(s, a)

a

+ 2γ

2


s

2







π(s, a)

a



a

Pss
 ∆v(s )

s

a
a
π 
π

Pss
 (Rss + γV (s ) − V (s))∆V (s )

s
π

Pss
 ∆v(s )

s
π
π
π 
π

Pss
 (Rss + γV (s ) − V (s))∆V (s )

(C.2)



q π (s, a)∆π(s, a) である．ここで，式 (C.1),(C.2)
を全ての s について集め，行列表現を用いると，
ただし，∆q(s) =a∆V = ∆Q + γPπ ∆V∆v = ∆q + γ 2 Pπ ∆v + 2γ 2 E∆V
ここで，∆Q，∆q は i 番目の要素がそれぞれ ∆Q(i), ∆q(i) にπ (Rπ +
相当する |S| 次元ベクトルであり，E は (i, j) 要素が，Pij
ij

γV π (j) − V π (i)) に相当する |S| × |S| 行列である．

362

16 巻 3 号 F（2001 年）

人工知能学会論文誌

このとき，評価関数 f の変化量 ∆f を ∆f = ∆fV − α∆fv と分解すると，以下の関係が成立する．
∆fV = s 0 (I − γPπ )−1 ∆Q,∆fv = s 0 (I − γ 2 Pπ )−1 (∆q + 2γ 2 E(I − γPπ )−1 ∆Q)= s 0 (I − γ 2 Pπ )−1 ∆q
2 

π −1

+ 2γ s 0 (I − γ P )
2

(C.3)
π −1

E(I − γP )∆Q (C.4)

ここで更に ∆fv を式 (C.3) と式 (C.4) に分解し，∆fv = ∆fv1 +∆fv2 と表す．そして逆行列を (I − αP)−1 = (I + αP + α2 P + · · ·)という関係を使って展開すると以下の関係を得る．
∆fV = s 0 (I + γP + γ 2 P2 + · · ·)∆Q,

∆fv1 = s 0 (I + γ 2 P + γ 4 P2 + · · ·)∆q


∆fv2 = 2γ 2 s 0 (I + γ 2 P + γ 4 P2 + · · ·)E(I + γP + γ 2 P2 + · · ·)∆Q

ここで s 0 Pn−1 は，i 番目の要素が Pr(st+n = i|s 0 , π) を意
味する |S| 次元ベクトルの転置ベクトルなので，∆fV と ∆fv1 に関しては以下の関係が成立する．

∆fV =

∞


t=0

∆fv1 =

D. 機械整備問題のパラメータ
我々が用いた状態遷移確率は以下の通りである．ただし，T は状
態遷移関数，RM ean は報酬の期待値関数，RV ar は報酬の分散関数である．
ここで，例えば状態 1 (不調) において整備行動を選択した場合に状態 0 (正常) に遷移する確率は 50%となる．本論文の設定では利得の期待値と分散のトレードオフを強調するため，通常の直観よりも整備行動の魅力を下げた設定にしている．
また，下の a は 0 に近い小さな正の実数を，b は 1 に近い 1 未満の実数を表している．これは，状態遷移のエルゴード性を維持しつ
つ，故障状態を終端状態ととらえることを可能にするためである．
即ち，状態 2 に遷移してしまうと，状態 2 へのセルフループを長い期間繰り返す．その結果，何の報酬も入らない状態遷移が長く続くことになるので，状態 2 の報酬の期待値と分散がともに 0 に近くなる．よって，状態 2 を近似的に終端状態と見なすことができる．
直接報酬のノイズに関しては一様分布を仮定し，パラメータ k によって特徴づけた．5%ノイズの場合は k = 0.05 を，50%ノイズの場合は k = 0.5 を代入すればよい．


T (使) =Pr(st = s|s0 , π)γ t ∆Q(s)



s

∞


t=0

T (整) =Pr(st = s|s0 , π)γ 2t ∆q(s)

0.95
0.05
0.00

0.50
0.45
0.05

a
0.0
b

5.0
5.0
0.0

0.0
5.0
−25.0



RM ean(使) =



∆fv2
2γ 2






= s 0 E∆Q + γs 0 EP∆Q + γ 2 s 0 EP2 ∆Q + · · ·+γ s 0 P E∆Q + · · ·∆fv2 = 2t=1

8.33k28.33k2208.33k2

0.0
0.0
0.0

RV ar(整) =0.33k20.33k20.0

0.33k20.33k2208.33k2

0.0
0.0
0.0

著

介


RV ar(使) =Pr(st = s|s0 , π)e(s, t)∆Q(s)

8.33k28.33k20.0

RM ean(整) =これをまとめると，
∞



0.0
0.0
0.0

−1.0
−1.0
−25.0



2



−1.0
−1.0
0.0

+γ 2 s 0 PE∆Q + γ 3 s 0 PEP∆Q + · · ·
4 



0.0
0.9
0.1

s

また ∆fv2 に関しては，以下のように展開できる．

a
0.0
b

0.1
0.9
0.0

s

0.0
0.0
0.0




となる．ただし，te(s, t) = E{

γ

τ +t

τ =1

最後に，∆π(s, a) =ππ(rt + γV (sτ ) − V (sτ −1 ))|st = s, s0 , π}.

 ∂π(s,a)l∂θl∆θl であるので，以下の勾配定理が導かれる．

∂π(s, a)∂fV
Pr(st = s|s0 , π)γ tQπ (s, a)
=
,
∂θ
∂θ
∞

t=0

s

a



∂π(s, a)∂fv1
Pr(st = s|s0 , π)γ 2tq π (s, a)
=
,
∂θ
∂θ
∞

t=0

s

a



∂π(s, a)∂fv2
Pr(st = s|s0 , π)e(s, t)
Qπ (s, a)
=2
.
∂θ
∂θ
∞

t=1

s

a

者 紹
佐藤

誠（正会員）

1996 年 3 月 東京工業大学工学部制御システム工学科卒
業．1998 年 3 月 同大学総合理工学研究科知能システム科学専攻修士課程修了．同年 4 月株式会社東芝入社．主として，強化学習，ニューラルネットワーク，データマイニ
ングに関する研究に従事．情報処理学会会員．

木村元（正会員）

1992 年東京工業大学工学部制御工学科卒業．1994 年同大学大学院総合理工学研究科知能科学専攻修士課程修了.
1997 年同大学大学院博士課程修了，同年 4 月日本学術振興会 PD 研究員，1998 年 4 月，東京工業大学大学院総合理工学研究科助手，現在に至る．人工知能，特に強化学
習に関する研究に従事．計測自動制御学会，日本ロボット学会各会員．

Q.E.D.
小林 重信（正会員）
1974 年東京工業大学大学院博士課程経営工学専攻修了．
同年 4 月，同大学工学部制御工学科助手．1981 年 8 月，
同大学大学院総合理工学研究科助教授．1990 年 8 月，教授．現在に至る．問題解決と推論制御，知識獲得と学習などの研究に従事．計測自動制御学会，情報処理学会各会員．