「BirdHead」の思考ルーチンを作ってみた。（その4）

昨日はプレイヤー・ビューの特徴ベクトル化とそれを使った価値の計算について説明した。

今日はそれを使ったアクションの選択と学習について説明していく。

SarsaComクラス（続き）

アクションの選択

アクションの選択は、Sarsa( $\lambda$ )法を使うので、任意のソフト方策を使うことになる。
ここでは、シンプルな $\varepsilon$ グリーディ法を使ってアクションの選択を行う。

  private var epsilon: Double
  var learn: Bool
  var debugPrint: Bool
  private(set) var weight: [Double]
  private var currentFeature: [Double]

  // 省略

  func select(view: GameInfo.PlayerView) throws -> Action {
    let legalActions = view.legalActions

    var selectedAction = legalActions[0]
    var selectedFeature = self.toFeature(view, action: selectedAction)
    var selectedValue = self.valueOfFeature(selectedFeature)

    for action in view.legalActions {
      let feature = self.toFeature(view, action: action)
      let value = self.valueOfFeature(feature)
      if self.debugPrint {
        print("action: \(action), value: \(value)")
      }
      if value > selectedValue {
        selectedAction = action
        selectedFeature = feature
        selectedValue = value
      }
    }

    if self.learn &&
       (legalActions.count > 0) &&
       (Random.getRandomProbability() < self.epsilon) {
      selectedAction = legalActions[Random.getUniformedRandom(legalActions.count)]
      selectedFeature = self.toFeature(view, action: selectedAction)
    }

    self.currentFeature = selectedFeature

    return selectedAction
  }

まずやっているのは、グリーディな行動の検索。
合法手となる各アクションをビューに対して実行したときの事後状態の価値を比べて、最も価値が高いと思われるアクションを見つけている。

そして、学習を行うフラグが立っていた場合には、epsilonより小さい確率でランダムにアクションを選択し直すようにしている。

なお、Random.getRandomProbability()は0.0以上1.0以下の数をランダムに返すメソッドで、以下のような実装。

//==============================
// BirdHead
//------------------------------
// Random.swift
//==============================

import Foundation
import Security

class Random {
  static func getUniformedRandom(upperBound: Int) -> Int {
    // 省略
  }

  static func getRandomProbability() -> Double {
    return Double(Random.getUniformedRandom(0x1_0000)) / Double(0xffff)
  }

  // 省略
}

最後、学習に使えるように、選択したアクションに対する特徴ベクトルをプロパティに保持して、選択したアクションを返している。

パラメータの学習

パラメータの学習は、特徴に対する適格度 $\boldsymbol{e} \in \mathbb{R}^{\mathcal{F}}$ を累積させていき（これは観測された価値と現在の価値の推定との差がそれぞれの特徴に対してどれくらい影響するのかを累積させている）、それに応じた分だけ値を変化させる。

具体的には、事後状態 $u \in \mathcal{S}$ を観測したときに適格度 $\boldsymbol{e} \in \mathbb{R}^{\mathcal{F}}$ を

${ \displaystyle \boldsymbol{e} \leftarrow \gamma \lambda \boldsymbol{e} + \boldsymbol{\phi}(u) }$

と更新し、報酬 $r$ と次の事後状態 $u' \in \mathcal{S}$ を観測したときに、パラメータを

${ \displaystyle \boldsymbol{\theta} \leftarrow \boldsymbol{\theta} + \alpha \left( r + Q_{u'} - Q_{u} \right) \boldsymbol{e} }$

と更新する。

なお、 $\lambda$ はトレース減衰パラメータと呼ばれるパラメータで、観測された差分をどれくらい前の状態にまで反映させるかを表すものになっている。
このパラメータを $\lambda = 0$ とすればこれはSarsa法と同じになり、逆に $\lambda = 1$ とすればこれはモンテカルロ法と同じになる。
実験結果では、0.6〜0.9くらいの値を使うと性能がよくなるみたい。

これを実装したコードが、以下。

  private var lambda: Double
  private var stepSize: Double
  private(set) var weight: [Double]
  private var previousFeature: [Double]
  private var currentFeature: [Double]
  private var accumulatedFeature: [Double]

  // 省略

  func learn(minusPoint: Int) {
    if self.previousFeature.count > 0 {
      let previousValue = self.valueOfFeature(self.previousFeature)

      let currentValue: Double
      if self.currentFeature.count > 0 {
        currentValue = self.valueOfFeature(self.currentFeature)
      } else {
        currentValue = 0.0
      }

      let diff = Double(-minusPoint) + currentValue - previousValue

      for i in 0..<self.accumulatedFeature.count {
        self.accumulatedFeature[i] *= self.lambda
        self.accumulatedFeature[i] += self.previousFeature[i]
        self.weight[i] += self.stepSize * diff * self.accumulatedFeature[i]
      }
    }

    self.previousFeature = self.currentFeature
    self.currentFeature = [Double]()

    // if terminal status is observed, reset accumulated feature
    if self.previousFeature.count == 0 {
      self.accumulatedFeature = [Double](count: 98, repeatedValue: 0.0)
    }
  }

なお、このコードは厳密に言うとちょっと間違ってる・・・
というのは、

行動選択→学習（観測された報酬が引数として渡ってくる）→次の行動選択→学習（次に観測された報酬が引数として渡ってくる）→・・・

なので、観測された報酬を一度保存しておいて、次の学習のタイミングで保存しておいた報酬を使うというのが本来は正しい。
けど、このコードだと観測された報酬を即座に使ってしまっている。

ただ、ディールの途中では報酬が常に0で渡ってきて、ディールの最後のトリックが終わり（このときも報酬は0が渡ってくる）、そのあとディールの解決のタイミングでマイナス点が報酬として渡ってくるので、結果的に辻褄があうようになっている。
（こちらも、本来は最後のトリックが終わった段階でマイナス点が報酬として渡ってきて、ディールの解決のタイミングの報酬は0となっているべきなんだけど、このように報酬が渡されるタイミングが1テンポ遅れているので、渡された報酬をそのまま使ってしまっても結果的に問題なくなっている）

これでアクション選択と学習のアルゴリズムの実装はOK。
あとは、パラメータの保存とロードを実装するだけ。

今日はここまで！

いものやま。

雑多な知識の寄せ集め

「BirdHead」の思考ルーチンを作ってみた。（その4）

SarsaComクラス（続き）

アクションの選択

パラメータの学習