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で近似する方法を提案する 単語リストと生コーパスによる確率的言語モデルの分野適応 森 信介 自然言語処理 (2006) Language Model Adaptation with a Word List and a Raw Corpus Shinsuke MORI ICSLP 2006

著者について 著者のEmanuel Todorov はUCSD の人 主に（人間を含む）制御系の話を研究しているらしい NIPS常連さんらしい ちょっと「脳みそNIPS」よりの人のようだ？ 参考文献4件（!）なので、なにか本質的に新しい技を提案してるかも？

マルコフ決定過程（MDP）のおさらい

マルコフ決定過程（MDP）のおさらい： マルコフ決定過程は、「アクションつきの」マルコフ過程 各状態 でアクションを選ぶと、あるコストが発生して次の状態に行くというのを繰り返していくゲームを考える 状態 i から状態 j に遷移する確率が、状態 i においてとるアクション u に依存する 状態遷移確率 pij(u) （普通のマルコフ過程ではコレがuに依存しない） 状態 i でアクション u をとると、コスト l(i, u) が発生する 終了状態のどれかに到達すると終了 ⇒ 総期待コストが最小になるようなアクションuを決定したい 解き方： 各状態の価値関数 v(i) についての再帰式を解く 価値関数 v(i) ： 状態 i から、将来にわたってかかるコストの期待値 通常、value iteration (か policy iteration) によって解く（以下を繰り返す） 現在の行動ポリシーのもとで、再帰式を解き、価値関数を得る 現在の価値関数のもとで、最良の行動ポリシーを決定する 0.3 0.7 0.7 0.3 状態 i の価値 状態 i で行動 u のコスト 次の状態 j の価値 遷移確率 （行動に依存） red と blue の２つのアクションの どちらをとるかで遷移確率がかわる

速く解けるMDP

MDPをもっと速く解きたい： 固有値計算一発で最良の行動ポリシーが求まる「念MDP」のクラスを考えた 状態 i でアクションを「状態 j に行けと念じるパワー uj 」によって与えるとする 遷移確率が 念uj によって変わるようなモデルを考える すると、以下の式を解けば状態の価値 v(i) が求まる よく観ると、（固有値１の）最大固有ベクトルを求めることになっている 反復計算： 非ゼロの の個数に比例した時間 結果、最適なアクション（念）は 求まった v(i) を以下の式に代入すると求まる ホントはこう書くのが正しい ベースの遷移確率 状態 j に行けと 念じる力 （注：i ごとに異なる） 実際の遷移確率 （行動に依存） given

実は、念MDPには、もうひとつ、コストに仮定をおいている： 「大きく分布を曲げるのには、念パワーを使う」 コストは、状態 i のコスト と、 と のKL-divergence の和とする 参考） KL-divergence の計算 なぜなら 状態 i で行動 u のコスト 状態 i のコスト 「ベースの確率」と 「念の入った確率」 の KL-divergence

参考）導出の概要 もともとのMDPの式 今回の仮定をいろいろ代入すると 確率の制約に気をつけて最小化問題を解く → ラグランジュ乗数法 状態 i の価値 状態 i で行動 u のコスト 次の状態 j の価値 遷移確率 （行動に依存） もともとのMDPの式 今回の仮定をいろいろ代入すると 確率の制約に気をつけて最小化問題を解く → ラグランジュ乗数法 と、最適な念の強さが求まる これをまたMDPに入れなおすと（minが落ちて）固有値問題がでてくる 状態 i のコスト ベースの遷移確率 念 制約：遷移確率の和が１ ラグランジアン

ここまでのまとめ： アクションが「右に行く」とか「左に行く」とか離散的ではなく、 「i からj に遷移しろと念じる強さ」であるとしたMDPは速くとける ポイントは、連続入力にしたことによって、離散アクションのminが、制約つきの最小化問題として解けちゃうところ コッソリ、コストにKL-divergenceが入っているのに注意 KL-divergence とは、ここでは「念の力によってどのくらい遷移確率を曲げたか」 コストの解釈： 「分布を大きく曲げると、パワーを消耗する」 が、実はKL-divergenceには上限があるので、状態コストを大きくすれば、相対的に影響は小さくなる ⇒ でも、このままでは何に使えるのかわからない 実は、最短経路問題 がコレを使って解ける 実は、離散アクションMDPを、念MDPで近似できる

最短経路問題を念MDPで解く

最良の行動ポリシーの下では最短経路の長さになる 最短経路問題は念MDPとして書ける 最短経路問題： 各状態から終了状態までの最短パスを見つける Dijkstra法はO(|枝| log|ノード|) これを模倣する念MDPをつくる ベースの遷移確率はランダムウォークとする 状態コスト： 一歩あるくごとに、コストρ 最終状態 最終状態以外 すると、状態の価値は、ρ×（そこから最終状態までの期待ステップ数） ＋ KL ρを十分大きくとれば、≒ ρ×（そこから最終状態までの期待ステップ数） と思ってよし ⇒ つまり、最短経路を小さくする念を求めることになる i → j の枝があれば１ （多分ホントは何でもいい） 最良の行動ポリシーの下では最短経路の長さになる

最短経路問題への適用例 左図：ρ小さい 右図：ρ大きい （左上がゴール）

離散アクションのMDPを念MDPで近似する

まず、離散アクションのMDPと等価な念MDPを想像する： 両者の確率が同じになるようにベースの遷移確率と状態のコストを調整する 遷移確率が同じになる必要がある コストが同じになる必要がある コレを解くと、 、 、 が求まる 念MDPの パラメータ 普通MDPの パラメータ コレをみたしている筈 ベースの遷移確率 念 （アクションa毎） 通常のMDPの遷移確率 （離散アクション a に依存する） 念MDPの コスト 普通MDPの コスト 状態 i のコスト 「ベースの確率」と 「念の入った確率」 の KL-divergence

対応する念MDPの解が、もとのMDPを再現する念じ方になっていない可能性があるので、あくまで近似解法 対応する念MDP上で、アクション a と同等のことをしようと思ったら、 のように念じれば、その結果はもともとのMDPと同じになる 問題： 対応する念MDPにおける、最適コストな念じる力 は、必ずしもどれかの a の には一致しない 解決策： 近似でがまん 求めた と を使って、念MDPを解き を得る に、もっとも近い をもつアクション a をえらべばよい ホントにこれでいいのかなあ… ⇒ 曰く、「整数計画を線形計画で近似するやつを想像してみ」

ここまでのまとめ： 最短経路問題が、念MDPとして書ける 念じる力は、どっちへむかうかという経路選択のポリシーと対応付ける コストを、終点までの距離に対応付ける コストにKL-divergenceが余分に入ってしまう問題は、KL以外のコストを大きくすることで相対的にKLが無視できるようにすることで解決 通常の離散アクションMDPを、念MDPとして近似的に解く 離散アクションMDPと等価な、念MDPを考える 念MDPを解いて得られる念じ方は、もとのMDPを再現する念の入れ方とは違う可能性がある もとのMDPのアクションはそれと近いものを選ぶことで近似的に解決

おわり このあと、離散MDPの確率などもわからない場合（強化学習： Q-learning）の場合に、実際に行動をとって得られたサンプルを使って、stochastic approximationする方法も提案される 普通のQ-learning よりも収束が速い 「離散的なmax(or min)操作を連続値に置き換えて閉じた形で解く」という技としてみると、他にもいろいろ使い道があるような気がする… parsing とかの、structure output 問題とか… 連続状態化できるかな？