強化学習の多腕バンディット問題を学んだのでまとめてみた
強化学習の勉強のために、ITエンジニアのための強化学習理論入門を読みました。
詳細な理論解説あり、コードありとかなり読み応えのある内容でした。
その中の1章、多腕バンディットのコーディングをまとめたいと思います。
なお、バンディットはスロットマシーン、腕(アーム)はスロットを回すためのアームのことで、たくさんスロットマシーンを回すシミュレーション、といったところでしょうか。
コーディング
ブログで使ったコードはこちら
github.com
import numpy as np import pandas as pd import warnings warnings.filterwarnings('ignore') # スロットの台数 slot_arms = 5 # 各スロットの期待値 # loc 平均、scale 標準偏差、size 出力配列のサイズ e_value = np.random.normal(loc=0.0, scale=1.0, size=slot_arms) for i in range(slot_arms): print("slot No.{0} 期待値: {1}".format(i, e_value[i])) print() print("最も期待値の大きい slot は No.{}".format(np.argmax(e_value)))
(以下、出力結果)
slot No.0 期待値: 0.39214341712590317
slot No.1 期待値: -0.20641977501211484
slot No.2 期待値: 0.6860500584941849
slot No.3 期待値: 0.4747609704743502
slot No.4 期待値: -0.7014833706044542
最も期待値の大きい slot は No.2
(以上)
沢山あるスロットの中から、もっとも期待値の大きいものを、何度も何度もランダムに選択する中で自動的に選択するというのが多腕バンディット問題のアルゴリズムです。
e_value = np.random.normal(loc=0.0, scale=1.0, size=slot_arms) により、各スロット台の期待値をランダムで設定しています。
期待値が事前にわかっていれば、単純に期待値の最も大きいスロットを選択すれば済む話ですが、多腕バンディット問題では現実のカジノ(パチンコやパチスロでもOK)と同じく、台の期待値がわかりません。
そこで、累計での結果が一番良かったものを選択し続ける、というアルゴリズムを用いて、結果的に一番期待値の高い台を抽出する、というのが多腕バンディット問題のアルゴリズムになります。
# スロットを回す回数 steps = 500 # ε(イプシロン)-greedy法の係数でスロットの中からランダムで選ぶ(=探索する)確率 epsilon = 0.1 # スロットマシーンの初期値 i_value = 0.0 # スロットマシーン台数分の初期値を格納した配列 qs = [i_value] * slot_arms # qsの内容をkeyに記録する空の辞書型 qs_histを作成 qs_hist = {} for i in range(slot_arms): qs_hist[i] = [] # 重み w = 0.1 for i in range(steps): # epsilon は 0.1 # ε(イプシロン)% の確率でスロットの中からランダムで選ぶ(=探索する) # np.random.random() で 0.0以上、1.0未満の乱数を作成 if np.random.random() < epsilon: arm = np.random.randint(len(qs)) else: # 残りの確率 (1 - ε)% は期待値の最も大きいスロットを選択 arm = np.argmax(qs) # reward はスロットから得られる報酬 # loc 平均、scale 標準偏差、size 出力配列のサイズ # 胴元が儲かる(プレイヤーが損をする)ように平均値は-0.1とした reward = np.random.normal(loc=e_value[arm], scale=1.0) qs[arm] += w * (reward - qs[arm]) for arm in range(slot_arms): qs_hist[arm].append(qs[arm])
ただし、収支がプラスだが期待値が最大でないスロット台をたまたま序盤に選択した結果、結果期待値が最大でないスロット台が選ばれる可能性もあります。
これを防ぐために、下記のε-greedy(イプシロン-グリーディ)法を用います。
# epsilon は 0.1 if np.random.random() < epsilon: arm = np.random.randint(len(qs)) else: arm = np.argmax(qs)
elseの部分で、配列の中で最も値が大きいものの位置を返しています。
これにより、その後のコードで最も大きい値のものを選択することになるわけですが、if の部分で epsilon(ε イプシロン)%の確率でランダム探索を行っています。
これにより、収支がプラスだが期待値が最大でないスロット台をたまたま序盤に選択した結果、結果期待値が最大でないスロット台の選択が続いてしまっても、選択する台の変更の余地を残すことが可能になります。
# グラフで表示 pd.DataFrame(qs_hist).plot(figsize=(6, 6), title='Initiative Value {}'.format(i_value))
50回目くらいまでは3番目に期待値の高い No.0 が選択され続けるが、50~300回目くらいまでは最も初期値の高い No.2 の成果が大きくなりました。
これは、探索でランダムに抽出した結果、No.2を選択し、その後も選ばれ続けている結果と思われます。
また300~340回目くらいにNo.0 が選択され続けているのも、探索でランダムに抽出した結果その後も選ばれ続けたためと思われます。
# スロットマシーンの初期値を変更 i_value2 = 3.0 # スロットマシーン台数分の初期値を格納した配列を新たに作成 qs2 = [i_value2] * slot_arms # qsの内容をkeyに記録する空の辞書型 qs_histを新たに作成 qs_hist2 = {} for i in range(slot_arms): qs_hist2[i] = []
for i in range(steps): # ε(イプシロン)% の確率でスロットの中からランダムで選ぶ(=探索する) # np.random.random() で 0.0以上、1.0未満の乱数を作成 if np.random.random() < epsilon: arm = np.random.randint(len(qs2)) else: # 残りの確率 (1 - ε)% は期待値の最も大きいスロットを選択 arm = np.argmax(qs2) # reward はスロットから得られる報酬 # loc 平均、scale 標準偏差、size 出力配列のサイズ reward = np.random.normal(loc=e_value[arm], scale=1.0) qs2[arm] += w * (reward - qs2[arm]) for arm in range(slot_arms): qs_hist2[arm].append(qs2[arm]) # グラフを表示 pd.DataFrame(qs_hist2).plot(figsize=(6, 6), title='Initiative Value {}'.format(i_value2))
初期値0.0の場合との大きな違いは、序盤の130回目くらいまで、すべてのパターンが選択され続けている点です。
初期値は以下のコーディング部分に影響します。
qs2 = [i_value] * slot_arms qs2[arm] += w * (reward - qs2[arm])
初期値0.0の場合は、qs2[arm]の初期値が3.0となります。
reward - qs2[arm] がプラスになる可能性が高く、今回選択したスロット台が実は期待値が最大でない場合でも、しばらく選択され続ける可能性があります。
一方、初期値を3.0に変更すると、reward - qs2[arm] がマイナスとなる可能性が高く、今回選択されたスロット台が次に選択されず、他のスロット台を選択できる可能性が高くなります。
これにより、たまたま最初に選択された期待値が最大でない台が連続して選択され続けることを防止することができ、期待値最大のスロット台を早い段階で検出することが可能となります。
自分がスロットを実際にしているところをイメージしてもらうと、たまたま最初に選択したスロット台の設定が実はそんなによくなくても、最初にたまたまいい結果がでてしまうと、なかなかその台を離れることができない、というのは理解できるところでしょう。
以上になります、最後までお読みいただきありがとうございました。