強化学習について学んでみた。（その21）

昨日は○×ゲームをプレイできるようにするところまで実装した。

今日はSarsa法を使ったAIを実装していく。

Valueクラス

まずは行動価値を表すValueクラスから。

#====================
# value.rb
#====================

require './state'

module TicTacToe
  class Value
    @@step_size = 0.1

    def initialize
      @value = Hash.new(0.0)
    end

    def get(state)
      return @value[state]
    end

    def get_max_action(state, mark)
      actions = state.valid_actions
      hash = actions.each_with_object(Hash.new) do |action, hash|
        after_state = state.set(action, mark)
        hash[action] = @value[after_state]
      end
      max_value = hash.values.max
      max_action = hash.key(max_value)
      return max_action
    end

    # 事後状態stateに対する価値を更新する
    # 終端状態で行動することが出来ない場合、
    # 次の事後状態next_stateとしてnilを指定すること
    def update(state, reward, next_state)
      if next_state == nil
        next_state_value = 0.0
      else
        next_state_value = @value[next_state]
      end
      @value[state] += @@step_size * (reward + next_state_value - @value[state])
    end
  end
end

事後状態

ここでちょっと注目したいのが、状態行動対 $(s, a)$ に対する価値を保持するようにしているのではなく、事後状態に対する価値を保存するようにしているということ。

事後状態とは何かというと、次状態 $s'$ とはまた違うもので、状態 $s$ に対して行動 $a$ を行った直後に観測される状態のこと。
それだけ聞くと次状態と違わないように思うけど、ゲームとかの場合だとこの2つは異なるものとなる場合がある。

事後状態は状態 $s$ に対して行動 $a$ を行った直後に観測される状態で、エージェントは事後状態で行動の選択を行えるとは限らない。
次状態は状態 $s$ に対して行動 $a$ を行った次にエージェントが行動の選択を行う状態で、行動を行った直後に観測されるとは限らない。

もし行動を行った直後に観測される状態でエージェントが再び行動の選択を行うのなら、事後状態＝次状態になるけれど、そうでない場合もある。

実際、○×ゲームだと

<状態s>

.|.|.
-+-+-
.|.|.
-+-+-
.|.|.

↓真ん中に○をつける

<事後状態>

.|.|.
-+-+-
.|o|.
-+-+-
.|.|.

↓相手が左上に×をつける

<次状態s'>

x|.|.
-+-+-
.|o|.
-+-+-
.|.|.

というふうに、行動を行った直後に観測される事後状態は相手の手番で、エージェントは選択を行うことは出来ないので次状態にはならず、相手の手に応じて遷移したさらに次の状態が、エージェントが行動の選択を行う次状態として現れることになる。

では、なぜ状態行動対 $(s, a)$ に対する価値ではなく事後状態に対する価値を保持するようにしているのかというと、異なる状態行動対でも事後状態は同じになることがあるから。

例えば、

○|.|.
-+-+-
.|×|.
-+-+-
.|.|.

↓右に○をつける

○|.|.
-+-+-
.|×|○
-+-+-
.|.|.

の場合も

.|.|.
-+-+-
.|×|○
-+-+-
.|.|.

↓左上に○をつける

○|.|.
-+-+-
.|×|○
-+-+-
.|.|.

の場合も、状態行動対は別なものであるのに、事後状態は同じものになっている。
ここで、この異なる2つの行動価値は別のものかというと、事後状態が同じになっているので同じ次状態に遷移するわけだから、同じ価値だと考えられる。
それなら、状態行動対のままで価値を扱うよりも、事後状態に対する価値を扱った方が、重複がなくて効率的になる。

価値の更新

さて、そんな事後状態に対する価値だけれど、状態行動対 $(s, a)$ の代わりに事後状態を使っているだけだから、更新の仕方はTD学習と同じ。
ある事後状態 $u$ の価値 $Q_{u}$ を、観測された報酬 $r$ と次の事後状態 $u'$ を使って

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

と更新することになる。

Value#update()では、これに従った実装を行っている。

SarsaCom

いよいよSarsa法を使ったAIの実装。

#====================
# sarsa_com.rb
#====================

require './tic_tac_toe'
require './state'
require './value'

module TicTacToe
  class SarsaCom
    @@epsilon = 0.1

    def initialize(mark, value, learning=true)
      @mark = mark
      @value = value
      @learning = learning
      @previous_reward = nil
      @previous_after_state = nil
    end

    attr_reader :mark
    attr_accessor :learning

    def select_index(state)
      selected_action = @value.get_max_action(state, @mark)

      if @learning
        if Random.rand < @@epsilon
          selected_action = state.valid_actions.sample
        end

        # 事後状態が確定するので、このタイミングで学習を行う
        after_state = state.set(selected_action, @mark)
        if @previous_reward != nil && @previous_after_state != nil
          @value.update(@previous_after_state, @previous_reward, after_state)
        end
        @previous_after_state = after_state
      end

      return selected_action
    end

    def learn(reward, finished=false)
      if @learning
        if finished
          # 終端状態の場合、学習する機会がここしかないので、
          # ここで学習する
          @value.update(@previous_after_state, reward, nil)
          @previous_reward = nil
          @previous_after_state = nil
        else
          @previous_reward = reward
        end
      end
    end
  end
end

方策としては $\varepsilon$ グリーディ方策を使っている。

行動を選択したら事後状態をバックアップしておき、報酬も観測されたタイミングでバックアップしておいて、次に行動を選択したときに次の事後状態が確定するので、そこで学習を行っている。
ただし、終端状態だけは次に行動の選択がされないので、報酬が観測されたタイミングで次の事後状態の価値を0として学習を行っている。

今日はここまで！