Document

読む
NIPS
Linearly-solvable Markov decision problems
Emanuel Todorov (UCSD)
Figures are borrowed from the paper in NIPS2006
これを読む人：鹿島久嗣（IBM TRL）
この論文の目的：超速くマルコフ決定過程を解く
 超速く解けるマルコフ決定過程（MDP）のクラス（「linearMDP」、別名「念じるMDP」、
略して「念MDP」）を提案する
– ある種の連続的な入力「念」をもつ特殊なMDPを考える
– 最大固有ベクトルを求める問題に帰着される
 通常の離散アクションをもつMDPを、念MDPで近似する
– 最短経路問題を、念MDPで近似する方法を提案する
– 通常の離散アクションをもつMDPを、念MDPで近似する方法を提案する
2
著者について
 著者のEmanuel Todorov はUCSD の人
 主に（人間を含む）制御系の話を研究しているらしい
– NIPS常連さんらしい
– ちょっと「脳みそNIPS」よりの人のようだ？
 参考文献4件（!）なので、なにか本質的に新しい技を提案してるかも？
3
マルコフ決定過程（MDP）のおさらい
4
マルコフ決定過程（MDP）のおさらい：
マルコフ決定過程は、「アクションつきの」マルコフ過程

各状態でアクションを選ぶと、あるコストが発生して次の状態に行くというのを繰り返していく
ゲームを考える
– 状態 i から状態 j に遷移する確率が、状態 i においてとるアクション u に依存する
•
状態遷移確率 pij(u) （普通のマルコフ過程ではコレがuに依存しない）
– 状態 i でアクション u をとると、コスト l(i, u) が発生する
0.3
– 終了状態のどれかに到達すると終了
⇒ 総期待コストが最小になるようなアクションuを決定したい
0.7

0.7
解き方：各状態の価値関数 v(i) についての再帰式を解く
– 価値関数 v(i) ：状態 i から、将来にわたってかかるコストの期待値
状態 i の
価値
状態 i で
行動 u
のコスト
0.3
red と blue の２つのアクションの
どちらをとるかで遷移確率がかわる
遷移確率
（行動に依存）
次の状態
j の価値
– 通常、value iteration (か policy iteration) によって解く（以下を繰り返す）
1. 現在の行動ポリシーのもとで、再帰式を解き、価値関数を得る
2. 現在の価値関数のもとで、最良の行動ポリシーを決定する
5
速く解けるMDP
6
MDPをもっと速く解きたい：
固有値計算一発で最良の行動ポリシーが求まる「念MDP」のクラスを考えた
 連続値の入力をアクションとして受け付ける、ある種のMDPを考える
– 状態 i でアクションを「状態 j に行けと念じるパワー uj 」によって与えるとする
– 遷移確率が念uj によって変わるようなモデルを考える
ホントはこう書くのが正しい
実際の遷移確率
（行動に依存）
ベースの
遷移確率
状態 j に行けと
念じる力
（注：i ごとに異なる）
 すると、以下の式を解けば状態の価値 v(i) が求まる
– よく観ると、（固有値１の）最大固有ベクトルを求めることになっている
given
– 反復計算：非ゼロの
の個数に比例した時間
 結果、最適なアクション（念）は求まった v(i) を以下の式に代入すると求まる
7
実は、念MDPには、もうひとつ、コストに仮定をおいている：
「大きく分布を曲げるのには、念パワーを使う」
 コストは、状態 i のコストと、
状態 i で
行動 u
のコスト
状態 i の
コスト
と
のKL-divergence の和とする
「ベースの確率」と
「念の入った確率」
の KL-divergence
 参考） KL-divergence の計算
– なぜなら
実際の遷移確率
（行動に依存）
8
ベースの
遷移確率
状態 j に行けと
念じる力
（注：i ごとに異なる）
参考）導出の概要
 もともとのMDPの式
状態 i の
価値
状態 i で
行動 u
のコスト
次の状態
j の価値
遷移確率
（行動に依存）
 今回の仮定をいろいろ代入すると
状態 i の
コスト
ベースの
遷移確率
念
 確率の制約に気をつけて最小化問題を解く → ラグランジュ乗数法
ラグランジ
アン
制約：遷移確率
の和が１
と、最適な念の強さが求まる
 これをまたMDPに入れなおすと（minが落ちて）固有値問題がでてくる
9
ここまでのまとめ：

アクションが「右に行く」とか「左に行く」とか離散的ではなく、
「i からj に遷移しろと念じる強さ」であるとしたMDPは速くとける
– ポイントは、連続入力にしたことによって、離散アクションのminが、制約つきの最
小化問題として解けちゃうところ

コッソリ、コストにKL-divergenceが入っているのに注意
– KL-divergence とは、ここでは「念の力によってどのくらい遷移確率を曲げたか」
•
コストの解釈：「分布を大きく曲げると、パワーを消耗する」
– が、実はKL-divergenceには上限があるので、状態コストを大きくすれば、相対
的に影響は小さくなる
⇒ でも、このままでは何に使えるのかわからない
1. 実は、最短経路問題がコレを使って解ける
2. 実は、離散アクションMDPを、念MDPで近似できる
10
最短経路問題を念MDPで解く
11
最短経路問題は念MDPとして書ける
 最短経路問題：各状態から終了状態までの最短パスを見つける
– Dijkstra法はO(|枝| log|ノード|)
 これを模倣する念MDPをつくる
i → j の枝が
あれば１
– ベースの遷移確率はランダムウォークとする
– 状態コスト：一歩あるくごとに、コストρ
（多分ホントは何でもいい）
• 最終状態
• 最終状態以外
 すると、状態の価値は、ρ×（そこから最終状態までの期待ステップ数）＋ KL
最良の行動ポリシーの下では最
短経路の長さになる
 ρを十分大きくとれば、≒ ρ×（そこから最終状態までの期待ステップ数）と思ってよし
⇒ つまり、最短経路を小さくする念を求めることになる
12
最短経路問題への適用例
 左図：ρ小さい

（左上がゴール）
13
右図：ρ大きい
離散アクションのMDPを念MDPで近似する
14
まず、離散アクションのMDPと等価な念MDPを想像する：
両者の確率が同じになるようにベースの遷移確率と状態のコストを調整する
 通常の（＝離散アクションの）MDP を念MDPで再現しようとすると、以下のつりあいを
満たすように、ベースの遷移確率と状態のコストを調整する必要がある
– 遷移確率が同じになる必要がある
普通MDPの
パラメータ
念MDPの
パラメータ
通常のMDPの遷移確率
（離散アクション a に依存する）
念
（アクションa毎）
ベースの
遷移確率
– コストが同じになる必要がある
念MDPの
コスト
「ベースの確率」と
「念の入った確率」
の KL-divergence
状態 i の
コスト
15
 コレを解くと、
、
普通MDPの
コスト
、
が求まる
コレをみたしている筈
対応する念MDPの解が、もとのMDPを再現する念じ方になっていない可能
性があるので、あくまで近似解法
 前頁で求まった
、
、
が実現できれば離散アクションMDPを再現できる
– 対応する念MDP上で、アクション a と同等のことをしようと思ったら、
うに念じれば、その結果はもともとのMDPと同じになる
 問題：対応する念MDPにおける、最適コストな念じる力
のaの
には一致しない
は、必ずしもどれか
 解決策：近似でがまん
– 求めた
–
と
を使って、念MDPを解き
に、もっとも近い
を得る
をもつアクション a をえらべばよい
 ホントにこれでいいのかなあ…
⇒ 曰く、「整数計画を線形計画で近似するやつを想像してみ」
16
のよ
ここまでのまとめ：

最短経路問題が、念MDPとして書ける
– 念じる力は、どっちへむかうかという経路選択のポリシーと対応付ける
– コストを、終点までの距離に対応付ける
– コストにKL-divergenceが余分に入ってしまう問題は、KL以外のコストを大きくす
ることで相対的にKLが無視できるようにすることで解決

通常の離散アクションMDPを、念MDPとして近似的に解く
– 離散アクションMDPと等価な、念MDPを考える
– 念MDPを解いて得られる念じ方は、もとのMDPを再現する念の入れ方とは違う
可能性がある
– もとのMDPのアクションはそれと近いものを選ぶことで近似的に解決
17
おわり
 このあと、離散MDPの確率などもわからない場合（強化学習： Q-learning）の場合に、
実際に行動をとって得られたサンプルを使って、stochastic approximationする方法
も提案される
– 普通のQ-learning よりも収束が速い
 「離散的なmax(or min)操作を連続値に置き換えて閉じた形で解く」という技としてみ
ると、他にもいろいろ使い道があるような気がする…
– parsing とかの、structure output 問題とか…
 連続状態化できるかな？
18

Download Report