2017-10-17

分散型DQNの論文を読む

ロボテックス確率・統計

ランニング30分　英語できず

(1) 分散型DQNの論文を読む

　「A Distributional Perspective on Reinforcement Learning」

https://arxiv.org/abs/1707.06887

　この論文はDeepMindのDQNの派生モデルを統合したRainbowの中核を成すもので、DQNに初めて行動価値関数の分布を取り込んだモデルです。

　ロボット学のAbbeel達は方策 $\pi$ 分布の最適化TRPOを提唱していますが、行動価値関数と方策との相違だけで殆ど似たモデルとなっています。やはり細かい制御をするには分布モデルが必要な様です。

　動機としては、簡単なPongゲームでも報酬が複雑な分布をしており、この報酬分布を旨く取り込んで強化学習の精度を向上させようとするものです。

f:id:mabonki0725:20171018183211p:plain

(1.1) 手法

　分布の行動価値関数は以下の $(a) \sim (d)$ で作成します。

ここでDQNは次の損失関数 $\mathcal{L}(\theta)$ を零にする様に $\theta$ を学習しますので

$\mathcal{L}(\theta) =[R+\gamma Q_{\theta-i}(s_{t+1},a_{t+1})-Q_\theta(s,a)]^2$

　下図は細分化変数 $z$ を用いて $Q \to P^\pi Z$ に置き換わったDQNといえます。

f:id:mabonki0725:20171018185434p:plain

　ここで

　　 $z$ は分割したベクトルです

　　 $P^\pi$ は方策 $\pi$ での行動価値関数 $q(s,t|\theta-i)$ です

　　 $\gamma \ \ R$ は割引関数と報酬です

　　 $\Phi$ は分布の整形作用素です（後述）

　まず $z$ を報酬 $V_{min} \sim V_{max}$ で $N_{atoms}$ に分割してます。

　ここで $V_{min} \ \ V_{max}$ は固定のパラメータです。

報酬 $z_j$ 毎に細分化した行動価値関数 $p_j(s,a)$ 分布を算出します。

　　 $p_j(s,t) = \Phi \hat{\mathcal{T}} z_\theta = \sum_{j=0}^{N_{atoms}} \left(1 - \frac{|[\hat{\mathcal{T}}_{z_j}]_{V_{min}}^{V_{max}} - z_i|}{\Delta z} \right)_0^1 \cdot p_j(s_{t+1},\pi(s_{t+1}))$

$z_\theta(s,a) = (p_1(s,a) \dots p_{N_{atoms}}(s,a))^T$

ここで　

　　　 $[\cdot]_a^b$ は $a \sim b$ までの範囲を示します

$\pi(s) = argmax_a Q(s,a)$

ZについてのDQNなので $\theta$ の損失関数 $\mathcal{L}_{s,a}(\theta)$ は前の方策 $z_{\theta_-1}(s,a)$ と現在の $z_\theta(s,a)$ との差としています。

$\mathcal{L}_{s,a}(\theta) = \mathcal{D}_{KL} [z_{\theta-1}(s,t) || z_{\theta}(s,a) ]$

(1.2) 結果

　通常のDQNより早期に精度が向上していおり、分割数も多い方が精度が高いことを示しています。

f:id:mabonki0725:20171018195209p:plain

2017-10-16

DeepMindのDQN統合版のRainBowの論文を読む

ロボテックス AI論文確率・統計

ランニング30分　英語できず

(1) DeepMindのDQN統合版のRainBowの論文を読む

「Rainbow:Combining Imporvements in Deep Reinforcement Learning」https://arxiv.org/abs/1710.02298

　2013年に発表されたDeepMind社のDQNの派生版を統合したRainbowの高パフォーマンスの論文です。

f:id:mabonki0725:20171017160719p:plain

　DQNは２年後にアルファ碁のモデルの中核部分をなすモデルで如何に革新的なものであるか実績が示しています。

　DQNはDeepLearningを使ってEnd-to-Endでモデルを精緻化することに成功しました。

　　・DeepLearning(CNN)による特徴量の自動抽出

　　・自動抽出した特徴量を変数とする行動価値関数の精緻化

　特徴量による価値関数の精緻化はSuttonのニューロモデルで既に実現されていましたが、特徴量の抽出は試行錯誤でした。

　整理のためDQNの論文よりQ-learningの式を掲げます。

https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf

次式は繰返し毎に推定された前の価値行動関数と現在の価値行動関数の差を零にする様に学習しています。

$\mathcal{L_i}(\theta_i) = \mathbb{E} _{s,a \sim \rho(\cdot)} [y_i - Q(s,a | \theta_i)]^2$

但し、 $y_i = \mathbb{E}_{s' \sim \varepsilon} [r + \gamma \ max_{a'} [Q(s',a' | \theta_{i-1} )]$

　損失関数は $L^2$ なので微分式は以下となります

　　 $\frac{\partial \mathcal{L}_i(\theta_i)}{\partial \theta_i} = \mathbb{E}_{s,a \sim \rho(\cdot) \ s' \sim \varepsilon} [ \{r + \gamma \ max_{a'} [Q(s',a' | \theta_{i-1} ) -Q(s,a | \theta_i) \} \frac{\partial Q(s,a | \theta_i)}{\partial \theta_i} ]$ 　

ここで

$\mathcal{L}_i(\theta_i)$ は損失関数

　　　 $i$ は繰返し数

$Q(s,a|\theta)$ が $\theta$ を微分して精緻化する行動価値関数

　　　 $r \ \ \gamma$ は報酬と割引率

　しかしDQNには不得意なゲームがあり、その克服のため多くの改良版が主にDeepMindによって達成されてきました。

(1.1) 手法

　以下の６モデルを統合したのがRainbowとなりますが、

　 5)の分散型強化学習(Deistributional RL)がベースとなっています。

　　1) Double Q-Learning

　　　過学習を避けるため、 $a' \to max_{a'} Q(s',a'|\theta)$ でＱ関数で推定し２重化しています。　　　

$\mathcal{L_i}(\theta_i) = \mathbb{E} _{s,a \sim \rho(\cdot)} [y_i(\theta_i) - Q(s,a | \theta_i)]^2$

$y_i(\theta_i) = \mathbb{E}_{s' \sim \varepsilon} [r + \gamma [Q(s', max_{a'} Q(s',a' | \theta_i)| \theta_{i-1} )]$

　　2) Prioritize replay

　　　差の拡大を避けるためサンプリングの間隔を比例させています。

　　　 $\mathcal{p}_t \propto [r + \gamma \ max_{a'} [Q(s',a' | \theta_{i-1} ) ] - Q(s,a | \theta_i)]^2\$

3) Dueling netwwork

　　　DeepLearningの構成を強化学習用に変更　(意味不詳）

4) Multi-step Learning

　　　倉庫問題や迷路問題を解くため、Ｎ期先の行動価値関数を推定しています。

　　 $\mathcal{L_i}(\theta_i) = \mathbb{E} _{s,a \sim \rho(\cdot)} [y_i^N - Q(s,a | \theta_i)]^2$

　　但し、 $y_i^N= \mathbb{E}_{s' \sim \varepsilon} [\sum_n^N r _n+ \gamma^N \ max_{a'} [Q(s_i^N,a' | \theta_{i-1} )]$

5) Deistributional RL

　　　これ以外は全て行動価値関数 $Q(s,a|\theta)$ の学習(Q_learing)でしたが、

ここは唯一方策 $\pi$ の学習になります。

このアイデアはライバルAbbeel達のTRPO(Trust Region Policy)に近いものです。

　　　ここで報酬 $z$ を区間 $v_{min} \sim v_{max}$ で $N_{atoms}$ に分割して、

報酬 $z_i$ 毎に行動価値関数 $q_\theta^i(s_t,a_t|z_i)$ を求めて方策 $\pi_\theta^*$ 分布としています。

$\theta$ の損失関数 $\mathcal{L}_{s,a}(\theta)$ は前の方策 $\pi_{\theta_-1}$ と現在の $\pi_\theta$ との差としています。

$\mathcal{L}_{s,a}(\theta) = \mathcal{D}_{KL} [\pi_{\theta+1} || \pi_\theta ]$

　　　　 $\pi_{\theta+1} = p_{\theta+1} (S_{t+1},a_{t+1}|z') \ \ z'=r + \gamma \cdot z$

6) Noisy Net

　　　DQNはMontezuma’s Revengeの様な変化の多い空間で移動する様なゲームでは同じ場面を繰返して最も不得意にしていました。

　　　そこで場面に叙々に少なくなる様なノイズをいれ大局的に場面の特徴量を掴む工夫を導入しています。

f:id:mabonki0725:20170827095038p:plain

(1.1) 結果

　6個のモデルを統合したRainbowはゲームを問わず高得点を達成することを示しました。

f:id:mabonki0725:20171017161210p:plain

2017-10-15

Abbeelの対等な敵対的ロボットの論文を読む

ロボテックス確率・統計

ランニング30分　英語できず

(1) Abbeelの対等な敵対的ロボットの論文を読む

　「Continuous Adaptation via Meta-Learning in Nonstationary and Competitive Environments」https://arxiv.org/abs/1710.03641

　対等な敵対的モデルはOpen-AIの手作りのカリキュラムを利用するモデルhttps://arxiv.org/abs/1710.03748が先日投稿されましたが、この論文は正攻法で対等な敵対モデルに取り組んだものです。モデル名はRobosumoです。

　　　 f:id:mabonki0725:20171015222544p:plain

　強化学習のモデルはDeepMind(Google)対UC Barkeley(OpenAI)の両巨頭に絞られてきた感があります。DeepMindはQ-Learnig　BarkeleyはTRPOをベースにしており、どちらが「強いAI」に至るか固唾を飲んで見守っている感じがします。

(1.1) 手法

　この論文の敵対的なモデルはタスクという概念を使い２階層モデルでできています。タスクは敵対的な相手に対する戦略の様なものです。

　・１階層目　(メタ学習）前のタスク $T_{i-1}\to T_i$ の方策 $\pi_\phi$ の改善

　・２階層目　(強化学習）動作 $\tau$ の方策 $\pi_\theta$ の改善

f:id:mabonki0725:20171015221913p:plain

最適化問題は次で定式化しています。

　 $min_\theta \mathbb{E}_{T \sim D(T)} \mathcal{R}_\tau(\theta)$

$\mathcal{R}_\tau(\theta) = \mathbb{E}_{\tau_\theta^{1:K} \sim P(\tau|\theta)} [\mathbb{E}_{\tau_\phi \sim P(\tau|\phi)} \{\mathcal{L}_T(\tau_\phi) | \tau_\theta^{1:K} ,\theta \} ]$

上式は２階層の期待値で出来ていることがわかります。

　　第１階層目 $\mathbb{E}_{\tau_\phi \sim P(\tau|\phi)} \{\mathcal{L}_T(\tau_\phi) | \tau_\theta^{1:K} ,\theta \}$

　　第２階層目 $\mathbb{E}_{\tau_\theta^{1:K} \sim P(\tau|\theta)}$

ここで

$T \sim D(T)$ はタスクの分布

　　 $\mathcal{R}_\tau(\theta)$ は動作 $\tau$ での報酬

　　 $\tau_\theta^{1:K}$ は経路 $\tau_\theta^1 \sim \tau_\theta^K$

　　 $\mathcal{L}_T(\tau_\phi)$ は損失関数

上式の最適化問題の動作 $\tau$ をタスク間の動作に置き換えます。 $\tau \to T_i,T_{i+1}$

　 $min_\theta \mathbb{E}_{T \sim D(T)} \mathcal{R}_{T_i,T_{i+1}} (\theta)$

$\mathcal{R}_{T_i,T_{i+1}}(\theta) = \mathbb{E}_{\tau_\theta^{1:K} \sim P(\tau|\theta)} [\mathbb{E}_{\tau_{i+1,\phi} \sim P_{T_{i+1}}(\tau|\phi)} \{\mathcal{L}_{T+1}(\tau_{i+1},\phi) | \tau_\theta^{1:K} ,\theta \} ]$

(1.2) 結果

　試合の回数に対する足の位置での報酬の低減です。提案モデルはMLP+meta-update LSTM+meta-update が該当します。提案モデルでは報酬の低減が緩やかになっています。

f:id:mabonki0725:20171015222837p:plain

2017-10-14

安定的な動作を保持するTRPOの論文を読む

ロボテックス確率・統計

ランニングできず　英語:Toiec 30分

(1) 安定的な動作を保持するTRPOの論文を読む

　「Trust Region Policy Optimization」https://arxiv.org/abs/1502.05477

この論文はロボットの強化学習で革新的な貢献をしたモデルです。UC Berkeleyのロボットチームの Shulmanが2015年にICMLで発表しました。

　ロボットの制御で必ずコストが低くなる（報酬が高くなる）信頼範囲(Trust Region)で方策 $\pi_\theta$ を改善していくアイデアです。

f:id:mabonki0725:20171014234339p:plain

当然このTrust Region内で維持していくには、細かい行動する制限が加わることになりますが、これによって複雑な機械がスムーズに動作できることを実現しました。

(1.1) 手法

　ここでは報酬 $r$ の代わりにコスト $c=-r$ で考えます。

　一般化利益関数 $A(s,a)$ (Generalized Advantage Estimation)は行動 $a$ によって受ける利益（ここではコスト削減）を示します。

　　　 $A_{\pi_\theta}(s,a) = Q_{\pi_\theta}(s,a) - V_{\pi_\theta}(s)$

ここで

　　　　 $s$ は状況

　　　　 $V_\pi(s)$ は状況 $s$ の価値

　　　　 $Q_\pi(s,a)$ は状況 $s$ で行動 $a$ を採った後の価値

　そこで、異なる方策 $\tilde{\pi}$ を採った場合の改善度 $\eta$ は次のとなります。

　　　 $\eta(\tilde{\pi}) = \eta(\pi) + \sum_s \rho_{\tilde{\pi}}(s) \sum_a \tilde{\pi}(a|s) A_\pi(s,a)$

但し、 $\rho_{\tilde{\pi}}(s)=P(s_0 = s) + \gamma P(s_1=s) + \dots + \gamma^t P(s_t = s)$

この式より $\sum_a \tilde{\pi}(a|s) A_\pi(s,a) \lt 0$ なら必ずコスト削減になって改善することができます。

　それではコスト削減ができる範囲で最大の $a$ を探っていけば、安定した制御ができる事になります。

この用件をTRPOでは次の制約付最適問題で更新規則を実現しています。

　　　 $\mathcal{L}(\pi_\theta) = \theta_{new} = argmin_\theta [ \eta(\pi_{\theta_{old}}) + \sum_s \rho_{\pi_\theta}(s) \sum_a \pi_\theta(a|s) A_{\pi_{\theta_{old}}}(s,a)]$

$s.t. \ \ \mathcal{D}_{KL} (\theta_{new} || \theta_{old}) \lt \epsilon$ 　　

　　　ここで $\epsilon$ は信頼境界への制限を示していますが。模擬にて適切な値が決定されます。

2017-10-13

一般化報酬による高次元の強化学習の論文を読む

ロボテックス確率・統計

ランニングできず　英語できず

(1) 一般化報酬による高次元の強化学習の論文を読む

「High - Dimensional Continuous Control using Generated Advantage Estimation」

https://arxiv.org/abs/1506.02438

　ゲームの強化学習ではQ-learningが一般的ですが、人間型のヒユーマロイド型ロボットでは複雑で高次元の制御が必要なため、この強化学習では方策 $\pi$ が適正拘束条件下の最適化で行うことが多いです。

f:id:mabonki0725:20171014000943p:plain

　https://youtu.be/Pvw28wPEWEo

　このモデルとしてはUC BerkelyのAbbeel率いるロボット研究グループのShulmanが編み出したTRPO(Trust Region Policy Optimization)が多く使われ実績を残しています。

　この論文は一般化報酬(GAE：Generated Advantage Estimation)を使ったTRPOモデルのアルゴリズムについて述べています。しかしこのGAE自体はSuttonのTD法で既にモデル化されているもので新しいものではありません。

　Suttonの偉大な面は数多くありますが、強化学習のBellman方程式が将来への無限の漸化式で本来は解けないものを、非常に簡単な式で表現して繰返し学習によって精緻化できることを示した事が最大の功績です。これが深層学習と合体して今のAlpha碁になっています。

方策 $\pi_\theta$ は将来の報酬 $r(s_t)$ の累計の期待値の最大化で最適化されます。

　　 $-\mathcal{L}(\theta,s_0) = \mathbb{E}_{\pi_\theta} [\sum_{t=0}^\infty \gamma r(s_t) ]$

　よってこれを微分してSGDで最適化することが一般的です。

$\frac{\partial \mathcal{L}(\theta,s_0)}{\partial \theta} = \sum_s \mu_{\pi_\theta}(s|s_0) \sum_a \frac{\partial \pi_\theta(a|s)}{\partial \theta} A_{\pi_\theta}(s,a)$

但し、 $\mu_{\pi_\theta} = \sum_{t=0}^\infty \gamma^t P(s_t = s|s_0)$

ここで $A_{\pi_\theta}(s,a)$ はGAEにあたります。

　このARGはSuttonの有名なTD(λ)によって次式となります。

$A^{ARG(\gamma,\lambda)} = \sum_{i=0}^\infty (\gamma \lambda)^i \delta_{t+i}$

　　ここで

　　　 $\gamma \ \lambda$ は割引係数とλ係数です

　　　 $\delta_t$ は価値関数 $V$ の増分 $\gamma V(s_{t+1}) + r_t - V(s_t)$

ARGは価値関数の増分 $\delta_t$ の累計なので、これは動作経路（観察データ）から得られます。

　これを使って最適な $\pi_\theta$ を求めるアルゴリズムが以下となります。　

f:id:mabonki0725:20171014004714p:plain

2017-10-12

複数人が競争する環境での強化学習の論文を読む

確率・統計ロボテックス AI論文

ランニングできず　英語できず

(1) 複数人が競争する環境での強化学習の論文を読む

「Emergent Complexity via Multi-Agent Competition」https://arxiv.org/abs/1710.03748

　複数の学習者が競争する環境は設定し易い環境ですが、強化学習にとっては最も複雑な環境となります。この論文では競争者が巧手であれば学習者が最も効果的に学習できる場としています。

　下記はOpenAIの３Ｄで実装できた競争の強化学習です。

f:id:mabonki0725:20171012225945p:plain

https://sites.google.com/view/multi-agent-competition

　このモデルの特徴は初期時には設計された動作をする様にカリキュラムを導入していて、除々に勝負に関わる学習に移行できる様にしています。

(1.1) 手法

　1) 学習モデル

　　競争モデルのはずですが、学習モデルは一般の方策 $\pi_\theta$ のパラメータ $\theta$ を最適化するPPO(Proximal Policy Optimization)モデルとなっています。

　　PPOは次の最適化問題

　　　 $max_\theta \ \ \mathbb{E}_t [\frac{\pi_{\theta_{old}}(a_t|s_t)} {\pi_\theta(a_t|s_t)} \cdot A_t ]$

　　　 $s.t.$

　　　 $\mathcal{L}(\theta) =\mathbb{E}_t [ \mathcal{KL} \{ \pi_{\theta_{old}} (a_t|s_t) || \pi_\theta(a_t,s_t) \}] \lt \delta$

　ここで $A_t$ は一般評価利益(GAE)です

　　　　 $A_t = Q_{\pi_\theta}(a_t,s_t) - V_{\pi_\theta}(s_t)$

　この最適化問題は次の深層学習で解いています(詳細不明)

　　MLP:価値に関する方策 $\pi_\theta$ と価値関数 $Q_{\pi_\theta}(a_t,s_t)$

LSTM:時間に関する方策 $\pi_\theta$

　2) カリキュラムの導入

　初期の動作訓練のためカリキュラムを導入しています。これは時間が経過するとに消滅する人工的な報酬で実現しています。

　　即ち、初期はカリキュラムに沿った動きをしますが、時間の経過と共に本来の勝負の報酬で学習する様になっています。

　　時間の経過する報酬は次のもので、焼き鈍し係数 $\alpha$ が零になると本来の勝負の報酬 $R$ のみなります。

　　詳細はAppendix Aにある様に課題毎に設定します。

　　　　 $r_t = \alpha_t s_t + (1-\alpha_t) \mathbb{I} [ t == T]R$

ここで

$\alpha$ は時間の経過で消滅する焼き鈍し係数

$R$ は勝負が尽いた場合の報酬

$s_t$ は状況で下記を対象としています。

　　　　・ゴールまでの距離

　　　　・x方向の速度

　　　　・制御のコスト

　　　　・衝撃コスト

　　　　・不倒の報酬

(1.2) 結果

　最初はカリキュラムに沿って動くので、カリキュラムでの学習度で差がでる場合があります。

　(a)の人間型の相撲では最初は同じレベルでしたが、差が除々に拡大しています。しかし(b)の蟻型の相撲ではカリキュラム時の差から反対に叙々に縮まっています。

　サーカーでは２パターンの様子があり、このモデルは安定していない事がわかります。

f:id:mabonki0725:20171013061729p:plain

2017-10-11

難易度が高いゴールを自動的に見つける強化学習

ロボテックス AI論文

ランニング30分　英語できず

(1) 難易度が高いゴールを自動的に見つける強化学習

「Automatic Goal Generation for Reinforcement Learning Agents」 https://arxiv.org/abs/1705.06366

　この論文には米国のロボット学の権威 Abbeel が参加しています。このモデルはGANを使うことでより難易度が高いゴールを学習します。　モデル名(Goal GAN)

(1.1) 手法

　難易度が異なる複数のゴールがある場合、ＧＡＮの構成によってその難易度を識別してより困難なゴールを探索します。

　識別器では探索されたゴールについて以下のことをします。

　　・他の達成された方策でこのゴールに達成できるか識別

　　・達成できない場合は強化学習して達成しようとします

　　・達成された場合、生成器に難易度が高いゴールを探索させます

　　・達成できない場合、生成器に難易度を下げたゴールを探索させます。

　このサイクルの循環は簡単な課題から難しい課題に進むカリキュラムを生成していることになります

f:id:mabonki0725:20171012071453p:plain

(1.2) 実験

　蟻型ロボットがＵ字路で反対側に移動する実験をこのモデルで行っています。この場合、ゴールはガウス分布で生成しています。

　　　　 f:id:mabonki0725:20171011233933p:plain

　この試行を繰り返すと叙々に反対側に移動できていることがわかります。

　この実験では次の報酬を与えているだけで、より負荷がかかる遠い距離の移動を実現しています。

　　・壁を越えるのは低い報酬

　　・通路歩行は高い報酬

f:id:mabonki0725:20171011234258p:plain