WIP 強化学習

reinforcement-learning

TDMC (λ)

アルゴリズム

  1. 終局まで仮想プレイする。
  2. 学習エピソードの末端局面 $p_{T}$ を除くすべての局面 $p_{t}$ について
  3. 静的評価値 $V(p_{t}) = \vec{w}^{\top} \Psi(p_{t})$ を計算。ここで、$\Psi(p)$ は局面 $p$ の特徴ベクトル。
  4. 収益 $R_{t} = \sum_{i=t}^{T} \gamma^{i-t} r_{i}$ を計算。ここで $r_{t}$ は局面 $p_{t}$ からプレイアウトして得られた勝率の近似値 (勝ち 1、負け -1、引き分け 0)。
  5. $n$ ステップ収益 $R_{t}^{(n)} = \sum_{i=t}^{t+n-1} \gamma^{i-t} r_{i} + V(p_{t+n})$ を計算。
  6. $\lambda$ 収益 $R_{t}^{\lambda} = \lambda^{T-t-1} R_{t} + \sum_{n=1}^{T-t-1} \lambda^{n-1} R_{t}^{(n)}$ を計算。
  7. 重みを更新する: $\vec{w} \leftarrow \vec{w} + \alpha \sum_{t=1}^{T-1} \left[ R_{t}^{\lambda} - V(p_{t}) \right] \nabla_{\vec{w}} V(p_{t})$

$\gamma$ は割引率、$\lambda$ は適格度、$\alpha$ は学習率、いずれも 0 ~ 1 の範囲で設定する (学習率が 0 はだめ)。

参考文献

  1. 大崎泰寛, 柴原一友, 但馬康宏, 小谷善行. 2008. TDMC(λ)に基づく評価関数の調整. ゲームプログラミングワークショップ2008論文集, Vol. 2008, No. 11, pp. 73-79.

LMS-MC と TD-MC

最小自乗 (LMS; Least Mean Squares) 法と時間差分 (TD; Temporal-Difference) 法にモンテカルロ法を応用した手法 LMS-MC と TD-MC のメモ。

LMS-MC

アルゴリズムは

  1. 終局まで仮想プレイする。
  2. 学習エピソードの末端局面 $p_{T}$ を除くすべての局面 $p_{t}$ で、静的評価値をシグモイド関数にかけた値 $r_{t} = \sigma(\vec{w}^{\top} \Psi(p_{t}))$ を得る。ここで、$\Psi(p)$ は局面 $p$ の特徴ベクトル。
  3. それらの局面での勝率をモンテカルロ法 (プレイアウト) で計算して $R_{t}$ と置く。
  4. 学習率 $\alpha$ で重みベクトルを更新する: $\vec{w} \leftarrow \vec{w} + \alpha \sum_{t=1}^{T-1} \left[ (R_{t} - r_{t}) \nabla_{\vec{w}} r_{t} \right]$

となる。

これは目的関数 $E_\textrm{LMS-MC} = \sum_{t=1}^{T-1} (R_{t} - r_{t})^2$ を最小化している。

TD-MC

LMS-MC とは最後の更新式が異なるだけである。

\vec{w} \leftarrow \vec{w} + \alpha \sum_{t=1}^{T-1} \left[ (R_{t+1} - r_{t}) \sum_{i=1}^{t} \lambda^{t-i} \nabla_{\vec{w}} r_{i} \right]

これは目的関数 $E_{\textrm{TD-MC}} = \sum_{t=1}^{T-1} (R_{t+1} - r_{t})^2$ を最小化している。

備考

単に勝率に近づけると考えて、目的関数として負の交差エントロピーを最大化してもいいとおもう。そうすると更新式は、たとえば

\vec{w} \leftarrow \vec{w} + \alpha \sum_{t=1}^{T-1} (R_{t} - r_{t})  \Psi(p_{t})

となる。

参考文献

  1. 大崎泰寛, 柴原一友, 但馬康宏, 小谷善行. 2008. モンテカルロシミュレーションを用いた強化学習法の提案. 情報処理学会研究報告, ゲーム情報学, Vol. 2008, No. 28, pp. 27-44.
  2. 大崎泰寛, 柴原一友, 但馬康宏, 小谷善行. 2007. TD(λ)-MC 法を用いた評価関数の強化学習. ゲームプログラミングワークショップ2007論文集, Vol. 2007, No. 12, pp. 36-43.

Asynchronous methods for deep reinforcement learning

  • Volodymyr Mnih, Adrià Puigdomènech Badia, Mehdi Mirza, Alex Graves, Timothy P. Lillicrap, Tim Harley, David Silver, Koray Kavukcuoglu
  • https://arxiv.org/abs/1602.01783
\begin{aligned}
\delta\theta_{\pi} &= \partial_{\theta_{\pi}} \left(R - V(s_{i}; \theta_{\pi})\right) \ln \pi(a_{i} \mid s_{i}; \theta_{\pi}) \\
\delta\theta_{V} &= \partial_{\theta_{V}} \frac{1}{2} \left(R - V(s_{i}; \theta_{V}) \right)^{2}
\end{aligned}
// initialize global variables
global_t = 0;
global_p = 0; // polnet parameters
global_v = 0; // valnet parameters
t = 1;
while (global_t < global_t_max) {
  // reset gradients
  grad_p = 0;
  grad_v = 0;

  // sync parameters
  p = global_p;
  v = global_v;

  t_start = t;
  s_t = get_state(t);

  for (;;) {
    a_t = sample(s_t, p);
    tie(r[t], s_t) = observe(s_t, a_t)
    ++t, ++global_t;
    if (is_terminal(s_t) || (t - t_start > t_max)) {
      break;
    }
  }
  R = is_terminal(s_t) ? 0 : V(s_t, v);

  while (t --> t_start) {
    R = r[t] + gamma * R;
    grad_p += (1)
    grad_v += (2)
  }

  // update by gradients
  global_p += alpha * grad_p;
  global_v += alpha * grad_v;
}

Reinforcement learning with unsupervised auxiliary tasks

  • Max Jaderberg, Volodymyr Mnih, Wojciech Marian Czarnecki, Tom Schaul, Joel Z Leibo, David Silver, Koray Kavukcuoglu
  • https://arxiv.org/abs/1611.05397

あとで書く

Loss is its own reward: self-supervision for reinforcement learning

  • Evan Shelhamer, Parsa Mahmoudieh, Max Argus, Trevor Darrell
  • https://arxiv.org/abs/1612.07307

あとで書く

REBAR: Low-variance, unbiased gradient estimates for discrete latent variable models

  • George Tucker, Andriy Mnih, Chris J. Maddison, Jascha Sohl-Dickstein
  • https://arxiv.org/abs/1703.07370

あとで書く

Bridging the gap between value and policy based reinforcement learning

  • Ofir Nachum, Mohammad Norouzi, Kelvin Xu, Dale Schuurmans
  • https://arxiv.org/abs/1702.08892
\prod_{i=0}^{T-1} \pi^{*}(a_{i} \mid s_{i}) \propto \exp \sum_{i=0}^{T-1} \frac{r_{i}}{\tau}

average, hardmax, softmax:

\begin{aligned}
Q^{\pi}(s, a) &= r(s, a) + \gamma \sum_{a' \in s'} \pi(a' \mid s') Q^{\pi}(s', a') \\
              &= r(s, a) + \gamma \mathbb{E}_{\pi(a' \mid s')} Q^{\pi}(s', a') \\
              &= r(s, a) + \gamma V^{\pi}(s') \\
Q^{\circ}(s, a) &= r(s, a) + \gamma \max_{a' \in s'} Q^{\circ}(s', a') \\
                &= r(s, a) + \gamma V^{\circ}(s') \\
Q^{*}(s, a) &= r(s, a) + \gamma \tau \ln \sum_{a' \in s'} \exp \frac{Q^{*}(s', a')}{\tau} \\
            &= r(s, a) + \gamma V^{*}(s')
\end{aligned}
\pi^{*}(a \mid s) \propto \exp \frac{Q^{*}(s, a)}{\tau}

備考

$\tau \rightarrow +0$ のとき

\begin{aligned}
\tau \ln \sum_{i} \exp \frac{Q(s, a_{i})}{\tau}
 &= \tau \ln \left\{ \exp \frac{Q^{*}(s)}{\tau} \sum_{i} \exp \frac{Q(s, a_{i}) - Q^{*}(s)}{\tau} \right\} \\
 &= \tau \ln \exp \frac{Q^{*}(s)}{\tau} + \tau \ln \sum_{i} \exp \frac{Q(s, a_{i}) - Q^{*}(s)}{\tau} \\
 &= \ln \exp Q^{*}(s) + \tau \ln \sum_{i} \exp \frac{Q(s, a_{i}) - Q^{*}(s)}{\tau} \\
 &= Q^{*}(s) + \tau \ln \sum_{i} \exp \frac{Q(s, a_{i}) - Q^{*}(s)}{\tau} \\
 &= Q^{*}(s)
\end{aligned}

となる。ここで $Q^{*}(s) = \max_{i} Q(s, a_{i})$ と置いた。また $\tau \rightarrow +0$ より、$Q(s, a_{i}) = Q^{*}(s)$ のとき $\frac{Q(s, a_{i}) - Q^{*}(s)}{\tau} \rightarrow 0$、$Q(s, a_{i}) \neq Q^{*}(s)$ のとき $\frac{Q(s, a_{i}) - Q^{*}(s)}{\tau} \rightarrow -\infty$ となるので、$\sum_{i} \exp \frac{Q(s, a_{i}) - Q^{*}(s)}{\tau} \rightarrow 1$ となり、結局 $\tau \ln \sum_{i} \exp \frac{Q(s, a_{i}) - Q^{*}(s)}{\tau} \rightarrow 0$ となる。 ___

等式

\tau \ln \pi(a\mid s) = r(s,a) + \gamma V(s') - V(s)

より

\begin{aligned}
\sum_{i} \pi(a_{i} \mid s) V(s)
 &= \sum_{i} \pi(a_{i} \mid s) \left\{
      r(s, a_{i}) + \gamma V(s') - \tau \ln \pi(a_{i} \mid s)
    \right\}
 \\
 &= \sum_{i} \pi(a_{i} \mid s) \left\{
      \tau \ln \exp \frac{r(s, a_{i}) + \gamma V(s')}{\tau} - \tau \ln \pi(a_{i} \mid s)
    \right\}
 \\
 &= -\tau \sum_{i} \pi(a_{i} \mid s) \left\{
      -\ln \exp \frac{r(s, a_{i}) + \gamma V(s')}{\tau} + \ln \pi(a_{i} \mid s)
    \right\}
 \\
 &= -\tau \sum_{i} \pi(a_{i} \mid s) \left\{
      \ln \frac{\pi(a_{i} \mid s)}{\exp \frac{r(s, a_{i}) + \gamma V(s')}{\tau}}
    \right\}
\end{aligned}

となる。

Equivalence between policy gradients and soft Q-Learning

  • John Schulman, Pieter Abbeel, Xi Chen
  • https://arxiv.org/abs/1704.06440

あとで書く

Infinite time horizon maximum causal entropy inverse reinforcement learning

  • Michael Bloem, Nicholas Bambos
  • https://www.semanticscholar.org/paper/Infinite-time-horizon-maximum-causal-entropy-Bloem-Bambos/ac7e39ec0ebb572a7ff52b694fd93139cea29052

定義

割引因果エントロピー (discounted causal entropy)

\mathcal{H}^{\beta}(A_{0:\infty} \parallel S_{0:\infty})
  = \mathbb{E}_{P_{0}, P, \pi} \left[
      \sum_{t=0}^{\infty} -\beta^{t} \ln \pi(A_{t} \mid S_{0:t}, A_{0:t-1})
    \right]
  • $s$: 状態
  • $a$: 行動
  • $t$: 時刻
  • $P_{0}$: 初期状態の分布 $s_{0} \sim P_{0}$
  • $P(S_{t+1} \mid S_{0:t}, A_{0:t})$: 状態遷移確率 $s_{t+1} \sim P(s_{t}, a_{t})$
  • $\pi(A_{t} \mid S_{0:t}, A_{0:t-1})$: 方策 $a_{t} \sim \pi(s_{0:t}, a_{0:t-1})$
  • $\beta$: 割引率 $\beta \in (0, 1)$

参考文献

  1. Michael Bloem and Nicholas Bambos. 2014. Infinite time horizon maximum causal entropy inverse reinforcement learning.

Maximum entropy deep inverse reinforcement learning

  • Markus Wulfmeier, Peter Ondruska, Ingmar Posner
  • https://arxiv.org/abs/1507.04888

あとで書く

A connection between generative adversarial networks, inverse reinforcement learning, and energy-based models

  • Chelsea Finn, Paul Christiano, Pieter Abbeel, Sergey Levine
  • https://arxiv.org/abs/1611.03852
    • https://twitter.com/mabonki0725/status/851287884753588226
    • https://twitter.com/dosei_sanga/status/851299905062658048
    • https://www.slideshare.net/takato_horii/3nips

あとで書く

Generative adversarial imitation learning

  • Jonathan Ho, Stefano Ermon
  • https://arxiv.org/abs/1606.03476
    • https://www.slideshare.net/DeepLearningJP2016/dlgenerative-adversarial-imitation-learning
    • https://speakerdeck.com/takoika/lun-wen-shao-jie-generative-adversarial-imitation-learning

あとで書く

Adversarial attacks on neural network policies

  • Sandy Huang, Nicolas Papernot, Ian Goodfellow, Yan Duan, Pieter Abbeel
  • https://arxiv.org/abs/1702.02284
  • http://rll.berkeley.edu/adversarial/

あとで書く

Evolution strategies as a scalable alternative to reinforcement learning

  • イテレーション: 世代 (generation)
  • パラメータベクトル: 遺伝子 (genotype) $\theta$
  • 目的関数: 適応度 (fitness) $F(\theta)$
  • パラメータ $\theta$ の分布 $p_{\psi}(\theta)$ ($\psi$ ハイパーパラメータ)
  • 適応度の期待値 $\eta(\psi)$
\begin{aligned}
\eta(\psi)
 &= \mathbb{E}_{\theta \sim p_{\psi}}[F(\theta)]
 \\

\nabla_{\psi} \eta(\psi)
 &= \mathbb{E}_{\theta \sim p_{\psi}}\left[
      F(\theta) \nabla_{\psi} \ln p_{\psi}(\theta)
    \right]
\end{aligned}

$\theta$ が現在の値のまわりの正規分布 $\mathcal{N}(\theta, \sigma I)$ に従うとすると、$\mathbb{E}_{\epsilon \sim N(0,I)}\left[\frac{F(\theta)}{\sigma} \epsilon \right] = 0$ より

\begin{aligned}
\eta(\theta)
 &= \mathbb{E}_{\epsilon \sim \mathcal{N}(0, I)}\left[
      F(\theta + \sigma \epsilon)
    \right]
 \\

\nabla_{\theta} \eta(\theta)
 &= \mathbb{E}_{\epsilon \sim \mathcal{N}(0, I)}\left[
      \frac{F(\theta + \sigma \epsilon) - F(\theta)}{\sigma} \epsilon
    \right]
 \\
 &= \frac{1}{\sigma} \mathbb{E}_{\epsilon \sim \mathcal{N}(0, I)}\left[
      F(\theta + \sigma \epsilon) \epsilon
    \right]
\end{aligned}

となる。

"""
alpha: 学習率
theta: 方策のパラメータ
dim: パラメータ数
sigma: ノイズの標準偏差
N: 世代数
n: 遺伝子数
"""
beta = alpha / (n * sigma)
for t in range(epochs):
    # 変位量をサンプリング
    epsilon = np.random.randn(n, dim)

    # 評価
    for i in range(n):
        F[i] = F(theta + sigma * epsilon[i])

    # 適応度の白色化
    F = (F - np.mean(F)) / np.std(F)

    # 更新
    theta += beta * np.dot(epsilon.T, F)
"""
alpha: 学習率
theta: 方策のパラメータ
sigma: ノイズの標準偏差
N: 世代数
n: 遺伝子数

乱数シードはすべてのノードで共有しておく
"""
beta = alpha / (n * sigma)
for t in range(epochs):
    # 変位量をサンプリング
    epsilon = np.random.randn(n, dim)

    # 評価
    F[rank] = F(theta + sigma * epsilon[rank])
    MPI_Allgather(F)

    # 適応度の白色化
    F = (F - np.mean(F)) / np.std(F)

    # 更新
    theta += beta * np.dot(epsilon.T, F)

備考

方策 $\pi_{\theta}$ を使ったときの報酬 $R$ の期待値は

\mathbb{E}_{\pi_{\theta}}[R] \approx \frac{1}{N} \sum_{i=1}^{N} \pi_{\theta}(X_{i}) R_{i}

となる。勾配は

\begin{aligned}
\nabla_{\theta} \mathbb{E}_{\pi_{\theta}}[R]
 &\approx \frac{1}{N} \sum_{i=1}^{N} \nabla_{\theta} \pi_{\theta}(X_{i}) R_{i}
 \\
 &= \frac{1}{N} \sum_{i=1}^{N} \frac{\pi_{\theta}(X_{i})}{\pi_{\theta}(X_{i})} \nabla_{\theta} \pi_{\theta}(X_{i}) R_{i}
 \\
 &= \frac{1}{N} \sum_{i=1}^{N} \pi_{\theta}(X_{i}) \frac{\nabla_{\theta} \pi_{\theta}(X_{i})}{\pi_{\theta}(X_{i})} R_{i}
 \\
 &= \frac{1}{N} \sum_{i=1}^{N} \pi_{\theta}(X_{i}) \nabla_{\theta} \ln \pi_{\theta}(X_{i}) R_{i}
 \\
 &= \mathbb{E}_{\pi_{\theta}}[R \ln \pi_{\theta}(x)]
\end{aligned}

参考文献

  1. Tim Salimans, Jonathan Ho, Xi Chen, Ilya Sutskever. 2017. Evolution strategies as a scalable alternative to reinforcement learning.
  2. Evolution Strategies as a Scalable Alternative to Reinforcement Learning

状態価値関数の先読み正則化付き学習

状態価値関数 (勝率予測関数、たとえば人工神経回路網で構成) のロス関数

\begin{aligned}
\mathcal{L}\left(\left\{(s_{i}, t_{i}) \right\}_{i}\right)
 &= \sum_{i} \mathcal{L}_{i}\left(s_{i}, t_{i} \right)
 \\
 &= \sum_{i} t_{i} \ln v_{i} + (1 - t_{i}) \ln(1 - v_{i})
\end{aligned}
  • $s_{i}$: $i$ 番目の局面
  • $t_{i}$: $i$ 番目の局面から対局したときの勝敗
  • $v_{i} = v(s_{i}) = \varsigma(f_{\Theta}(s_{i}))$: 状態価値関数 (ANN で構成、最終層の活性化関数はシグモイド関数)

先読み結果を正則化項として付加

\begin{aligned}
\mathcal{L}_{\lambda}\left(\left\{(s_{i}, t_{i}, v'_{i}) \right\}_{i}\right)
 &= \sum_{i}
         \lambda_{i}  \mathcal{L}_{i}\left(s_{i}, t _{i}\right) +
    (1 - \lambda_{i}) \mathcal{L}_{i}\left(s_{i}, v'_{i}\right)
 \\
 &= \sum_{i}
        \lambda_{i}  \left\{t _{i} \ln v_{i} + (1 - t _{i}) \ln(1 - v_{i}) \right\} +
   (1 - \lambda_{i}) \left\{v'_{i} \ln v_{i} + (1 - v'_{i}) \ln(1 - v_{i}) \right\}
 \\
 &= \sum_{i} \bar{t}_{i} \ln v_{i} + (1 - \bar{t}_{i}) \ln(1 - v_{i})
 \\
 &= \sum_{i} \mathcal{L}_{i}\left(s_{i}, \bar{t}_{i} \right)
 \\
 &= \mathcal{L}\left(\left\{(s_{i}, \bar{t}_{i}) \right\}_{i}\right)
\end{aligned}

ここで $\bar{t}_{i} = \lambda_{i} t_{i} + (1 - \lambda_{i}) v’_{i} = v’_{i} + (t_{i} - v’_{i}) \lambda_{i}$ とおいた ($v’_{i}$ は局面 $s_{i}$ から先読みした予想勝率)。

  • $\lambda_{i} = 0.998^{(局面 s_{i} から終局までの手数)}$ ぐらいにするとよさそう
  • 勝敗を計算するときは $\Theta$ にランダム成分を加えるといいかも
    • 重みに $\mathcal{N}(0, \sigma^{2})$ を加えるとか ($\sigma = 0.1$ とかで)
    • アンサンブル的な効果が得られそう
    • $\hat{v}_{i}$ の計算は、それとは別のランダム成分を加えるといいかも

参考文献

  1. elmo (wcsc27)
  2. 激指 (wcsc26)
  3. †白美神† (第 4 回将棋電王トーナメント)