【強化学習、Python】Epsilon-Greedy法を使って、多腕バンディット問題を解いてみる

1. はじめに

この記事では、強化学習の一つの手法であるEpsilon-Greedy法を用いて、
コイントスを例とした多腕バンディット問題の解法について、実装します。

以下に実装を記載します。この実装では、いくつかの異なるコインの中から、表が出る確率が最も高いコインを見つけることを目指します。

【動作環境】
numpy : 1.26.4
python : 3.10

import random
import numpy as np


def ε_Greedy(ε, expectations):
    """
    εの確率でランダムに行動を選択。1-εの確率で、期待値が最大の行動を選択。
    
    Parameters
    ----------
    expectations : List[float]
        各行動に対する「期待値（=報酬 / 回数）」が格納されたリスト

    Returns
    -------
    action : int
        選択された行動（=リストのindex）
    """
    # 確率εのとき、ランダムに行動を選択
    if random.random() < ε:
        index = range(len(expectations))
        action = random.choice(index)
    # 確率1-εのとき、最も期待値が大きい行動を選択
    else:
        action = np.argmax(expectations)

    return action


def calculate_Reward(coin_head_prob):
    """
    報酬を計算
    
    Parameters
    ----------
    coin_head_prob : float
        選択されたコインの表が出る確率
    
    Returns
    -------
    reward : float
        表が出れば1, 出なければ0を報酬として返す
    """    
    # 報酬を計算
    if random.random() < coin_head_prob:
        reward = 1.0
    else:
        reward = 0.0
    
    return reward
        

def calculate_Expectation(count, expectation, reward):
    """
    報酬に基づき、期待値を（再）計算。
    コインを投げた回数 * 期待値 + 新たに得られた報酬で計算。
    
    Parameters
    ----------
    count  : int
        あるコインについて、これまでに投げられた回数
    expextation : float
        あるコインについての期待値
    reward      : float
        新たに得られた報酬
    
    Returns
    -------
    new_expectation : float
        再計算された期待値
    """   
    # 今までに得られた報酬の総和を計算
    total_reward = count * expectation + reward
    
    # 期待値を計算
    new_expectation = total_reward / (count + 1)
    
    return new_expectation


def RL(ε, coins_head_prob, max_episode_size):
    """
    強化学習の実施
    
    Parameters
    ----------
    ε                 : float
        ε_greedyのパラメータ
    coins_head_prob   : List[float]
        各コインの表が出る確率が記載されたリスト
    max_episode_steps : int
        最大ループ回数
    
    Returns
    -------
    rewards : List[float]
        1試行ごとの報酬が格納されたリスト
    coins_expectation : List[float]
        コインごとの期待値が格納されたリスト
    """  
    # コインごとに、コインを投げた回数を格納するリスト
    coins_count = [0] * len(coins_head_prob)
    
    # コインごとの、期待値を格納するリスト
    coins_expectation = [0] * len(coins_head_prob)
        
    rewards = []
    for i in range(max_episode_size):
                
        # 1. 行動方針（policy）に基づいて行動を決定
        action = ε_Greedy(ε, coins_expectation)
        
        # 2. actionに基づき報酬を計算
        reward = calculate_Reward(coins_head_prob[action])
        rewards.append(reward)
        
        # 得られた報酬に基づき、期待値を再計算
        new_e = calculate_Expectation(coins_count[action], coins_expectation[action], reward)
        
        # 更新処理
        coins_count[action] += 1
        coins_expectation[action] = new_e

    return rewards, coins_expectation


if __name__ == "__main__":
    coins_head_prob = [0.1, 0.5, 0.1, 0.8, 0.1, 0.9]
    ε = 0.1
    max_episode_size = 100
    rewards, expectations = RL(ε, coins_head_prob, max_episode_size)

    # 期待値の最も高い行動を確認
    print(np.argmax(expectations))    

2. 強化学習とは

強化学習は、「エージェント」と「環境」の相互作用によって、エージェントがより良い「行動」をとるように学習する、機械学習の一種です。

エージェントとは、「行動」の主体であり、「環境」とは「エージェント」の「行動」や前提条件に基づき、「報酬」を返すものです。

2.1 強化学習の流れ

強化学習の流れは、以下の①～③のようになります。

①エージェントは、行動方針（policy）に基づいて行動を決定します。
↓
②エージェントが何らかの「行動」を行うと、その行動に対して「環境」から「報酬」を得られます。
↓
③エージェントは「報酬」をもとに、行動方針を調整します。

①へ戻る

強化学習の説明は以上となりますが、もう少し知りたい場合、以下の本が大変参考になりました。今回の実装も、ベースはこちらの本を参考にさせて頂いてますが、自身の理解のために、少々編集しております。

機械学習スタートアップシリーズ Pythonで学ぶ強化学習 入門から実践まで (KS情報科学専門書) | 久保 隆宏 |本 | 通販 | Amazon

2.2 Epsilon-Greedy法とは

タイトルに記載しているEpsilon-Greedy法は、①の行動方針を決定するアルゴリズムの一種です。

Epsilon-Greedyは、一定の確率εでランダムに選択を行い（探索）、残りの
1-εの確率でこれまでの経験から最も良いと思われる選択を行う（活用）戦略です。

εの値によって、探索と活用のバランスを取りながら、最適な行動を学習します。εが大きいと、ランダムな行動を多くとるため報酬が増えづらい一方で、εが小さいと、特定の行動が増え、他に良い行動があっても選択されにくくなります。

---

3. 多腕バンディット問題とは

多腕バンディット問題は、複数の選択肢から最も良いものを選ぶ問題です。

各選択肢は、それぞれ異なる確率で報酬が得られますが、エージェントは、どの選択肢を選べば報酬を得やすいかは知りません。

強化学習では、エージェントは選択肢を選ぶという「行動」と、行動から得られる「報酬」をもとに、学習を繰り返すことで、選択肢の中から「報酬を最大化する」選択肢を選ぶようになります。

3.1 (例)コイントスのゲームの場合

コイントスのゲームを例に挙げて考えてみます。
1回のゲームでは、コインを1度弾き、コインの表が出たら報酬は1点、
裏が出たら報酬は0点もらえるとします。

この時、ゲームに使えるコインは6枚あり、それぞれ表が出る確率が異なるとします。例えば、表の出る確率が [0.1, 0.5, 0.1, 0.8, 0.1, 0.9] であるとします（値が高い方が、表が出やすい）。

エージェントは各コインの表が出る確率（ [0.1, 0.5, 0.1, 0.8, 0.1, 0.9]部分）を知らない状態からスタートし、ゲームを繰り返す中で、最も表が出やすいコインを見つけることを目指します。

4. 実装の解説

以降は実装の解説になります。強化学習の理論については触れておらず、各関数内で何をしているかのみ記載しています。

if __name__ == "__main__":
    coins_head_prob = [0.1, 0.5, 0.1, 0.8, 0.1, 0.9]
    ε = 0.1
    max_episode_size = 100
    rewards, expectations = RL(ε, coins_head_prob, max_episode_size)

    # 期待値の最も高い行動を確認
    print(np.argmax(expectations))    

• coins_head_probは、6枚のコインについて表が出る確率を定義しています。これらの値自体は、エージェントは知ることはできません。

• εは、Epsilon-Greedy法に利用するパラメータです。探索と活用のバランスを取ります。今回は0.1に設定しています。

• max_episode_sizeは学習のループ回数で、今回は100に設定しています。

• rewardsは、各ループごとに得られた報酬を格納したリストです。

• expectationsは、各コインごとの期待値です。
  期待値は、1ループごとに「報酬 ÷ コインを投げた回数」で計算します。
  要するに、そのコインを選ぶと、どれくらいの報酬が期待できるかを、
  コインごとに記録したものです。

• print(np.argmax(expectations))
  では、最も期待値の大きいコインのインデックスをprintしています。
  表が出る確率が高いコインほど、期待値が高くなるはずなので、
  確率0.9のコインである「5」が出力されることが望ましいです。
  ただし、確率0.8も十分高いため、「3」が出力される可能性もあります。

def RL(ε, coins_head_prob, max_episode_size):
    ...
    # コインごとに、コインを投げた回数を格納するリスト
    coins_count = [0] * len(coins_head_prob)
    
    # コインごとの、期待値を格納するリスト
    coins_expectation = [0] * len(coins_head_prob)
        
    rewards = []
    for i in range(max_episode_size):
                
        # 1. 行動方針（policy）に基づいて行動を決定
        action = ε_Greedy(ε, coins_expectation)
        
        # 2. actionに基づき報酬を計算
        reward = calculate_Reward(coins_head_prob[action])
        rewards.append(reward)
        
        # 得られた報酬に基づき、期待値を再計算
        new_e = calculate_Expectation(coins_count[action], coins_expectation[action], reward)
        
        # 更新処理
        coins_count[action] += 1
        coins_expectation[action] = new_e

    return rewards, coins_expectation

• RL関数では、2.1節で記載した流れに沿って強化学習を行ないます。

• actionは、Epsilon-Greedy法に則り、「ランダム or 期待値が最大の行動」を選択しています。行動とは、どのコインを選択するかです。

• rewardは、actionに基づき報酬を計算しています。coins_head_prob[action]によってコインを選択し、表が出れば1, 裏なら0が報酬として返ってきます。コインの表が出る確率が大きいほど表が出やすくなります。

• new_eは、得られた報酬をもとに、期待値を再計算します。表が出やすいコインほど、期待値は大きくなります。

• coins_count[action]では、これまでにコインを投げた回数を、コインごとに格納します。

• coins_expectation[action]では、再計算された期待値を、コインごとに格納します。

def ε_Greedy(ε, expectations):
    ...
    # 確率εのとき、ランダムに行動を選択
    if random.random() < ε:
        index = range(len(expectations))
        action = random.choice(index)
    # 確率1-εのとき、最も期待値が大きい行動を選択
    else:
        action = np.argmax(expectations)

    return action

• ε_Greedy関数では、Epsilon-Greedy法に基づき行動を決定します。

• 確率εのとき、ランダムに行動を選択し、確率1-εのとき、最も期待値が大きい行動を選択します。

• 表が出やすいコインほど期待値も大きくなるため、学習を繰り返すと、表が出やすいコインが選択されやすくなります。

def calculate_Reward(coin_head_prob):  
    ...
    if random.random() < coin_head_prob:
        reward = 1.0
    else:
        reward = 0.0
    
    return reward

• calculate_Reward関数では、報酬を計算します。

• random.random() < coin_head_probは「表」が出た場合を表す条件式で、1を返します。それ以外は0を返します。

def calculate_Expectation(count, expectation, reward):
    ... 
    # 今までに得られた報酬の総和を計算
    total_reward = count * expectation + reward
    
    # 期待値を計算
    new_expectation = total_reward / (count + 1)
    
    return new_expectation

• calculate_Expectatio関数は、新たに得られた報酬と、過去に得られた報酬から期待値を計算します。

5. 所感

実装によって、基本的な強化学習のアルゴリズムは学べました。
今後は異なる強化学習アルゴリズムについて記事を書きたいと思います。

以上となります。
最後まで読んで頂き、誠にありがとうございました。

参考

機械学習スタートアップシリーズ Pythonで学ぶ強化学習 入門から実践まで (KS情報科学専門書) | 久保 隆宏 |本 | 通販 | Amazon