Epsilon-Greedy法で満足度の高いレストランの見つけ方を考えてみた #Python

目的

Pythonで学ぶ強化学習の 3.1 で強化学習の1つの手法である Epsilon-Greedy 法の解説の中に「表が出る確率が異なる複数枚のコインを投げて、表が出やすいコインを探索し、その結果を活用しながら報酬を最大にする」というゲームがサンプルコードと共に紹介されていました。
そのコイン投げゲームを応用して、「普段の外食で利用するレストランの探索と活用の割合（例：10回ランチの機会のうち2回は新しいお店を探して、8回は馴染みの店に行くみたいな割合）として何割くらいが良さげなのか？」という問いを以下のような簡易なモデルで検討してみました。

モデル

選択したレストランの評価は、そのレストランの口コミ評価を平均、分散 $σ=0.5$ とした正規分布に従った乱数として表します
選択したレストランに満足したかどうかという判断は、「行くことを検討した複数のお店の口コミ評価の平均値より高い評価がその回のそのレストランの選択に対して得られたかどうか」でおこないます
- 特に、今回、実際に会社近くのランチのお店を10店舗調べて、Google の口コミレビュー評価の値として [2.8, 4.1, 3.5, 4.1, 3.7, 3.9, 3.6, 3.4, 4.0, 3.6] という値を用いました
選択したレストランに満足した場合の報酬は 1 で、満足しなかった場合の報酬は 0 とします
普段の外食で利用するレストランの探索と活用の割合 は Epsilon-Greedy法の $\epsilon$ に相当するパラメータで 今回 [0.0, 0.1, 0.2, 0.3, 0.8] （0% or 10% or 20% or 30% or 80%）という割合について 結果を確認しました。

結果

下記図の横軸はレストラン選択回数、縦軸は1回のレストラン選択あたりの報酬（0以上1以下の範囲を取りうる）です。
普段の外食で利用するレストランの探索と活用の割合として良い方から順番に 10% > 20% > 30% > 80% > 0% という結果になりました。
つまり、「10回外食するうちの1回くらいは行き慣れたお店だけじゃないランダムにお店を選んだ方が長い目で見ると満足度の高いレストランを見つけて活用することができるようになる」ということを示唆していそうです（あくまで上記モデルの上での話）。

コード

Pythonで学ぶ強化学習の 3.1 の Epsilon-Greedy法のサンプルコードを適宜上記モデルに合わせて書き換えたものが下記です。
計算実行は Google の Colaboratory 上で Python3 で実施しました。計算時間としては数10秒 or 1分程度でした。

ChoiceRestaurantクラス（上記簡易モデル含）

import random
import numpy as np

class ChoiceRestaurant():

  def __init__(self, online_reviews, max_episode_steps=30):
    self.online_reviews = online_reviews
    self.max_episode_steps = max_episode_steps
    self.toss_count = 0

  def __len__(self):
    return len(self.online_reviews)

  def reset(self):
    self.toss_count = 0

  def step(self, action):
    final = self.max_episode_steps - 1
    if self.toss_count > final:
      raise Exception("The step count exceeded maximum. Please reset env.")
    else:
      done = True if self.toss_count == final else False

    if action >= len(self.online_reviews):
      raise Exception("The No.{} restaurant doesn't exitst.".format(action))
    else:
      average_online_reviews = sum(self.online_reviews)/len(self.online_reviews)
      online_review = self.online_reviews[action]
      sigma = 0.5
      if average_online_reviews < random.gauss(online_review, sigma):
        reward = 1.0
      else:
        reward = 0.0
      self.toss_count += 1
      return reward, done

Epsilon-Greedy法の計算実行クラス

class EpsilonGreedyAgent():

  def __init__(self, epsilon):
    self.epsilon = epsilon
    self.V = []

  def policy(self):
    restaurants = range(len(self.V))
    if random.random() < self.epsilon:
      return random.choice(restaurants)
    else:
      return np.argmax(self.V)

  def play(self, env):
    # Initialize estimation.
    N = [0] * len(env)
    self.V = [0] * len(env)
    env.reset()
    done = False
    rewards = []
    while not done:
      selected_restaurant = self.policy()
      reward, done = env.step(selected_restaurant)
      rewards.append(reward)

      n = N[selected_restaurant]
      restaurant_average = self.V[selected_restaurant]
      new_average = (restaurant_average * n + reward) / (n+1)
      N[selected_restaurant] += 1
      self.V[selected_restaurant] = new_average

    return rewards

具体的な評価レビュー/epsilon値を入れて計算実行しグラフ描画

if __name__ == "__main__":
  import pandas as pd
  import matplotlib.pyplot as plt

  def main():
    env = ChoiceRestaurant([2.8, 4.1, 3.5, 4.1, 3.7, 3.9, 3.6, 3.4, 4.0, 3.6])
    epsilons = [0.0, 0.1, 0.2, 0.3, 0.8]
    game_steps = list(range(10, 3010, 10))
    result = {}
    for e in epsilons:
      agent = EpsilonGreedyAgent(epsilon=e)
      means = []
      for s in game_steps:
        env.max_episode_steps = s
        rewards = agent.play(env)
        means.append(np.mean(rewards))
      result["epsilon={}".format(e)] = means
    result["restaurant choice count"] = game_steps
    result = pd.DataFrame(result)
    result.set_index("restaurant choice count", drop=True, inplace=True)
    result.plot.line(figsize=(10,5))
    plt.show()

  main()

参考

Pythonで学ぶ強化学習の 3.1 節
Epsilon-Greedy法のサンプルコード