Learning Action Representations for Reinforcement Learningを読んだ際のメモ

出典

 International Conference on Machine Learning 2019に採択

読んだ理由

 前回に続いて行動の表現を学習する手法についてのものがICMLにあった。特に昨日の論文が行動ログから事前学習という形のものだったのに対して、より強化学習の学習ステップに明示的に組み込まれているようだったので読んでみた。

概要

 行動決定を(1)行動表現空間への方策計算(2)サンプリングされた表現から行動への復元 という2ステップに分ける手法を提案。行動空間が大きい場合に対する強化学習で性能が向上する。普通の方策勾配法に組み込むことができるので汎用的に適用できる。

詳細

 全体としての方策を\pi_o、表現部分への確率分布を示す方策を\pi_iとして、行動を次のように2段階で決定する。

f:id:tokumini:20190614185200p:plain

 式としては次のように行動決定する。

$$ E_t \sim \pi_i(\cdot|S_t), \qquad A_t = f(E_t) $$

\pi_iを固定した際のfの学習方法

 まず前提として二つの連続した状態が与えられた際の行動推定は、行動の表現を介して次のように表せる。

$$ P(A_t | S_t, S_{t + 1}) = \int_{\varepsilon} P(A_t|E_t = e)P(E_t=e|S_t, S_{t+1}) \mathrm{d}e $$

 右辺の二つの要素をそれぞれ\hat{f},\hat{g}としてパラメータを持つ関数で近似することを考える。\hat{f}はそのまま表現から実際の行動への復号関数fの推定として推論時にも用いるが、\hat{g}\hat{f}を学習するためだけに用いるものとなる。推定値は次のようになる。(以下式番号は論文中のものと揃えた)

$$ \hat{P}(A_t | S_t, S_{t + 1}) = \int_{\varepsilon} \hat{f}(A_t|E_t = e)\hat{g}(E_t=e|S_t, S_{t+1}) \mathrm{d}e \tag{3} $$

 これらの式をカルバックライブラー情報量で評価する。

$$ D_{KL}\left(P(A_t | S_t, S_{t + 1}) || \hat{P}(A_t | S_t, S_{t + 1})\right) = -\ln \mathbb{E} \left[ \left(\frac{\hat{P}(A_t | S_t, S_{t + 1})}{P(A_t | S_t, S_{t + 1})} \right) \right] \tag{4} $$

 この式の最小化を考えると、分母は定数なので関係なくなる。結局得られた遷移の3つ組(S_t, A_t, S_{t + 1})について損失関数は次のようにすれば良い。

$$ \mathcal{L}(\hat{f}, \hat{g}) = -\mathbb{E}\left[ \ln\left(\hat{P}(A_t | S_t, S_{t + 1}) \right) \right] \tag{5} $$

 報酬は関係しないので遷移からそのまま教師あり学習を行うだけとなる。

 (付録D)実際には表現eについての積分にかかる計算量を抑えるため、積分を取り払って

$$ \hat{P}(A_t | S_t, S_{t + 1}) \approx \hat{f}\left(A_t | \hat{g}(S_t, S_{t+1}) \right) $$

として近似する(これはどの程度正当性があるのだろうか。かなり大胆な近似をしているように思える)。\hat{f}(a|\hat{g}(s, s'))

$$ \hat{f}(a|\hat{g}(s, s')) = \frac{\exp{\frac{z_a}{temp}}}{\sum_{a'} \exp{\frac{z_{a'}}{temp}}} , \qquad z_a = W_a^{\mathrm{T}} \hat{g}(s, s') \tag{22} $$

とする。tempは温度変数(はてなブログの数式モードではギリシャ文字tauが表示できなくて困った)。W \in \mathbb{R}^{d_e \times |\mathcal{A}|}は各列が各行動のd_e次元の表現となる行列。W_a^{\mathrm{T}}は行動aに対応する列を抜き出して転置を取ったベクトル。つまり\hat{g}が予測する表現と今までに学習した表現の内積になっている。

fを固定した際の\pi_iの学習方法

 単純に方策勾配法を用いて学習する。特に全体方策\pi_oではなく内部方策\pi_iに対するパフォーマンス関数の微分で方策勾配法を考えればよい。復号関数fが確定的な関数ならば $$ \frac{\partial J_o(\theta, f)}{\partial \theta} = \frac{J_i(\theta)}{\partial \theta} $$ となるためである(証明は付録B)。これによりf^{-1}を計算する必要はなく、内部方策\pi_iに対する状態価値関数v^{\pi_i}(s)を考えてパフォーマンス関数 $$J_i(\theta) = \sum_{s\in\mathcal{S}} d_{0}(s) v^{\pi_i}(s) $$ に対する微分を考えれば良くなる。(付録D)内部方策\pi_iとして実験ではガウス分布を仮定してその期待値を近似するようなニューラネットワークを学習させた。

同時学習

 以上の結果から次のようなアルゴリズムで学習を行えば同時に学習していくことができる。

f:id:tokumini:20190614171905p:plain

 1行目の部分では、最初にランダム方策による行動から行動表現部分だけを多少学習させる。

実験

迷路タスク

f:id:tokumini:20190614182615p:plain

 星がゴールの位置。n方向に独立なアクチュエータがあり、可能な行動としては全部で2^n通りになる。

実験結果

f:id:tokumini:20190614182650p:plain

 普通のActor-Criticと比較して、nが大きいほど提案手法を入れた場合に性能が伸びやすい。つまり行動が多い場合に有効。

得られた表現

f:id:tokumini:20190614183457p:plain

 左の図はデカルト座標における各行動の遷移先であり、右は表現空間での各行動の座標。左右で同じ行動には同じ色が与えられている。つまり右の図で近い色は近い場所に集まっていることから、同じような行動をまとめることができていると思われる。また特定の方向で最大限移動するような方策がそれぞれ縁にあって区別しやすいように表現が学習できている(?)。

現実世界の推薦システム

 ビデオチュートリアルの推薦とマルチメディア編集ソフトの推薦。ユーザの使用履歴・満足度からMDP環境を作り、そこにおける報酬を最大化するタスク。前者は1498個、後者は1843個の行動(選択肢)が存在。

f:id:tokumini:20190614183645p:plain

 提案手法を入れた方が性能が良く、学習も速い。

所感

  • 言われてみれば自然なやり方に思えるが、実際のところ近似が上手くいくのかどうかが怪しいと感じるところもないわけではない
  • 特に内部方策はガウス分布で近似されており、多次元空間の確率分布はモデル化が難しそうだがもう少し表現力が高そうなものを用いたい気もする
  • 自分の将棋プログラムでは9 \times 9 \times 27 = 2187種類の行動から選択するように実装しているため、だいたい同じくらいの行動の量で性能が上がるなら試してみる価値はありそう。AlphaZero形式の方策学習が方策勾配法とどのような関係にあるのかは理解できていないが、AlphaGoなどでは明示的に方策勾配法が使われていたので応用はできるはず