repryty

그리디 알고리즘

Develope
  • 2024년 03월 10일

멀티 암드 밴딧

카지노에 놀러간 여러분의 앞에는 $n$개의 서로 다른 슬롯머신이 있습니다. 레버를 당기면 랜덤한 확률로 상금(보상)을 탈 수 있는데, 각각의 슬롯머신이 상금을 주는 확률과 상금의 크기가 서로 다릅니다. 여러분은 오늘 하루동안 이 슬롯머신이 상금을 주는 확률과 상금의 크기가 서로 다릅니다. 여러분은 오늘 하루동안 이 슬롯머신을 당겨서 최대한의 보상을 받고자 합니다.

에이전트는 한정된 플레이 횟수 속에서 자신이 알고있는 가장 좋은 슬롯머신을 계속 플레이해야할까? 아니면 더 좋은 슬롯머신이 있는지 미지의 환경을 탐색해야할까?

탐색과 활용

탐색(Exploration)

아직 잘 모르는 슬롯머신을 선택해 더 많은 정보를 얻는 과정이다. 더 좋은 슬롯머신을 발견할 가능성이 있다.

활용(Exploitation)

현재까지 알려진 정보를 바탕으로, 가장 좋은 보상을 줄것으로 보이는 슬롯머신을 선택하는 과정이다.

보상 추정하기

$1$번부터 $n$번까지의 슬롯머신 $i$에 대해 각각 $n$번씩 선택했다 해보자, i번 슬롯머신을 $n$번 당겨 $n$번의 보상을 받았을때 이 $i$번 슬롯머신 가치의 추정치는 보상의 평균이다.

환경 구성하기

import gymnasium as gym
import numpy as np
#라이브러리 불러오기

class BanditEnv(gym.Env):
    def __init__(self, num_bandits):
        self.num_bandits = num_bandits # 슬롯머신의 갯수
        self.action_space = list(range(num_bandits)) # 행동은 가능한 모든 슬롯머신
        self.observation_space = [0] # 상태는 의미 없음

    def reset(self):
        # 슬롯머신의 평균 보상의 크기를 미리 결정하는 코드
        # 각 슬롯머신에 대해, 랜덤한 평균 보상의 크기를 결정해 줌.
        # self.mean = np.random.normal(size=self.num_bandits) * 10

        # 아래는 항상 같은 크기의 보상을 정해둔 코드의 예시
        # self.mean = [9, 8, 7.5, 7, 8.5, 7, 6, 7.5, 8, 8.5]
        self.mean=np.random.normal(size=self.num_bandits) * 10
        return 0 # 상태 전환 없음. 의미 없음.

    def step(self, action):
        state = 0
        mean = self.mean[action] # 정해둔 평균값에서 선택한 슬롯머신에 대한 값 확인
        reward = mean + np.random.normal() # 보상은 그 슬롯머신의 평균값 + 랜덤한 노이즈
        done = False
        return state, reward, done, {}

슬롯 머신의 환경을 구현하는 코드이다. 클래스 BanditEnv를 만들고 num_bandits와 같은 데이터를 저장해주는데, 여기서 슬롯머신 문제의 특성상 상태와같은것은 필요 없기에 적절히 설정만 해둔다. 환경의 step부분은 먼저 정해둔 각 슬롯머신의 평균값에서 랜덤한 노이즈를 더해 구현한다.

직접 구현해보기

class MyPolicy:
    def __init__(self, num_bandits):
        self.num_bandits = num_bandits # 슬롯머신 개수 저장
        # 아래에 더 저장하고싶은정보 저장가능
        self.bandits_data=[0 for i in range(num_bandits)]

    def __call__(self, state, reward):
        global howMuch
        action = 0
        if np.random.random(1)[0] <= howMuch:
            action=np.random.randint(0, self.num_bandits)
            # print("random select")
            isRandom=True
        else:
            action=self.bandits_data.index(max(self.bandits_data))
            # print("best select")
            isRandom=False
        self.bandits_data[action]=(self.bandits_data[action] + reward)/2
        # print(" ".join(map(str, self.bandits_data)))

        return action, isRandom

직접 문제 해결을 시도한 코드이다. 탐색 과정을 확률을 이용해 강제로 진행하는 방식으로 진행하였고, 외부에서 지정한 확률에 따라 랜덤한 슬롯머신을 당기거나, 평균값이 최대인 슬롯머신의 레버를 당긴다. bandits_data 리스트는 평균값을 저장하는데, bandits_data[action]=(self.bandits_data[action] + reward)/2에서 기존 평균값과 새로운 보상값을 평균내었다. 다만 이 방법은 정확한 평균값 수정이 아니었다.

env=BanditEnv(10)
state= env.reset()
agent=MyPolicy(10)
reward=0
n=20
howMuch=0.3

total_reward = []
len1, len2=[],[]
random_reward=[]

graph1=[]
graph2=[]

total_reward=0
    # howMuch=0.01*i
for t in range(n):
    action, isRandom = agent(state, reward)
    # action = 1
    # print("Chose action:", action)
    state, reward, done, _= env.step(action)
    # print("Reward:", reward)
    if isRandom: 
        random_reward.append(reward)
        len1.append(t)
    else: 
        total_reward+=reward
        len2.append(t)
    # print("="*20)
total_reward+=reward

print(env.mean[action])
print("최고의 슬롯머신의 보상 평균", max(env.mean))
print(total_reward)

9 최고의 슬롯머신의 보상 평균 9 131.73648839473503

직접 구현하려는 시도에서는 위와같이 운좋게 성공하는 경우가 있긴 했으나, 대다수 실패했다.

Image

직접 만든 코드의 시각화인데, 정상적으로 진행되지 않은걸 볼수있다.

제대로된 구현

class MyPolicy:
    def __init__(self, num_bandits):
        self.num_bandits = num_bandits # 슬롯머신 개수 저장
        initial_q=100
        self.q = [initial_q for machine in range(num_bandits)]
        self.n = [0 for machine in range(num_bandits)]

    def __call__(self, state):
        action = np.argmax(self.q)
        return action

제대로된 구현에서는 비정상적으로 높은 값에서 뽑은 값과 평균내며, 확률 없이도 전체 탐색이 가능하도록 만들어져있다.

ε-greedy 알고리즘

env = BanditEnv(10)
state = env.reset()
agent = MyPolicy(10)

# 그동안의 선택 정보를 저장
history = [100 for i in range(env.num_bandits)]
num=[1 for i in range(env.num_bandits)]

total_reward = 0
for t in range(2000):
    if np.random.random(1)[0]<=0.01:
        action = action=np.random.randint(0, env.num_bandits)
    else:
        action = agent(state)
#   action = np.random.choice(env.num_bandits)
    state, reward, done, _ = env.step(action)

    # 기록 저장
    agent.n[action]+=1
    agent.q[action]+= (reward - agent.q[action])/ agent.n[action]
    total_reward+=reward

    # agent.q = ???
    # print(f"Action: {action}")
    # print(f"Reward: {reward}")
    total_reward += reward

print(f"Total Reward: {total_reward}")

ε-그리디 알고리즘은 기존 그리디 알고리즘이 탐색을 정상적으로 진행하지 않는다는 점을 보완하여, 특정한 확률에 따라 강제적으로 탐색을 실행하도록 만들어진 알고리즘이다. 이 코드에서는 단순하게 특정 확률로 다른 에이전트를 실행하는 방식으로 구현했지만, 에이전트 클래스 내부에서 확률에 따라 달라지게 만들수도 있다.

과제

  1. 정리하기
  2. 도식화한 내용 코드짜오기
  3. 배운 내용 교재 읽어보기
  4. 사전과제 안한 것 수행
  5. 강화학습으로 풀 수 있는 주제 고민해보고 코드로 구현가능하면 해보기
검색