hatena blogでtexによる下付き文字がうまく表示されない

以下のような形で書いたところうまく表示されない

[tex: x_{i,j} + x_{j,k}]

このように表示される [tex: x{i,j} + x{j,k}]

少しググってみるとこちらのブログでその原因が解説されていた

はてなブログのTeX記法で数式を書く時用のチートシートと注意点 - ぴよぴよ.py

原因はアンダースコアに挟まれた部分は強調表示されるという書式があるため。なので下付き文字を複数書く場合はアンダースコアをエスケープする必要があった。

なので上記のものはこう書く

[tex: x\_{i,j} + x\_{j,k}]

これで以下のように表示される

 x_{i,j} + x_{j,k}

ということで基本的にエスケープしておくのが良さそう

pytorchでnoisy networkを実装

元の論文はこちら

[1706.10295] Noisy Networks for Exploration

常にその時点で価値の高い行動を取り続けた場合、最初に価値が高くなった行動が取られ続け、別の行動を取る可能性がなくなってしまう。それを防ぐため元のDQNではε-greedy法と呼ばれる手法を用いている。これは一定確率で価値に依らずランダムで行動を選択することにより、選ばれる行動の可能性を広げようとするものである。

noisy networkはこの部分を改良するもので、ネットワークそのものに学習可能なパラメータと共に外乱を与え、それも含めて学習させていくことでより長期的で広範囲に探索を進めようというもの。

We propose a simple alternative approach, called NoisyNet, where learned perturbations of the network weights are used to drive exploration. The key insight is that a single change to the weight vector can induce a consistent, and potentially very complex, state-dependent change in policy over multiple time steps

noiseを含んだ計算式はこちら

 \displaystyle y = (µ^{w} + σ^{w} ⦿ ε^{w}) x + µ^{b} + σ^{b} ⦿ ε^{b}

通常のLinearの計算y = wx + bのw, bの項の部分をそれぞれnoiseを含んだパラメータに置き換えたもの。

添字としてついているwとbは要素数を表しており、入力数をp、出力数をqとすると、wが付くものはq * p個、bが付くものはq個の要素を持つtensor。μとσは学習させるパラメータ、εは計算のたびに生成する乱数(ガウス分布)、⦿の演算子は要素毎の積を表す。

また、乱数の取り方について2種類言及されているが、DQNに適用するため論文に合わせてFactorised Gaussian noiseの方法で実装した。

We explore two options: Independent Gaussian noise, which uses an independent Gaussian noise entry per weight and Factorised Gaussian noise, which uses an independent noise per each output and another independent noise per each input. The main reason to use factorised Gaussian noise is to reduce the compute time of random number generation in our algorithms. This computational overhead is especially prohibitive in the case of single-thread agents such as DQN and Duelling

乱数生成の計算によるオーバーヘッドをへらすためというのがFactorised Gaussian noiseを使う理由。

実装

noiseを含んだLinear layerの実装はこちら

class FactorizedNoisy(nn.Module):
    def __init__(self, in_features, out_features):
        super(FactorizedNoisy, self).__init__()
        self.in_features = in_features
        self.out_features = out_features

        # 学習パラメータを生成
        self.u_w = nn.Parameter(torch.Tensor(out_features, in_features))
        self.sigma_w  = nn.Parameter(torch.Tensor(out_features, in_features))
        self.u_b = nn.Parameter(torch.Tensor(out_features))
        self.sigma_b = nn.Parameter(torch.Tensor(out_features))
        self.reset_parameters()

    def reset_parameters(self):
        # 初期値設定
        stdv = 1. / math.sqrt(self.u_w.size(1))
        self.u_w.data.uniform_(-stdv, stdv)
        self.u_b.data.uniform_(-stdv, stdv)

        initial_sigma = 0.5 * stdv
        self.sigma_w.data.fill_(initial_sigma)
        self.sigma_b.data.fill_(initial_sigma)

    def forward(self, x):
        # 毎回乱数を生成
        rand_in = self._f(torch.randn(1, self.in_features, device=self.u_w.device))
        rand_out = self._f(torch.randn(self.out_features, 1, device=self.u_w.device))
        epsilon_w = torch.matmul(rand_out, rand_in)
        epsilon_b = rand_out.squeeze()

        w = self.u_w + self.sigma_w * epsilon_w
        b = self.u_b + self.sigma_b * epsilon_b
        return F.linear(x, w, b)

   def _f(self, x):
       return torch.sign(x) * torch.sqrt(torch.abs(x))

初期値の設定は論文の3.2

For factorised noisy networks, each element µi,j was initialised by a sample from an independent uniform distributions  \displaystyle U[−\frac{1}{\sqrt{p}}, +\frac{1}{\sqrt{p}}] and each element  σ_{i,j} was initialised to a constant  \displaystyle \frac{σ_0}{\sqrt{p}}. The hyperparameter  σ_0 is set to 0.5.

これを使ってnoisy networkを作成したのが以下(dueling networkの実装も含む) ただし、ノード数などは完全には合わせてないので注意

class DuelingNetConv2d(nn.Module):
    def __init__(self, num_states, num_actions, is_noisy=False):
        super(DuelingNetConv2d, self).__init__()
        self.num_states = num_states
        self.num_actions = num_actions

        self.conv1 = nn.Conv2d(num_states, 16, kernel_size=8, stride=4)
        self.conv2 = nn.Conv2d(16, 32, kernel_size=4, stride=2)
        if is_noisy:
            # 9 * 9 * 32 = 2592
            self.fcV1 = FactorizedNoisy(2592, 256)
            self.fcA1 = FactorizedNoisy(2592, 256)
            self.fcV2 = FactorizedNoisy(256, 1)
            self.fcA2 = FactorizedNoisy(256, num_actions)
        else:
            self.fcV1 = nn.Linear(2592, 256)
            self.fcA1 = nn.Linear(2592, 256)
            self.fcV2 = nn.Linear(256, 1)
            self.fcA2 = nn.Linear(256, num_actions)

    def forward(self, x):
        x = F.relu(self.conv1(x))
        x = F.relu(self.conv2(x))
        x = x.view([-1, 2592])
        V = self.fcV2(self.fcV1(x))
        A = self.fcA2(self.fcA1(x))

        averageA = A.mean(1).unsqueeze(1)
        return V.expand(-1, self.num_actions) + (A - averageA.expand(-1, self.num_actions))

元々Linear layerを使っていた部分をすべて置き換えた。noisy networkの論文では3.1にこうかかれていた

We apply the following modifications to both DQN and Dueling: first, ε-greedy is no longer used, but instead the policy greedily optimises the (randomised) action-value function. Secondly, the fully connected layers of the value network are parameterised as a noisy network,

なのでこの通りであればdueling network中のvalue network側のみをnoisyなものに置き換えるのが正しそうだが、今回はrainbowを実装するための一要素として実装していたので、こちらの論文を参考にすべてのLinear layerを置き換えた。

[1710.02298] Rainbow: Combining Improvements in Deep Reinforcement Learning

(The Integrated Agentの項目の最後)

We then replace all linear layers with their noisy equivalent described in Equation (4). Within these noisy linear layers we use factorised Gaussian noise (Fortunato et al. 2017) to reduce the number of independent noise variables

結果

atariのbreakoutを20000 episodes分学習させた結果がこちら 縦軸が100 episodes毎の平均reward(崩したブロックの数)、横軸がepisode数 f:id:y-kamiya:20181013105913p:plain

ちなみに、prioritized experience reply(とimportance sampling)の実装も含んだ状態で学習させた。noisy networkを適用した方が立ち上がりが遅くなっているものの、baselineに比べて後半が右肩上がりの状態になっているように見える。rainbowの関連情報などを見ると、noisy networkは最終的なパフォーマンスを向上させるのに寄与すると言われているので、それに沿った結果にはなっていそう。

ただし注意点として、上記の学習はたった20000 episodes(steps数は1.5M程度)しかやっていないため、論文にかかれているようなスケール(100M stepsとか)からするとほとんど差が出ていない初期の部分に当てはまる(noisy networkの論文のグラフを見るとbaselineとnoisy network適用時の結果に差が出始めているのは10M steps経過くらいで、それまではほとんど差が見えない)

参考

[1706.10295] Noisy Networks for Exploration

Extending PyTorch — PyTorch master documentation

RL-Adventure/5.noisy dqn.ipynb at master · higgsfield/RL-Adventure · GitHub

Rainbow/model.py at master · Kaixhin/Rainbow · GitHub

速習 強化学習 ―基礎理論とアルゴリズム―

速習 強化学習 ―基礎理論とアルゴリズム―

  • 作者: Csaba Szepesvari,小山田創哲,前田新一,小山雅典,池田春之介,大渡勝己,芝慎太朗,関根嵩之,高山晃一,田中一樹,西村直樹,藤田康博,望月駿一
  • 出版社/メーカー: 共立出版
  • 発売日: 2017/09/21
  • メディア: 単行本
  • この商品を含むブログを見る

pytorchでprioritized experience replyを実装

元の論文はこちら

[1511.05952] Prioritized Experience Replay

DQNで学習を進めるための重要なテクニックとしてexperience replyというものがあり、これはメモリにためておいたstateやactionの記録をmini batchとしてランダムに取り出して学習させるというもの。

prioritized experience reply (PER)はこれを改善したもので、mini batchとして取り出すデータをランダムではなくTD誤差の大きさに基づく確率によって決める。TD誤差が大きい=理想的な出力と実際の差が大きい、ということなので優先的に学習に使うべきという考え方。

実装で特に参考にさせてもらったのはこちらのブログ

Let’s make a DQN: Double Learning and Prioritized Experience Replay | ヤロミル

保存した経験を効率的に取り出すための二分木(sum tree)の説明や実装もあり、とてもわかりやすかった。sum treeの実装についてはそのまま使わせて頂きました。

AI-blog/SumTree.py at 5aa9f0ba91f12ab4e24043134c0b33900a2f6236 · jaara/AI-blog · GitHub

実装の全体はこちら

environment

https://github.com/y-kamiya/machine-learning-samples/blob/7b6792ce37cc69051e9053afeddc6d485ad34e79/python3/reinforcement/dqn/cartpole_rainbow.py

agent

https://github.com/y-kamiya/machine-learning-samples/blob/7b6792ce37cc69051e9053afeddc6d485ad34e79/python3/reinforcement/dqn/agent.py

Prioritized Experience Reply

下記クラスを元々experience replyに使っていたRandomMemoryの代わりに使えばOK

なお、priorityの付け方としてProportional prioritizationの方法で実装した。

class PERMemory:
    epsilon = 0.0001
    alpha = 0.6
    size = 0

    # SumTreeについては参考にしたブログから拝借して必要なものをつけたし
    def __init__(self, capacity):
        self.tree = SumTree(capacity)

    # Proportional prioritizationによるpriorityの計算
    def _getPriority(self, td_error):
        return (td_error + self.epsilon) ** self.alpha

    # 新しい経験を入れる際は、必ず一度はreplyされるようにその時点で最大のpriorityで
    # reply開始前の場合は論文に従いpriority=1とした
    def push(self, transition):
        self.size += 1

        priority = self.tree.max()
        if priority <= 0:
            priority = 1

        self.tree.add(priority, transition)

    # 0 ~ priorityの合計値の間でbatch sizeの分だけ乱数を生成し、
    # それに合致するデータを取得する
    def sample(self, size):
        list = []
        indexes = []
        for rand in np.random.uniform(0, self.tree.total(), size):
            (idx, _, data) = self.tree.get(rand)
            list.append(data)
            indexes.append(idx)

        return (indexes, list)

    # 再生した経験のpriorityを更新
    def update(self, idx, td_error):
        priority = self._getPriority(td_error)
        self.tree.update(idx, priority)

    def __len__(self):
        return self.size

reply部分にpriorityの更新処理を追加

def reply(self):
    if len(self.memory) < self.config.steps_learning_start:
        return

    self.model.train()

    # batch size分だけデータを取り出す
    indexes, transitions = self.memory.sample(BATCH_SIZE)
    # lossの計算に必要な形に(DDQNとかの処理はこの中でやっている)
    values, expected_values = self._get_state_action_values(transitions)

    loss = F.smooth_l1_loss(values, expected_values)
    self.optimizer.zero_grad()
    loss.backward()
    self.optimizer.step()

    # replyしたデータのpriorityを更新
    if (indexes != None):
        for i, value in enumerate(values):
            td_error = abs(expected_values[i].item() - value.item())
            self.memory.update(indexes[i], td_error)

SumTreeに追加した処理はpriorityの最大値を取得する部分 リーフに該当するindexの中で最大値を取得する

# class SumTree
# self.index_leaf_start = capacity - 1
def max(self):
    return self.tree[self.index_leaf_start:].max()

bufferが大きくなるほど時間がかかるはずなので、問題になるかもと思って時間を測ったみた(bufferのcapacityが105の場合)

$ python -m timeit -s "import numpy as np; values = [float(x) for x in range(200000)]; npvalues = np.fromiter(values, np.float)" "npvalues[100000:].max()"
10000 loops, best of 3: 36 usec per loop

なので問題なし

Importance Sampling

priorityに基づく確率によりreplayに使うデータをサンプリングすることにより、priorityが大きなものほど学習に使われる頻度が高くなる。そのため、priorityの大きなデータほど学習への寄与が大きくなる(=bias)。

論文より引用

The estimation of the expected value with stochastic updates relies on those updates corresponding to the same distribution as its expectation. Prioritized replay introduces bias because it changes this distribution in an uncontrolled fashion

このbaisを是正するために、サンプリングされる確率の大きいデータほど、lossへの寄与が小さくなるように補正をかける。これにより全体としての期待値を、一様にサンプリングした場合に近づけることができる。

# class PERMemory
def sample(self, size, episode):
    list = []
    indexes = []
    weights = np.empty(size, dtype='float32')
    total = self.tree.total()
    # 初期の設定値から1に向けてannealing
    # episode単位で更新して最後のepisode時に1となるように
    beta = self.BETA + (1 - self.BETA) * episode / self.config.num_episodes

    for i, rand in enumerate(np.random.uniform(0, total, size)):
        (idx, priority, data) = self.tree.get(rand)
        list.append(data)
        indexes.append(idx)
        # 各データのωを計算
        weights[i] = (self.capacity * priority / total) ** (-beta)

    #  必ず1以下の値となるようωの最大値で割る
    return (indexes, list, weights / weights.max())

上記の呼び出し側

def loss(self, input, target, weights):
    if self.config.use_IS:
        # 論文だとω * δをすべてのデータで足し合わせているがここでは平均値を取る
        loss = torch.abs(target - input) * torch.from_numpy(weights).to(device=self.config.device)
        return loss.mean()

    return F.smooth_l1_loss(input, target)

def replay(self, episode):
    if len(self.memory) < self.config.steps_learning_start:
        return

    self.model.train()

    indexes, transitions, weights = self.memory.sample(BATCH_SIZE, episode)
    values, expected_values = self._get_state_action_values(transitions)

    # 各データに重みをかけるため独自の処理に
    loss = self.loss(values, expected_values, weights)
    ...

lossの計算のところは論文(のAlgorithm 1)だと以下のような式になっている

Accumulate weight-change ∆ ← ∆ + wj · δj · ∇θQ(Sj−1, Aj−1)

ただ、この最後の項については論文内で明確には説明されておらずよく理解できていない。 なので単純にω * δの和をとって試してみたのだが、学習がまったく進まなくなってしまった。そのため、ISを行わない場合に使っていたhubor lossと同じ程度のlossとなるようにTD誤差の絶対値を使い、かつ全体の和ではなく平均値を取るようにしたところ、学習が進むようになった。

結果

とりあえず簡単に計算が終わるcartpoleで試してみた 直近100episodeの経過steps数が150を超えた段階で終了とみなし、そこに到達するまでにかかったepisode数を比較した。同じ操作を100回行った平均値が以下

  • baseline:140
  • baseline + PER:140
  • baseline + PER + IS:120

ちなみにbaselineにはDDQNとDueling networkが含まれている。

PERだけを適用しても結果が変わらなかったが、ISも適用することで学習が早まった。ISも適用した場合については明らかに少ないepisode数で終わっているのでpriorityによる重み付けが効いているのだと思われる。PERのみ適用した場合は変化がなかったが、これはデータの偏りを補正しないことによる悪影響とpriorityをつけたことによる学習の立ち上がりの向上が相殺してそうなったのだろうか。(もしくは実装がおかしい?)

cartpoleでは学習する対象が小さいためこれらの効果見づらくなっている可能性はあるためatariでも試してみることにする。

atariで動かしてみた結果がこちら f:id:y-kamiya:20181008110450p:plain

縦軸は100 episodes毎に得たreward(壊したブロック数)の平均。 実行時間をへらすため10000episodesしかやってないが、PERを入れた方が明らかに学習の立ち上がりが早くなっている。 また、論文では108ステップとか学習させているので、10000 episodesくらいならannealingしないのと同じといえるかと思い、no anealingというデータもとってみた。

注意点として、episode数によって学習の終わりを決めていたので、終了までに行った総ステップ数(=学習時間)は一致していないこと。最も学習の進んだPERのみのもので900000、baselineのものは500000程度だった。なので論文に出ているstep数による取得rewardのグラフと比べる意味はないので参考までに。

一定ステップ数を経過したら評価用のepisodeを設けるという形でのデータもそのうちとってみる。