強化学習理論のまとめ（その2）です。その1（強化学習の一般的な定義から方策勾配法まで）は以下から。
DPG
方策は現在の状態sでの行動aに対する確率分布としてモデル化されますが、Deterministic policy gradient (DPG)は、決定的な行動
として方策がモデル化されます。
論文にある記載の通りに定義していきます。
: 初期の状態分布
: 状態sからs'にk step変化したときの状態分布
このように定義すると、時間割引された状態分布は下式となります。
\begin{align} \rho^{\mu}(s') = \int_{\mathcal{S}} \sum_{k=0}^{\infty} \gamma^{k} \rho_0 (s) \rho^{\mu}(s → s', k)ds \end{align}
このとき最適化するための目的関数は以下の通りです。 \begin{align} J(\theta) = \int_{\mathcal{S}} \rho^{\mu}(s)Q(s, \mu_{\theta}(s))ds \end{align}
Deterministicのときの方策勾配定理は、上式をパラメータで微分し得られます。
\begin{align} \nabla_{\theta} J(\theta) &= \int_{\mathcal{S}} \rho^{\mu}(s) \nabla_{a} Q^{\mu}(s, a) \nabla_{\theta} \mu_{\theta}(s) |_{a=\mu_{\theta}(s)}ds \\ &= \mathbb{E}_{s \sim \rho^{\mu}} [\nabla_{a} Q^{\mu}(s,a)\nabla_{\theta} \mu_{\theta}(s) |_{a=\mu_{\theta}(s)} ] \end{align}
決定的な方策を確率的な方策の特別な場合と考えることができます。DPGの論文
では確率的な方策は、決定的な方策
とバリエーション
で表現され、
とすれば決定的な方策と同一の式になります。
例としてDPGをon policy actor-critic with SARSAとして適用してみます。SARSAは以下の方策の更新式によって行動を決定するようになります。
\begin{align} \delta_t &= R_t + \gamma Q_w (s_{t+1}, a_{t+1}) - Q_w (s_t, a_t) \\ w_{t+1} &= w_t + \alpha_w \delta_t \nabla_w Q_w (s_t, a_t) \\ \theta_{t+1} &= \theta_t + \alpha_{\theta} \nabla_w Q_w (s_t, a_t)\nabla_{\theta} \mu_{\theta}(s) |_{a=\mu_{\theta}(s)} \end{align}
1式目がSARSAのTD誤差を表します。2式目は、TD誤差が得られた時のQ関数の勾配からQ関数のパラメータwを更新します。3式目が、Deterministic policy gradient (DPG)です。
しかし、環境に十分なノイズがなければ、決定的な方策のため十分な探索を宝生することは困難です。そこで方策にノイズを加えることもできます。これはoff-policyのアプローチになります。確率的方策を導入します。
\begin{align} J(\theta) &= \int_{\mathcal{S}} \rho^{\beta}(s)Q(s, \mu_{\theta}(s))ds \\ \nabla_{\theta} J(\theta) &= \mathbb{E}_{s \sim \rho^{\beta}} [\nabla_{a} Q^{\mu}(s,a)\nabla_{\theta} \mu_{\theta}(s) |_{a=\mu_{\theta}(s)} ] \end{align}
ポリシーが決定的であるので、方策勾配定理でのではなく、状態sでの期待される報酬
だけが必要なのがポイントです。行動によりません。off-policyのアプローチでは、行動とターゲット間でのずれを解消するために重点サンプリングがよく用いられます。しかし、行動に対する積分がないため、重点サンプリングせずとも求められます。
DDPG
DDPG (Lillicrap, et al., 2015) Deep Deterministic Policy GradientはDPGとDQNを組み合わせたoff-policyなactor criticアルゴリズムです。 DQN (Deep Q-Network)はexperience replayとtarget networkの固定によりQ関数の学習を安定化させています。DQNは離散空間で動きますが、DDPGは連続空間で動くアルゴリズムです。
よりよい探索を行うため、探索方策はノイズ
を加えることで構築されます。
\begin{align} \mu'(s) = \mu_\theta (s) + \mathcal{N} \end{align}
加えて、DDPGはsoft update (conservative policy iteration)によるACのパラメータが更新されます。一連の流れは以下のようになります。
critic updateはtarget networkとQ値のMSEを最小化させることで更新します。
\begin{align} y_i &= r_{i} + \gamma Q'(s_{i+1}, \mu'(s_{i+1} | \theta^{\mu'}) | \theta^{Q}) \\ L &= \frac{1}{N} \sum_i (y_i - Q(s_i, a_i | \theta^{Q}) )^{2 } \end{align}
次のactor updateは方策勾配法を用います。
\begin{align} \nabla_{\theta} J(\theta) \approx \frac{1}{N}\sum_{i} [\nabla_{a} Q(s,a | \theta^{\mu})\nabla_{\theta} \mu_{\theta^{\mu}}(s) |_{a=\mu_{\theta}(s)} ] \end{align}
target networkの更新は次の式です。
\begin{align} \theta^{Q'} = τ \theta^{Q} + (1-τ) \theta^{Q'} \\ \theta^{\mu'} = τ \theta^{\mu} + (1-τ ) \theta^{\mu'} \end{align}
ここで、です。このようにtarget networkの値を制約することで、方策はゆるく変化します。一連のDDPGのアルゴリズムは下記のようになります。
D4PG
Distributed Distributional DDPGはDDPGに分布を追加することでDDPGを改善した方法になります。
※ 1. Distributional Critic criticはwでパラメタライズさら分布Zを用いてサンプリングし、Q関数の期待値を推定します。したがって、Q関数を次のように表現できます。
\begin{align} Q_w (s, a ) = \mathbb{E}Z_w(x, a) \end{align}
分布のパラメータを学習するための損失は2つの分布間距離を最小化するように決めます。distributional TD errorを定義します。
\begin{align} L(w) = \mathbb{E} [d (\mathcal{T}_{\mu_{\theta}}, Z_{w'}(s, a), Z_{w}(s, a) ] \end{align}
ここではベルマンオペレータです。決定的な方策勾配は
\begin{align} \nabla_{\theta} J(\theta) \approx \mathbb{E}_{\rho^{\mu}}[\nabla_{a} Q(s,a)\nabla_{\theta} \mu_{\theta}(s) |_{a=\mu_{\theta}(s)} ] \\ =\mathbb{E}_{\rho^{\mu}}[\mathbb{E} [\nabla_{a} Q(s,a)] \nabla_{\theta} \mu_{\theta}(s) |_{a=\mu_{\theta}(s)} ] \end{align}
1式目は、方策勾配法です。2式目はQ値分布の期待値です。
※ 2. N-step報酬 TD誤差を計算するとき、D4PGは報酬の先読みを1stepではなくN-step TD targetを計算します。
\begin{align} Y_i = r(s_0, a_0) + \mathbb{E} [\sum_{n=1}^{N-1} r(s_n, a_n) + \gamma^{N} Q(s_N, \mu_{\theta}(s_N) |s_0, a_0] \end{align}
※ 3. Multiple Distributed Parallel Actors D4PGはKの独立なactorを用いて、並列で経験を集め、同じreplay bufferにデータをフィードします。
※ 4. Prioritized Experience Replay (PER)
最後に一様分布でない分布とともにreplay buffer Rからサンプリングします。重点サンプリングの重みを
としています。
MADDPG
Multi-agent DDPG (MADDPG)はDDPGをmulti agentに対応させたものです。1つのagentの視点において、環境は静止していません。他のagentの方策はすぐに更新され、その方策は未知のままになってしまいます。MADDPGはそのような環境変化とagent間の相互作用を扱うためのactor-criticモデルになっています。
この問題はMDP, a.k.a Markov gamesにおけるマルチエージェントで定式化できます。それぞれの状態セットSでN agents存在すると仮定します。方策パラメータを, 行動セット
と観測セット
を持っています。状態遷移関数はすべての状態、行動、そして観測空間
に関わっています。一方、各agentの確率的方策は自身の状態と行動にのみ関連し、
]で記載されます。自身の観測を所与とする行動に対する確率分布、決定的な方策は、
です。
MADDPGのcriticは中央化された行動価値関数を学習します。決定方策、観測、行動はそれぞれベクトルのボールド表記で記載しています（
など)。各Qは別々に学習されることで、複数のagentは任意の報酬構造を持つことができます。一方、複数のactorは自身の持つパラメータ
を探索・更新していきます。
- actorの更新のための勾配
\begin{align} \nabla_{\theta_i} J(\theta) = \mathbb{E}_{\mathbf{o}, a \sim \mathcal{D}}[\nabla_{a_i} Q_i^{\vec{\mu}}(\mathbf{o},\mathbf{a})\nabla_{\theta_i} \vec{\mu}_{\theta_i}(o_i) |_{a_i=\vec{\mu}_{\theta_i}(o_i)} ] \\ \end{align}
ここで、はexperience replay bufferです。全てのagentの経験
を含んでいます。
- criticの更新（中央化された行動価値関数の更新）
\begin{align} L(\theta_i) &= \mathbb{E}_{\mathbf{o}, \mathbf{a}, \mathbf{r}, \mathbb{o'}} [(Q_{i}^{\vec{\mu}}(\mathbf{o}, \mathbf{a} ) - y)^{2}] \\ y &= r_i + \gamma Q_i^{\vec{\mu'}} (\mathbf{o'},\mathbf{a'}) \end{align}
ここで、はソフトアップデートされたtarget policyです。概略図を下図に示します。
他のagentからの方策の推論や、方策アンサンブルなども提案されています。他のagentの方策を知っているという前提を除くために、近似の方策を導入時します。これを用いるとagentの対数分布とエントロピーHの正則化を追加すると下式になります。
\begin{align} L(\phi_i^{j}) & = - \mathbb{E}_{o_j, a_j} [\log \vec{\mu}_{i}^{j} (a_j | o_j) + \lambda H(\vec{\mu}_{i}^{j})] \\ \hat{y} &= r_i + \gamma Q_i^{\vec{\mu'}} (\mathbf{o'},\vec{\mu_i}(\mathbf{o})) \end{align}
参考・引用文献
主に以下のサイトを参考にさせて頂きました。実装例はOpen AIのbaselineに大体あります。 大方まとまってきたら、改めてコンパイルしたいと思います。
