Suttonの強化学習本をひたすら読む(2章)

Richard S. Suttonの強化学習のメモ。

概要

この章で扱う問題のイメージ

• 環境

この章で扱う環境はn本腕Bandit問題。 エージェントがプレイする度にいくらかの「報酬」を返すマシンがあり、そのようなマシンn台から構成されている。 それぞれのマシンが返す報酬は以下で定義されている。

* 平均：平均0分散1の正規分布（マシンごとに固有の値が一番最初に決まっている）
* 分散：平均0分散1の正規分布（プレイするたびに変わる）

「状態」に当てはまるものは特にない。

• エージェント

より多くの報酬を得る、もしくは探索をするため、何番目のマシンをプレイするかという「行動」を決定する。 この章では、エージェントが最適な行動をとるための手法を扱っている。 説明の便宜上、これらの手法を報酬推定、行動決定に分類して示す。

2.2章　標本平均、ε-greedy

標本平均

「報酬推定」に当たる手法。 過去にi番目のマシン(マシンi)から得た報酬の平均値により、マシンiによる報酬を推定するもの。

ε-greedy

「行動決定」に当たる手法。 小さい値εの確率で探索（報酬の推定値とは無関係にランダムなマシンをプレイ）し、1-εの確率でgreedyな行動（報酬の推定値が最も大きいマシンをプレイ）を取る。

上記の結果はn本腕Bandit問題を2000回解き、その全ての試行に対して平均を取ったもの。 左右のグラフはそれぞれ、ある時点において過去に得た報酬、平均報酬が最も大きい行動を取った割合を表す。 ε=0.1の場合は探索の結果最適な行動を見出している。 ε=0の場合は一切探索を行わず、ε=1の場合は完全にランダムにプレイすることになる。

2.3 softmax法

「行動決定」に当たる手法。 1-εの確率でgreedyな行動を取るのはε-greedyと同様。ただし探索を行う場合は、ランダムではなく報酬推定に応じた重み付けに従い探索を行う。 τ=0の場合は全く探索を行わない結果となり、τ=1の場合はε-greedy手法の結果と完全に一致する。

2.6 指数減衰荷重平均

「報酬推定」に当たる手法。 報酬推定にあたり、過去に得た全ての報酬を平等に扱うのではなく、直近に得た報酬を重視するような加重平均をとる。 環境が時間変化する場合に有効に働く。

2.7 optimistic初期値

「報酬推定」に当たる手法。 報酬推定の初期値を設定する際、十分に大きい報酬を期待して（optimisticな）初期値を設定する。 行動の結果期待したほどの報酬が得られないため、全ての行動について試行、評価を行うことに繋がる。 ただし初期値のみに焦点を当てた手法であり、非定常問題に適しておらず、一般に探索を促す目的で使用されることは少ない。

2.8 強化比較

「行動決定」に当たる手法。 この手法を用いる場合には報酬推定を行わない。 ステップ毎に、そのステップで受け取った報酬とリファレンス報酬を比較し、受け取った報酬の大きさに応じて行動の優先度を設定する。

2.9 追跡手法

「行動決定」に当たる手法。 ステップ毎に、greedyな行動の優先度を上げ、そうでない行動の優先度を下げる。

コード

各手法を試すに当たって書いたn本腕Bandit問題、プレーヤーのコードは以下（実行部分は省略する）。 （コード部分をシンタックスハイライトで表示させると、なぜか記事中の画像が表示されなくなるのでべた貼り・・・）

import numpy as np import matplotlib.pyplot as plt

class n_Bandit(): """n本腕Bandit問題を定義""" def init(self, n): """n個のマシンから成るゲームの初期設定を行う""" self.machine_num = n self.mean_reward = np.random.randn(self.machine_num) # マシンが返す報酬の平均値を設定 self.lavish = np.argmax(self.mean_reward)

def reset(self):
    """全てのマシンの設定を初期化する"""
    self.mean_reward = np.random.randn(self.machine_num)
    self.lavish = np.argmax(self.mean_reward)

def play(self, nth):
    """報酬を返させる関数．playごとの報酬は確率的に変動するが、平均値はself.mean_rewardとなる．"""
    return np.random.randn()+self.mean_reward[nth]

class Player(): """プレーヤーを定義する""" def init(self, game2play, act_strategy=None, est_strategy=None, epsilon=0.0, tau=1.0, alpha=1.0, reward_init=0, alpha_rc=0.1, beta_pr=0.01): """プレーヤーの行動戦略、ゲーム報酬の予想戦略を設定する""" self.game = game2play self.machine_num = game2play.machine_num self.Reward_init = reward_init # 報酬予想の初期値を設定（reward_initが大きい場合optimistic初期値となる） self.Reward_est = np.ones(self.machine_num)*self.Reward_init self.PlayTime = np.ones(self.machine_num) # 初期状態で各行動を1回試行していると設定。optimistic初期値対応のため（報酬推定が正確ではなくなるが、大勢に影響はない） self.epsilon = 1-epsilon self.tau = tau self.alpha = alpha self.alpha_rc = alpha_rc self.beta_pr = beta_pr self.ref_reward = self.Reward_init # リファレンス報酬。強化比較の場合のみ使用する self.priority_rate = np.ones(self.machine_num) # 行動優先度。強化比較、追跡手法の場合のみ使用する # ----------------- 行動戦略を設定 ----------------- if act_strategy == "greedy": # εグリーディ self.act = self.greedy elif act_strategy == "softmax_selection": # softmax行動選択 self.act = self.softmax_selection elif act_strategy == "reinforcement_comparison": # 強化比較 self.act = self.reinforcement_comparison elif act_strategy == "pursuit": # 追跡手法 self.act = self.pursuit else: # 行動戦略の設定が上記いずれでもない場合は例外を出力 # todo 例外を出力 print("行動戦略設定エラー") # ----------------- 報酬の予想戦略を設定 ----------------- if est_strategy == "sample_average": # 標本平均 self.est = self.sample_average elif est_strategy == "recency_weighted_average": # 指数元帥加重平均 self.est = self.recency_weighted_average else: # 予想戦略の設定が上記いずれでもない場合は例外を出力 # todo 例外を出力 print("報酬の予想戦略設定エラー")

def reset(self):
    """プレーヤーの戦略は変えず、報酬の予想値、リファレンス報酬、行動優先度、プレイ回数をリセットする"""
    self.Reward_est = np.ones(self.machine_num) * self.Reward_init
    self.ref_reward = self.Reward_init
    self.priority_rate = np.ones(self.machine_num)
    self.PlayTime = np.ones(self.machine_num)  #

# ----------------- 行動戦略の定義 -----------------
def greedy(self):
    search = (np.random.rand() < self.epsilon)  # εの確率で探索、それ以外はgreedyに振る舞う
    if search:
        # greedyに振る舞う場合は、予想報酬がもっとも大きいマシンをプレイする
        n = np.argmax(self.Reward_est)
    else:
        # 探索する場合はランダム
        n = np.random.randint(self.machine_num)
    # n番目をプレイする
    reward = self.game.play(n)
    return n, reward

def softmax_selection(self):
    search = (np.random.rand() < self.epsilon)  # εの確率で探索、それ以外はgreedyに振る舞う
    if search:
        # greedyに振る舞う場合は、予想報酬がもっとも大きいマシンをプレイする
        n = np.argmax(self.Reward_est)
    else:
        # 探索する場合は予想報酬のsoftmaxに従い、プレイするマシンを選択する
        tmp = self.Reward_est/self.tau - np.max(self.Reward_est)/self.tau  # オーバーフロー回避
        softmax = np.exp(tmp) / np.sum(np.exp(tmp), axis=0)
        n = np.random.choice(self.machine_num, p=softmax)
    # n番目をプレイする
    reward = self.game.play(n)
    return n, reward

def reinforcement_comparison(self):
    tmp = self.priority_rate-np.max(self.priority_rate)
    softmax = np.exp(tmp) / np.sum(np.exp(tmp), axis=0)
    n = np.random.choice(self.machine_num, p=softmax)
    # n番目をプレイする
    reward = self.game.play(n)
    self.priority_rate[n] += self.beta_pr*(reward-self.ref_reward)
    self.ref_reward += self.alpha_rc*(reward-self.ref_reward)
    return n, reward

def pursuit(self):
    self.priority_rate /= np.sum(self.priority_rate, axis=0)
    n = np.random.choice(self.machine_num, p=self.priority_rate)
    # n番目をプレイする
    reward = self.game.play(n)
    n_greedy = np.argmax(self.Reward_est)
    self.priority_rate[n_greedy] += self.beta_pr*(1-self.priority_rate[n_greedy])
    for i in range(self.machine_num):
        if i != n_greedy:
            self.priority_rate[i] -= self.beta_pr*self.priority_rate[i]
    return n, reward

# ----------------- 報酬の予想戦略を定義 -----------------
def sample_average(self, n, reward):
    self.Reward_est[n] += 1/(self.PlayTime[n]+1)*(reward-self.Reward_est[n])

def recency_weighted_average(self, n, reward):
    self.Reward_est[n] += self.alpha*(reward-self.Reward_est[n])

# ----------プレイするメソッドの定義-----------
def play(self):
    n, reward = self.act()  # n番目のマシンをプレイし、報酬を得る
    if self.act != self.reinforcement_comparison:  # 行動戦略が強化比較でない場合は、報酬の予想値を更新する
        self.est(n, reward)
    self.PlayTime[n] += 1
    return n, reward