slides - Latent Dynamics 研究会

第2回 Latent Dynamics Workshop＠東京大学
Workshop＠東京大学
2011.06.22
潜在ダイナミクス
潜在ダイナミクスにおける
ダイナミクスにおける
リスク考慮型意思決定
リスク考慮型意思決定
IBM東京基礎研究所
東京基礎研究所
森村 哲郎
Joint work with
杉山 将
東京工業大学
鹿島 久嗣
八谷 大岳
田中 利幸
東京大学
東京工業大学
京都大学
© 2011 IBM Corporation
やりたいこと：データに基づく意思決定（支援）
未知の
未知の環境との
環境との相互作用
との相互作用のもたらす
相互作用のもたらすダイナミクス
のもたらすダイナミクスを
ダイナミクスを解析し
解析し、
意思決定を
意思決定を最適化する
最適化する
– 「何をすべきか（
）」 を与えて、
をすべきか（what）」
データから 「どのように実現
）」 を学習してほしい
どのように実現するか
実現するか（
するか（how to）」
その基盤
その基盤となる
基盤となる理論的枠組
となる理論的枠組に
理論的枠組に強化学習がある
強化学習がある
2
© 2011 IBM Corporation
といっても、「データに基づく意思決定」は多岐の研究領域に
わたります
強化学習だけでは
強化学習だけでは完結
だけでは完結しない
完結しない
意思決定理論
確率過程、数理ファイナンス
強化学習
(機械学習、最適化)
• 従来、研究しやすい部分を
切り出している
• そのためか応用例が多くない
• （本日はこの部分です）
統計、データ解析、システム同定
実データ
に近 い
3
実験計画、能動学習
データ、センサー設置、データ取得
© 2011 IBM Corporation
[ご参考・少し異なる解釈] 強化学習は最も一般的な学習パラ
ダイム
(copied from Langford MLSS2006)
4
© 2011 IBM Corporation
アウトライン
強化学習の
強化学習の概要
リスク考慮型強化学習
リスク考慮型強化学習
5
© 2011 IBM Corporation
強化学習の概要
強化学習の位置づけ（機械学習の分類）
教師あり
トレーニングデータ：
教師あり学習
あり学習 [トレーニングデータ
トレーニングデータ：特徴値、
特徴値、教師ラベル ]
– クラス分類
– 回帰
強化学習 [トレーニングデータ：
トレーニングデータ：特徴値、
特徴値、報酬（
報酬（評価値）
評価値）]
（明示的な教師信号の代わりに、報酬を利用して学習）
– 強化学習問題:
強化学習問題: 状態遷移あり
状態遷移あり (MDPやPOMDP)
– バンディット問題： 行動に依存した状態遷移なし
教師なし
トレーニングデータ：
教師なし学習
なし学習 [トレーニングデータ
トレーニングデータ：特徴値のみ
特徴値のみ]
のみ
– クラスタリング
– 確率密度推定
6
© 2011 IBM Corporation
強化学習の概要
強化学習は相互作用から学習する
強化学習 (RL) は(人工
人工)生命
人工 生命のようなもの
生命のようなもの
環境
知覚
行動
報酬
Agent
–(実)時間軸に沿って，
反復的に学習や意思決定を行う
–エージェントは環境に影響を及ぼす
–環境は確率的で未知
7
© 2011 IBM Corporation
強化学習の概要
将来の累積報酬（リターン）が最大になるように行動を選択
エージェントの
エージェントの人生は
人生は経験の
経験の並び
エージェントの一生
経験の単位
目的は
目的はリターン（
リターン（≒累積報酬）
累積報酬）を最大にする
最大にする方策
にする方策をみつけること
方策をみつけること
– 即時報酬の最大化を目指しているわけではない
• リターンの
リターンの定義:
定義
非減衰の累積報酬
時間減衰率
8
（もしくは平均報酬）
γ の累積報酬
© 2011 IBM Corporation
強化学習の概要
強化学習（RL）の簡単な例題：
近視眼的な方策が最悪な方策になる例
キャンペーン・
キャンペーン・プランニング問題
プランニング問題
– キャンペーンを打つと、短期売上げは
短期売上げは上
げは上がるが、
がるが キャンペーン後の
カスタマーの
カスタマーの購買意欲は
購買意欲は下がる
• 観測 o : カスタマー購買意欲 (low, mid, high)
• 行動
: キャンペーンを実施
: 実施しない
• 報酬 r : 単期の売上げ
r=6
optimal
policy：
r=3
r=0
olow
low
worst policy：
9
omid
mid
r = -1
ohigh
high
r=2
r=1
時間遅れのある大
発見する
は時間遅れのある
れのある大
大きな報酬
きな報酬を
報酬を
を発見する
する
RLは
は
時間遅
れのある
きな
報酬
発見
© 2011 IBM Corporation
強化学習の概要
RLの実施例
従来、
従来、ロボット制御
ロボット制御や
制御やゲーム等
ゲーム等に使われてきた
–ロボティクス
• ナビゲーション、二足歩行、ロボカップ･サッカー、ジャグリング、…
–制御
Matsubara+ (2005)
• 工場プロセス制御、通信の流入制御、マルチメディアネットワーク
のリソース制御、ヘリコプター、エレベーター、…
–ゲーム
• バックギャモン、チェス、オセロ、テトリス、…
–オペレーションズ・リサーチ
Tesauro (1995)
• 倉庫管理、トランスポーテイション、スケジューリング、…
–その他
• 対話システム、ヘルスケア、生物モデリング、…
Cross channel
optimized marketing
Abe+ (2004)
10
© 2011 IBM Corporation
強化学習の概要
近年、現実の問題に適用され、新たな注目が集まっています
ビジネスデータ解析
が決定的役割
ビジネスデータ解析や
解析や自然言語処理などの
自然言語処理などの分野
などの分野で
分野でRLが
を果たす実問題
たす実問題が
実問題が次々に見出されている
見出されている
–Abeら（KDD’10）は税金取立てに応用し、
これによりNY州は3年間
年間で
万ドルもの
年間で100万
ドル
巨額の追加税収を得る見込み
• 行動選択に制約のある制約付
制約付き
制約付きRLを定式化
• KDD’10 best industry/government paper
＄ ＄＄
＄＄ ＄
＄
＄＄
Tax Collections Optimizer
–Branavanら（ACL’09）はPCインストラクションの読解にRLを利用して、
学習に必要な教師データ数の削減に成功
• ACL’09 best paper
Mapping “natural language instructions”
↓
“sequences of executable actions”
11
© 2011 IBM Corporation
強化学習の概要
強化学習法の分類
大きく２
きく２軸で分けられる
（直接）
直接）方策-探索型
方策 探索型
価値/方策
価値 方策-反復型
方策 反復型
モデル・
モデル・ベース型
ベース型
環境モデルを同定し、
その同定したモデルを
利用して意思決定を行う
- 価値関数が方策を規定
価値関数
- 方策パラメータが方策を規定
- 価値関数を学習することで、
価値関数
(暗に)方策が更新される
- 目的関数の勾配等で、(明に)方策
パラメータを更新
・動的計画 [Sutton & Barto ’98]
・線形計画
[Puterman’94, Ballo & Riano ‘06]
・R-Max
[Brafman & Tenneholz ‘03]
・LSTD/LSPI [Lagoudakis&Parr’03]
モデル・
モデル・フリー型
フリー型
環境の同定を経ずに、
方策を学習する
・Q-learning [Watkins ’89]
・RAINFORCE [Williams ‘92]
・Delayed Q-learning (with
PAC Analysis) [Strehl ‘09]
・Actor-Critic [Sutton & Barto ’98]
- （自然）方策勾配法 [Peters+‘03]
本日はここ
12
© 2011 IBM Corporation
アウトライン
強化学習の
強化学習の背景
リスク考慮型強化学習
リスク考慮型強化学習
13
© 2011 IBM Corporation
リスク考慮型強化学習
なぜリスク
なぜリスクを
リスクを考慮するのか
考慮するのか？
するのか？
期待値だけでは
期待値だけでは見
だけでは見えない大切
えない大切な
大切な情報がある
情報がある
– 背後にあるリスクの見積もりが不可能
– 従来の意思決定手法は、各選択肢のもたらす利得（損失）の期待値
をもとに行われてる
実問題や
実問題や状況に
状況に応じて、
じて、リスク嗜好性
リスク嗜好性は
嗜好性は異なる
–とにかく期待リターンを最大にしたい
14
⇒ risk-neutral
– 多少コストがかかっても、
大損失することだけは避けたい
⇒ risk-aversion
– 損するかもしれないが，
大儲けの大チャンスに賭けたい
⇒ risk-taking
(chance-discovery)
discovery
© 2011 IBM Corporation
リスク考慮型強化学習
分布がわかれば
分布がわかれば、
がわかれば、多種多様な
多種多様なリスク指標
リスク指標（
指標（情報）
情報）が手に入る
Mean: 25
0.1-VaR: 38
0.05
0
良い場合もあれば
悪い場合もある
0
20
40
Return
0.3 戦略Ｂ
戦略Ｂ
たまに大儲け
0.2
Mean: 25
0.1-VaR: 45
0.1
0
0
20
Return
40
Probability density
0.1
戦略Ａ
戦略Ａ
Probability density
Probability density
– リターンの
リターンの分布が
分布が求まれば、金融工学等でよく用いられる
まれば
Value-atRisk （VaR）等、様々なリスク指標を算出でき、リスク指標
リスク指標に
指標に基づいた
意思決定が
意思決定が可能
0.5 戦略
戦略Ｃ
Ｃ
0.4
結果が安定
0.3
Mean: 25
0.1-VaR: 27
0.2
0.1
0
0
20
Return
40
どれも期待値は一緒だわ…
でもリスクが小さいのは“C”ね!!
難点:
難点: リターンの
リターンの観測まで
観測まで時間遅
まで時間遅れがあるため
時間遅れがあるため、
れがあるため、
その分布推定
その分布推定は
分布推定は難しい。
しい。
15
© 2011 IBM Corporation
リスク考慮型強化学習
目的： 効率の
効率の良いリターン分布手法
リターン分布手法の
分布手法の確立
目次：
1. 二つのアプローチ
つのアプローチ
2. 分布Bellman方程式
方程式
分布
3. 分布Bellman方程式
方程式を
分布
方程式を用いたリターン
いたリターン分布推定
リターン分布推定
- パラメトリック法 [Morimura+ UAI2010]
- ノンパラメトリック法 [Morimura+ ICML2010]
- 実験
4. 推定リターン
推定リターン分布
リターン分布を
分布を用いたリスク
いたリスク考慮型意思決定
リスク考慮型意思決定
5. まとめ
16
© 2011 IBM Corporation
(リスク考慮型強化学習)
リスク考慮型強化学習) １．二つのアプローチ
リターン分布推定のためのアプローチ
価値関数（
価値関数（期待リターン
期待リターン）
リターン）推定の
推定の場合同様、
場合同様、二通りの
二通りのアプローチ
りのアプローチがあります
アプローチがあります
シミュレーション・
シミュレーション・アプローチ
（モンテカルロ法
モンテカルロ法）
解析的アプローチ
解析的アプローチ
– リターン分布についての再帰式を
導出して、その再帰式を解くこと
でリターン分布を推定
–直接的な方法だが、リターンまで
観測に（無限の）時間遅れがある
ため非効率
非効率
Monte
Carlo
2. Counting
st+1
st+2
st+3
η = 4.2
4.7
5.5
1.9
.
.
.
Our approach Solving recursive formula
for return distribution
st+1
1. MC sampling
st
17
st
© 2011 IBM Corporation
(リスク考慮型強化学習)
リスク考慮型強化学習) １．二つのアプローチ
用語・関数の定義
マルコフ決定過程
マルコフ決定過程;
決定過程
MDP
マルコフ連鎖
マルコフ連鎖;
連鎖
– （確率的）方策:
– 状態： s ∈ S
– 行動： a ∈ A
– 報酬： r ∈ R
リターンに
リターンに関する統計量
する統計量
（未知）
– 状態遷移確率（
未知）:
– リターン （γ ： 割引率）
– 報酬観測確率（
（未知）
未知）：
– (条件付) リターン分布関数
リターン分布関数
行動：a
状態：s
エージェント
報酬：r
（ロス）
– 価値関数 （= 期待リターン）
： x の期待値
環境
18
推定したい
推定したい関数
したい関数
s+
© 2011 IBM Corporation
(リスク考慮型強化学習)
リスク考慮型強化学習)
（リスク考慮型強化学習）
目次：
1. 二つのアプローチ
2. 分布Bellman方程式
方程式
分布
3.分布Bellman方程式を用いたリターン分布推定
- パラメトリック法 [Morimura+ UAI2010]
- ノンパラメトリック法 [Morimura+ ICML2010]
- 実験
4.推定リターン分布を用いたリスク考慮型意思決定
5.まとめ
19
© 2011 IBM Corporation
(リスク考慮型強化学習)
方程式
リスク考慮型強化学習) 2．分布Bellman
．分布Bellman方程式
リターンに関する再帰式；ベルマン方程式
実は期待リターンに関してだけでなく、分布に関する再起式も簡単に導出できます
リターンの
リターンの再帰式：
再帰式：
η limT →∞
= r + γη+1
T
t=0
γ t r+t
期待リターン
方程式）：
期待リターンに
リターンに関する再帰式
する再帰式（
再帰式（Bellman方程式
方程式）： （∵ r⊥η+1|s+1 ）
V (s) E[η|s, π] = E[r + η +1 |s, π]
=
pT (s+1 |s, a)π(a|s)
rpr (r|s, a, s+1 )dr + γV (s+1 )
s+1 ∈S a∈A
r
リターン分布
方程式）：
リターン分布に
分布に関する再帰式
する再帰式 （分布Bellman方程式
分布
方程式）： （∵ r⊥η+1|s+1 ）
[中田&田中 2006]
20
© 2011 IBM Corporation
(リスク考慮型強化学習)
方程式
リスク考慮型強化学習) 2．分布Bellman
．分布Bellman方程式
分布Bellman方程式を用いたリターン分布推定
準備：
作用素
準備：分布Bellman作用素
分布
の定義
(＊)
– 分布Bellman方程式 ⇒
分布Bellman方程式
方程式を
分布
方程式を解くとは?
くとは
– ある累積分布関数 F(η|s) が
を満す時、 F(η|s) は分布Bellman方程式の解（=リターン分布関数
リターン分布推定は、
学習すること
21
と
が近くなるように
）
を
© 2011 IBM Corporation
(リスク考慮型強化学習)
方程式
リスク考慮型強化学習) 2．分布Bellman
．分布Bellman方程式
分布Bellman方程式の解の一意性
動的計画法（DP）によるリターン分布推定は常に真の分布関数に収束する
DPにより
により、
方程式を
により、分布Bellman方程式
分布
方程式を解く; dBellman-DP
– 各タイムステップ k で、推定リターン分布関数
を更新
任意の
任意の初期分布から
初期分布から、
から、常に真のリターン分布関数に収束
＊
証明:
特性関数化して証明される
証明 分布Bellman方程式を特性関数化
特性関数化
22
© 2011 IBM Corporation
(リスク考慮型強化学習)
方程式
リスク考慮型強化学習) 2．分布Bellman
．分布Bellman方程式
モーメント推定量に関する収束率
準備
23
⇒ 低次の
低次のモーメント推定誤差
モーメント推定誤差が
推定誤差が大きいほど、
きいほど、高次の
高次のモーメント推定
モーメント推定は
推定は非効率に
非効率に
© 2011 IBM Corporation
(リスク考慮型強化学習)
方程式
リスク考慮型強化学習) 2．分布Bellman
．分布Bellman方程式
モーメント推定量に関する収束率はO(γk)
線形変換された
線形変換されたモーメント
されたモーメント推定誤差
モーメント推定誤差ベクトル
推定誤差ベクトル
１DPステップで少なくても γ （<1）減衰
の各要素は
各要素は
減衰率
24
© 2011 IBM Corporation
(リスク考慮型強化学習)
方程式
リスク考慮型強化学習) 2．分布Bellman
．分布Bellman方程式
モーメント推定量に関する収束率はO(γk)
Special case： 一次モーメント
分布Bellman方程式
方程式における
分布
方程式におけるDPでの
における での1次
での 次のモーメントの
モーメントの収束率は
収束率は、
従来の
方程式における
従来のBellman方程式
方程式におけるDPの
における の収束率と
収束率と同じ
期待値推定から分布
から分布への
分布への自然
への自然な
自然な拡張
⇒ dBellman-DPは、Bellman-DPの期待値推定から
25
© 2011 IBM Corporation
(リスク考慮型強化学習)
方程式
リスク考慮型強化学習) 2．分布Bellman
．分布Bellman方程式
[ご参考] 数値実験でDPの収束性を検証
14状態
状態の
状態のランダムウォーク
0
A
1
-1
0
2
-1
0
3
-1
4
0
-1
5
-1
-1
14
30
B
0
0 Start 0
KS統計量
統計量で
方程式に
統計量で分布Bellman方程式
分布
方程式に基づくDPの
づく の収束性を
収束性を評価
–KS (Kolmogorov-Smirnov) 統計量 :
1
DP on d-Bellman
Maximum KS statistic
• 2つの分布 p と q を差異を計る最も
有効かつ一般的な統計量の一つ
0.8
0.6
0.4
0.2
0
0
26
Proposition 1
50
100
time step
150
200
© 2011 IBM Corporation
(リスク考慮型強化学習)
リスク考慮型強化学習)
（リスク考慮型強化学習）
目次：
1. 二つのアプローチ
2. 分布Bellman方程式
3.分布
分布Bellman方程式
方程式を
分布
方程式を用いたリターン
いたリターン分布推定
リターン分布推定
- パラメトリック法 [Morimura+ UAI2010]
- ノンパラメトリック法 [Morimura+ ICML2010]
- 実験
4.推定リターン分布を用いたリスク考慮型意思決定
5.まとめ
27
© 2011 IBM Corporation
(リスク考慮型強化学習)
方程式を用いたリターン分布推定
リスク考慮型強化学習) 3．分布Bellman
．分布Bellman方程式を用いたリターン分布推定
分布モデルを仮定して分布Bellman方程式を解く
分布Bellman方程式
方程式は
分布
方程式は汎関数の
汎関数の自由度持つため
自由度持つため、
つため、そのままでは解
そのままでは解き
にくい
–リターン分布のモデルを仮定する
方針
–以下の繰り返して、少しずつ分布Bellman方程式の再帰（右辺と左辺の）
関係を満たすようにする
近似
28
推定リターン
推定リターン分布
リターン分布
ターゲット分布
ターゲット分布
（分布Bellman方程式の左辺
左辺に対応）
左辺
（分布Bellman方程式の右辺
右辺に対応）
右辺
© 2011 IBM Corporation
(リスク考慮型強化学習)
リスク考慮型強化学習)
（リスク考慮型強化学習）
目次：
1. 二つのアプローチ
2. 分布Bellman方程式
3.分布
分布Bellman方程式
方程式を
分布
方程式を用いたリターン
いたリターン分布推定
リターン分布推定
- パラメトリック法
パラメトリック法 [Morimura+ UAI2010]
- ノンパラメトリック法 [Morimura+ ICML2010]
- 実験
4.推定リターン分布を用いたリスク考慮型意思決定
5.まとめ
29
© 2011 IBM Corporation
(リスク考慮型強化学習)
方程式を用いたリターン分布推定 ｜パラメトリック・アプローチ
リスク考慮型強化学習) 3．分布Bellman
．分布Bellman方程式を用いたリターン分布推定
パラメトリック・リターン分布推定:
KLダイバージェンスを(確率的)自然勾配法により最小化
リターン分布
リターン分布を
分布をパラメータθ をもつパラメトリック
をもつパラメトリック分布
パラメトリック分布
ターゲット分布
ターゲット分布
を使用
から
で表現
の擬距離に
ダイバージェンス
擬距離にKLダイバージェンス
θ を調整して
調整して DKLを（局所）
局所）最小化することで
最小化することで、
することで、リターン分布
リターン分布を
分布を推定
–DKLの勾配:
–(確率的)自然勾配法により最小化: ←指数分布族を
指数分布族を使えばモーメント
えばモーメントが
モーメントが一致
30
学習率
p̂η (η|s, θ) のフィッシャー情報行列
© 2011 IBM Corporation
(リスク考慮型強化学習)
方程式を用いたリターン分布推定 ｜パラメトリック・アプローチ
リスク考慮型強化学習) 3．分布Bellman
．分布Bellman方程式を用いたリターン分布推定
使用するパラメトリック分布
解析的に
を計算できる
解析的に自然勾配と
自然勾配とVaRを
計算できる分布
できる分布を
分布を利用
31
– ガウス分布：
← 指数分布族のため
指数分布族のため、
のため、モーメント一致性
モーメント一致性が
一致性が保障される
保障される
– ラプラス分布：
← 裾野の
裾野の重たい対称分布
たい対称分布
– 歪ラプラス分布：
← 裾野の
裾野の重たい
非対称分布
(どの分布も平均は0)
© 2011 IBM Corporation
(リスク考慮型強化学習)
方程式を用いたリターン分布推定 ｜パラメトリック・アプローチ
リスク考慮型強化学習) 3．分布Bellman
．分布Bellman方程式を用いたリターン分布推定
各パラメトリック分布の更新式
ガウスモデル：
ガウスモデル： [ µ µ(s; θ), σ σ(s; θ), µ′ µ(s+1 ; θ), σ′ σ(s+1 ; θ), δ r + γµ′ − µ ]
従来の
従来のTD学習と
学習と同じ更新式
TD誤差
誤差
[Dearden 1998, Sato & Kobayashi 2001]
の分散の
分散の更新式と
更新式と同様
ラプラスモデル：
ラプラスモデル： [ m m(s; θ), b b(s; θ), m′ m(s+1 ; θ), b′ b(s+1 ; θ), δ r + γm′ − m:
]
ガウスモデルと
ガウスモデルと異なり、
なり、更新量
が bound される
↓
ロバストRLの更新式と
更新式と類似
[Mihatsch & Neuneier 2002, Sugiyama+ 2010]
歪ラプラスモデル：
ラプラスモデル： [ m′ m(s; θ), b b(s; θ), c ′ c(s; θ), m′ m(s+1 ; θ), b′ b(s+1 ; θ),
c c(s+1 ; θ), δ r + γm − m ]
・δ≦0
32
・δ ＞0
© 2011 IBM Corporation
(リスク考慮型強化学習)
方程式を用いたリターン分布推定 ｜パラメトリック・アプローチ
リスク考慮型強化学習) 3．分布Bellman
．分布Bellman方程式を用いたリターン分布推定
TD誤差（δ ）対する、更新値
・ ガウスモデル
・ ラプラスモデル
bound
されてる
bound
されてる
・ 歪ラプラスモデル (対称)
33
・歪ラプラスモデル (非対称)
© 2011 IBM Corporation
(リスク考慮型強化学習)
リスク考慮型強化学習)
（リスク考慮型強化学習）
目次：
1. 二つのアプローチ
2. 分布Bellman方程式
3.分布
分布Bellman方程式
方程式を
分布
方程式を用いたリターン
いたリターン分布推定
リターン分布推定
- パラメトリック法 [Morimura+ UAI2010]
- ノンパラメトリック法
ノンパラメトリック法 [Morimura+ ICML2010]
- 実験
4.推定リターン分布を用いたリスク考慮型意思決定
5.まとめ
34
© 2011 IBM Corporation
(リスク考慮型強化学習)
方程式を用いたリターン分布推定 ｜ノンパラメトリック・アプローチ
リスク考慮型強化学習) 3．分布Bellman
．分布Bellman方程式を用いたリターン分布推定
ノンパラメトリック・リターン分布推定：
パーティクルでリターン分布を近似
N個のパーティクル
でリターン分布
リターン分布
–ランダムにパーティクルηi を選ぶことは、近似分布
を1つ生成することと同義：
を近似
から標本
1
Particles
Estimated probability density
PDF/CDF
0.8
Estimated cumulative distribution
0.6
0.4
※パーティクルから確率密度への変換には、
ガウスカーネルを使用
0.2
0
35
-3
-2
-1
0
Return
1
2
3
© 2011 IBM Corporation
(リスク考慮型強化学習)
方程式を用いたリターン分布推定 ｜ノンパラメトリック・アプローチ
リスク考慮型強化学習) 3．分布Bellman
．分布Bellman方程式を用いたリターン分布推定
パーティクル・スムージングによる分布推定：
1時刻先の状態のパーティクルを利用して、現状態のパーティクルを更新
リターン分布
リターン分布の
分布の再帰式
より、
より、互いに独立
いに独立な
独立な標本 (r(1),v+1(1)),…,(r(N), v+1(N)) を用いて：
いて：
（ I は指示関数）
＜分布の
分布の平衡式＞
平衡式＞
パーティクル・
；PS)
パーティクル・スムージング (Particle Smoothing；
–
を分布の
状態s のパーティクル
分布の平衡式に従わせるには、乱択の
平衡式
一時刻先の
一時刻先の状態s+1 の乱択パーティクル
乱択パーティクル
36
を、
を用いて更新
いて更新すればいい
更新すればいい：
すればいい：
© 2011 IBM Corporation
(リスク考慮型強化学習)
方程式を用いたリターン分布推定 ｜ノンパラメトリック・アプローチ
リスク考慮型強化学習) 3．分布Bellman
．分布Bellman方程式を用いたリターン分布推定
Particle Smoothing Return Distribution approximation
(RDPS) アルゴリズム
ダイナミクス
ダイナミクス（
ダイナミクス（環境）
環境）に関する知識
する知識は
知識は必要としない
必要としない
– 以下の繰り返し
(iv) update
(i) 方策に従って行動選択 at
(ii) 次状態 st+1 と報酬 rtを観測
(iii) 乱択で st と st+1 のパーティクルを一つ選択
(iv) 選んだ st のパーティクルを rt と
st+1のパーティクルを用いて更新
(ii) observe
(iii) pick
s+1
(iii) pick
reward
s
old-approximation of
the return distribution
Only using
using
Only
observations
return
update
new-approximation
37
© 2011 IBM Corporation
(リスク考慮型強化学習)
方程式を用いたリターン分布推定 ｜ノンパラメトリック・アプローチ
リスク考慮型強化学習) 3．分布Bellman
．分布Bellman方程式を用いたリターン分布推定
RDPSアルゴリズムの精度保証
Kolmogorov-Smirnov (KS) 統計量で
測る
と
の相違度を
Proposition (概要): extending Kolmogoroff (1941) result
PDPSのパーティクル更新を十分に繰り返せば、 以下が成り立つ
分散
⇒ パーティクル数
方程式の
パーティクル数を増やすほど、
やすほど、分布Bellman方程式
分布
方程式の残差を
残差を減らせる
38
© 2011 IBM Corporation
(リスク考慮型強化学習)
リスク考慮型強化学習)
（リスク考慮型強化学習）
目次：
1. 二つのアプローチ
2. 分布Bellman方程式
3. 分布Bellman方程式
方程式を
分布
方程式を用いたリターン
いたリターン分布推定
リターン分布推定
- パラメトリック法 [Morimura+ UAI2010]
- ノンパラメトリック法 [Morimura+ ICML2010]
- 実験
4. 推定リターン分布を用いたリスク考慮型意思決定
5. まとめ
39
© 2011 IBM Corporation
(リスク考慮型強化学習)
方程式を用いたリターン分布推定 ｜数値実験
リスク考慮型強化学習) 3．分布Bellman
．分布Bellman方程式を用いたリターン分布推定
数値実験：
リターン分布推定能を評価 ※エージェントはランダムウォーク
無限期間
期間、
状態2行動
期間、5状態
状態 行動MDP
行動
報酬の設定
：状態
：リンク
：r ~ N(µ=20, σ2=2)
（N：ガウス分布）
：r ~ G(k=2, θ=5)+30
（G：ガンマ分布）
有限期間
期間、
状態2行動
期間、5状態
状態 行動MDP
行動
その他の
状態遷移 ：r = 0
：終端状態
無限期間
期間、
状態2行動
期間、30状態
状態 行動MDP
行動
–状態遷移確率と報酬は乱数で決定 [Morimura+ ’09]
• 状態遷移はDirichlet分布で初期化
• 報酬はガウス分布で初期化
40
© 2011 IBM Corporation
(リスク考慮型強化学習)
方程式を用いたリターン分布推定 ｜数値実験
リスク考慮型強化学習) 3．分布Bellman
．分布Bellman方程式を用いたリターン分布推定
無限期間、5状態MDP：
0.02
0.01
0
50
Return
100
0.02
0.01
0
150
0
25
Return
0.02
0.01
0
150
0
0
25
Return
0
5
Return
10
150
: 10*103ステップ時
0
0
25
Return
: 15*104ステップ時,
50
: 30*104ステップ時
0.3
0.2
0.1
0
-5
100
0.05
50
: 6*104ステップ時,
Probability Density
0.1
50
Return
0.1
0.3
0.2
0
: 5*103ステップ時,
0.05
50
無限期間、30状態MDP
Probability Density
100
Probability Density
Probability Density
0.05
0
-5
50
Return
: 30*103ステップ時
• パーティクルモデル（ノンパラメトリックモデル）
0.1
0.3
41
0
: 2*103ステップ時,
0.1
0
0
: 15*103ステップ時,
• 歪ラプラスモデル（パラメトリックモデル）
有限期間、5状態MDP:
Probability Density
: 6*103ステップ時,
Probability Density
Probability Density
• ガウスモデル（パラメトリックモデル）
: 真のリターン分布
リターン分布（モンテカルロにより
モンテカルロにより推定
により推定）
推定）]
[
Probability Density
のリターン分布推定結果
リターン分布推定結果
Probability Density
状態
0
5
Return
10
0.2
0.1
0
-5
0
©
Corporation
5 2011 IBM 10
Return
(リスク考慮型強化学習)
リスク考慮型強化学習)
（リスク考慮型強化学習）
目次：
1. 二つのアプローチ
2. 分布Bellman方程式
3. 分布Bellman方程式を用いたリターン分布推定
- パラメトリック法 [Morimura+ UAI2010]
- ノンパラメトリック法 [Morimura+ ICML2010]
- 実験
4. 推定リターン
推定リターン分布
リターン分布を
分布を用いたリスク
いたリスク考慮型意思決定
リスク考慮型意思決定
5. まとめ
42
© 2011 IBM Corporation
(リスク考慮型強化学習)
リスク考慮型強化学習) 4．推定リターン分布を用いたリスク考慮型意思決定
推定リターン分布を用いたリスク考慮型意思決定の例
RDPSにより
によりリターン
によりリターン分布
リターン分布を
分布を求められるので、
められるので、分布から
分布から規定
から規定される
規定される任意
される任意
のリスク指標
を用いた最適化問題
リスク指標
いた最適化問題を
最適化問題を扱える:
える
リスク嗜好性は探索・搾取のトレードオフをバランスする [Bagnell 2004]
– Risk-aversion → 搾取 (robust RL)
– Risk-taking → 探索
今回は
を用いて探索
今回は、CVaRを
いて探索の
探索の効率化を
効率化を目指す
目指す
– 実方策（実際の行動選択に用いる探索用方策）
と目的方策の二種類の方策を用いる
43
• 実方策の目的関数： CVaR+
• 目的方策の目的関数： 期待リターン
• (両方策のバランスに重点サンプリングを利用)
PDF
CVaR+c
(c)
(1-c)
VaRc
return
© 2011 IBM Corporation
(リスク考慮型強化学習)
リスク考慮型強化学習) 4．推定リターン分布を用いたリスク考慮型意思決定
リスクを活用すれば，学習の効率化が実現できます
隠れたチャンス
れたチャンス（
チャンス（リスク）
リスク）を発見する
発見する
0
A
1
-1
0
2
-1
0
3
-1
0
4
チャンス
-1
5
-1
0 Start 0
-1
14
30
B
0
Proposed algorithm
(chance-discovery RL)
44
© 2011 IBM Corporation
(リスク考慮型強化学習)
リスク考慮型強化学習)
（リスク考慮型強化学習）
目次：
1. 二つのアプローチ
2. 分布Bellman方程式
3. 分布Bellman方程式を用いたリターン分布推定
- パラメトリック法 [Morimura+ UAI2010]
- ノンパラメトリック法 [Morimura+ ICML2010]
- 実験
4. 推定リターン分布を用いたリスク考慮型意思決定
5. まとめ
45
© 2011 IBM Corporation
(リスク考慮型強化学習)
リスク考慮型強化学習) 5．まとめ
まとめ
リターン分布
方程式をみた
リターン分布の
分布の再帰式である
再帰式である分布
である分布Bellman方程式
分布
方程式をみた
–その性質、解の一意性などを明らかにした
分布Bellman方程式
方程式を
分布
方程式を用いた二通
いた二通りの
二通りのリターン
りのリターン分布法
リターン分布法を
分布法を提案した
提案した
–パラメトリック法： 自然勾配によりKLダイバージェンス
ダイバージェンスを(局所)最小化
ダイバージェンス
–ノンパラメトリック法： particle smoothingによりKS統計量
統計量を小さくする
統計量
パラメトリック・
パラメトリック・アプローチ
ノンパラ・
ノンパラ・アプローチ
収束までに
収束までに要
までに要する試行数
する試行数
（学習の
学習の効率）
効率）
モデルの
モデルの自由度
（≒VaR等
等の推定精度）
推定精度）
小ない
低い
多い
高い
リスク考慮
リスク考慮によって
考慮によって、
によって、効率の
効率の良い探索を
探索を達成できることを
達成できることを示
できることを示した
46
© 2011 IBM Corporation
参考文献
N. Abe, N. K. Verma, C. Apte, and R. Schroko. Cross channel optimized marketing by reinforcement learning. In
International Conference on Knowledge Discovery and Data Mining, pages 767-772, 2004.
D Bello and G Riano. Linear programming solvers for markov decision processes. In IEEE Systems and Information
Engineering Design Symposium, pages 90-95, 2006.
R. I. Brafman and M. Tennenholtz. R-max { a general polynomial time algorithm for near-optimal reinforcement learning.
Journal of Machine Learning Research, 3:213-231, 2003.
A. Kolmogoroff. Condence limits for an unknown distribution function. The Annals of Mathematical Statistics, 12(4):461-463,
1941.
J. Langford. Reinforcement Learning Theory. Machine Learning Summer School, 2006.
M. G. Lagoudakis and R. Parr. Least-squares policy iteration. Journal of Machine Learning Research, 4:1107-1149, 2003.
T. Morimura, M. Sugiyama, H. Kashima, H. Hachiya, and T. Tanaka. Nonparametric return distribution approximation for
reinforcement learning. In International Conference on Machine Learning,2010.
T. Morimura, M. Sugiyama, H. Kashima, H. Hachiya, and T. Tanaka. Parametric return density estimation for reinforcement
learning. In Conference on Uncertainty in Articial Intelligence, 2010.
J. Peters, S. Vijayakumar, and S. Schaal. Reinforcement learning for humanoid robotics. In IEEE-RAS International
Conference on Humanoid Robots, 2003.
M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, 1994.
A. L. Strehl, L. Li, and M. L. Littman. Reinforcement learning in nite mdps: Pac analysis. Journal of Machine Learning
Research, 10:2413-24443, 2009.
R. S. Sutton and A. G. Barto. Reinforcement Learning. MIT Press, 1998.
G. Tesauro. Temporal difference learning and td-gammon. Communications of the ACM, 38(5): 58-68, 1995.
C. J. C. H. Watkins and P. Dayan. Technical note: Q-learning. Machine Learning, 8:279{292, 1992.
R. J. Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning,
8:229-256, 1992.
中田浩之and 田中利幸. マルコフ決定過程における収益分布の評価. In 情報論的学習理論ワークショップ(IBIS), 2006.
森村哲郎, 杉山将, 八谷大岳, 鹿島久嗣, and 田中利幸. 動的計画法によるリターン分布推定. In 報論的学習理論ワ－クショッ
47 プ (IBIS), 2010.
© 2011 IBM Corporation