$\star$ 목표: 일주일에 몇 장씩이라도 보기!

1

심층강화학습 deep reinforcement learning DRL 이란 머신 러닝 기법 중 하나.

  • 지능이 요구되는 문제를 해결할 수 있도록 인공지능 컴퓨터 프로그램을 개발하는데 사용
  • 시행착오를 통해 얻은 반응을 학습

심층 강화학습은 문제에 대한 접근법이다.

  • 에이전트agent: 의사를 결정하는 객체 자체
    • ex) 사물을 집는 로봇 학습시킬때 의사 결정을 좌우하는 코드와 연관
  • 환경unvironmnet: 에이전트(의사 결정) 이외의 모든 것
    • ex) 의사결정하는 로봇(객체) 제외한 모든 것이 환경의 일부
  • 상태 영역state space: 변수가 가질 수 있는 모든 값들의 집합
  • 관찰observation: 에이전트가 관찰할 수 있는 상태의 일부
  • 전이 함수transition function 에이전트와 환경 사이의 관계를 정의한 함수
  • 보상 함수reward function: 행동에 대한 반응으로 환경이 제공한 보상 신호와 관련된 함수
  • 모델model: 전이와 보상함수를 표현 가능

에이전트의 3단계 과정

  1. 환경과 상호작용을 나누고
  2. 행동에 대해서 평가를 하며,
  3. 받은 반응을 개선시킨다.
  • 에피소드형 업무episodic task: 게임과 같이 자연적으로 끝나는 업무
  • 연속형업무continuing task: 앞으로 가는 동작을 학습하는 경우

  • 연속형 피드백이 야기하는 문제

    • 시간적 가치 할당 문제tamporal credit assignment problem:문제에 시간적 개념이 들어가 있고, 행동에도 지연된 속성이 담겨 있으면, 보상에 대한 가치를 부여하기 어렵다.
  • 평가 가능한 피드백이 야기하는 문제
    • 탐험과 착취 간의 트레이드 오프exploration versus explotation trade-off: 에이전트는 현재 가지고 있는 정보에서 얻을 수 있는 가장 좋은 것과 정보를 새로 얻는 것 간의 균형을 맞출 수 있어야 한다.

2

에이전트의 세 단계 과정

  1. 모든 에이전트는 상호작용 요소를 가지고 있고, 학습에 필요한 데이터를 수집한다.
  2. 모든 에이전트들은 현재 취하고 있는 행동을 평가하고,
  3. 전체적인 성능을 개선하기 위해 만들어진 무언가를 개선한다.
  • 상태 영역state space: 표현할 수 있는 변수들의 모든 값에 대한 조합
  • 관찰observation: 에이전트가 어떤 특정 시간에 얻을 수 있는 변수들의 집합
  • 관찰 영역observation space: 변수들이 가질 수 있는 모든 값들의 조합
  • 행동 영역action space: 모든 상태에서 취할 수 있는 모든 행동에 대한 집합
  • 전이 함수transition function: 환경은 에이전트의 행동에 대한 반응으로 상태를 변화할 수 있는데 이와 관련된 함수
  • 보상 함수reward function: 행동과 관련된 보상에 대한 함수
  • 모델mpdel: 전이와 보상 함수의 표현

보상 신호가 밀집되어 있을수록, 에이전트의 직관성과 학습속도가 높아지지만, 에이전트에게 편견을 주입하게 되어, 결국 에이전트가 예상하지 못한 행동을 할 가능성은 적어지게 된다. 반면, 보상 신호가 적을수록 직관성이 낮아져 에이전트가 새로운 행동을 취할 확률이 높아지지만, 그만큼 에이전트르르 학습시키는데 오래 걸리게 될 것이다.

  • 타임 스텝time step: 상호작용이 진행되는 사이클, 시간의 단위
  • 경험 튜플experience tuple: 관찰 또는 상태, 행동, 보상 그리고 새로운 관찰
  • 에피소드형 업무episodic task: 게임과 같이 자연적으로 끝나는 업무 - 에피소드episode
  • 연속형 업무continuing task: 앞으로 전진하는 동작과 같이 자연적으로 끝나는 업무
  • 반환값return: 에피소드 동안 수집된 보상의 총합
  • 상태state: 문제에 포함되어 있는 독특하고, 자기 자신만의 설정이 담긴 요소
  • 상태 영역state square: 모든 가능한 상태, 집합 S로 표현,

마르코프 결정 과정Markov decision process MDP

  • 수학 프레임워크, 이를 이용해서 강화학습 환경을 연속적인 의사결정 문제로 표현하는 방법 학습.
  • 일반적인 형태는 불확실성상에 놓여진 상황에서 어떠한 복잡한 연속적 결정을 가상으로 모델링해서, 강화학습 에이전트가 모델과 반응을 주고받고, 경험을 통해서 스스로 학습할 수 있게 해준다.
  • 모든 상태들의 집합S
  • 모든 시작 상태starting state 혹은 초기 상태initial state라고 부르는 S+의 부분집합이 있음
  • MDP와의 상호작용 시작하면서 어떤 S에서의 특정 상태에서 어떤 확률 붙포 간의 관계를 그릴 수 있는데 이때 이 확률 분포는 무엇이든 될 수 있지만, 학습이 이뤄지는 동안에는 고정되어 있어야 한다.
    • 즉, 이 확률 분포에서 샘플링된 확률은 학습과 에이전트 검증의 처름 에피소드부터 마지막 에피소드까지는 항상 동일해야 한다는 것
  • 흡수absorbing 또는 종료 상태terminal state 라는 특별한 상태도 존재.
    • 종료 상태(꼭 하나는 아님) 이외의 모든 상태들을 S라고 표현

MDP에서는

  • A: 상태에 따라 결정되는 행동의 집합
    • $\therefore$ 특정 상태에서 허용되지 않는 행동도 존재한다는 말.
    • 상태(s)를 인자로 받는 함수.
    • A(s); 상태(s)에서 취할 수 있는 행동들의 집합 반환, 상수 정의 가능.
  • 행동 영역은 유한 혹은 무한 가능,
    • 단일 행동에 대한 변수들의 집합은 한 개 이상의 료소를 가질 수 있고, 유한해야 함.
    • $\therefore$ 대부분의 환경에서 모든 상태에서 취할 수 있는 행동의 수는 같도록 설계됨

상태-전이 확률state-transition probability = 전이 함수

  • $T(s,a,s')$
  • 전이함수$T$는 각 전이 튜플인 $(s,a,s')$을 확률과 연결시켜준다.
  • 어떤 상태 s에서 행동 a를 취하고 다음 상태가 s'이 되었을 때, 이때의 확률을 반환해준다는 뜻
  • 이 확률의 합은 1 $$p(s'|s,a) = P(S_t = s'|S_{t-1} = s,A_{t-1}=a)$$ $$\sum_{s' \in S}p(s'|s,a) = a, \forall s \in S, \forall a \in A(s)$$

보상 함수$R$

  • 전이 튜플 $s,a,s'$을 특정한 스칼라 값으로 매핑,
    • 양수 보상 = 수익 또는 이득
    • 음수 보상 = 비용, 벌칙, 패널티
  • $R(s,a,s')$ = $R(s,a)$ = $R(s)$
  • 보상 함수를 표현하는 가장 명확한 방법은 상태와 행동 그리고 다음 상태, 이 세 가지를 함께 쓰는 것 $$r(s,a) = \mathbb{E} [R_t|S_{t-1} = s,A_{t-1} = a]$$ $$r(s,a,s') = \mathbb{E} [R_t|S_{t-1} = s, A_{t-1} = a, S_t= s']$$ $$R_t \in \cal{R} \subset \mathbb{R}$$

호라이즌horixon

  • 계획 호라이즌planning horizon: 에피소드형 업무나 연속적 업무를 에이전트의 관점에서 정의
    • 유한 호라이즌finite horizon: 에이전트가 유한한 타임 스템 내에 업무가 종료된다는 것을 알고 있는 계획 호라이즌
    • 탐욕 호라이즌greedy horizon: 계획 호라이즌이 1인 경우
    • 무한 호라이즌infinite horiaon 에이전트한테 미리 정의된 타임 스텝에 대한 제한이 없어 에이전트가 무한하게 계획할 수 있음
      • 특히, 무한한 계획 호라이즌을 가지는 업무는 무기한 호라이즌 업무indefinite horizon task 라고 부름
  • 에이전트가 타임 스텝 루프에 빠지는 것을 막기 위해 타임 스텝을 제한하기도 한다.

감가율discount factor = 감마gamma

  • 받았던 보상의 시점이 미래로 더 멀어질수록, 현재 시점에서는 이에 대한 가치를 더 낮게 평가

  • 환경; 자세한 예제; 5개의 미끄러지는 칸을 가지는 환경slippery walk five, SWF $$G_t = R_{t+1} + R_{t+2} + R_{t+3} + \dots R_T$$ $$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots +\gamma^{T-1} R_T$$ $$G_t = \sum^{\infty}_{k=0} \gamma^k R_{t+k+1}$$ $$G_t = R_{t+1}+ \gamma G_{t+1}$$

# deterministic environment (100% action success)
# 1 non-terminal states, 2 terminal states
# only reward is still at the right-most cell in the "walk"
# episodic environment, the agent terminates at the left- or right-most cell (after 1 action selection -- any action)
# agent starts in state 1 (middle of the walk) T-1-T
# actions left (0) or right (1)
P = {
    0: {
        0: [(1.0, 0, 0.0, True)],
        1: [(1.0, 0, 0.0, True)]
    },
    1: {
        0: [(1.0, 0, 0.0, True)],
        1: [(1.0, 2, 1.0, True)]
    },
    2: {
        0: [(1.0, 2, 0.0, True)],
        1: [(1.0, 2, 0.0, True)]
    }
}

# import gym, gym_walk
# P = gym.make('BanditWalk-v0').env.P
P
{0: {0: [(1.0, 0, 0.0, True)], 1: [(1.0, 0, 0.0, True)]},
 1: {0: [(1.0, 0, 0.0, True)], 1: [(1.0, 2, 1.0, True)]},
 2: {0: [(1.0, 2, 0.0, True)], 1: [(1.0, 2, 0.0, True)]}}
# stochastic environment (80% action success, 20% backwards)
# 1 non-terminal states, 2 terminal states
# only reward is still at the right-most cell in the "walk"
# episodic environment, the agent terminates at the left- or right-most cell
# agent starts in state 1 (middle of the walk) T-1-T
# actions left (0) or right (1)
P = {
    0: {
        0: [(1.0, 0, 0.0, True)],
        1: [(1.0, 0, 0.0, True)]
    },
    1: {
        0: [(0.8, 0, 0.0, True), (0.2, 2, 1.0, True)],
        1: [(0.8, 2, 1.0, True), (0.2, 0, 0.0, True)]
    },
    2: {
        0: [(1.0, 2, 0.0, True)],
        1: [(1.0, 2, 0.0, True)]
    }
}

# import gym, gym_walk
# P = gym.make('BanditSlipperyWalk-v0').env.P
P
{0: {0: [(1.0, 0, 0.0, True)], 1: [(1.0, 0, 0.0, True)]},
 1: {0: [(0.8, 0, 0.0, True), (0.2, 2, 1.0, True)],
  1: [(0.8, 2, 1.0, True), (0.2, 0, 0.0, True)]},
 2: {0: [(1.0, 2, 0.0, True)], 1: [(1.0, 2, 0.0, True)]}}
# Walk three: 
# deterministic environment
# 3 non-terminal states, 2 terminal states
# only reward is at the right-most cell in the walk
# episodic environment, the agent terminates at the left- or right-most cell
# agent starts in state 2 (middle of the walk) T-1-2-3-T
# actions left (0) or right (1)
P = {
    0: {
        0: [(1.0, 0, 0.0, True)],
        1: [(1.0, 0, 0.0, True)]
    },
    1: {
        0: [(1.0, 0, 0.0, True)],
        1: [(1.0, 2, 0.0, False)]
    },
    2: {
        0: [(1.0, 1, 0.0, False)],
        1: [(1.0, 3, 0.0, False)]
    },
    3: {
        0: [(1.0, 2, 0.0, False)],
        1: [(1.0, 4, 1.0, True)]
    },
    4: {
        0: [(1.0, 4, 0.0, True)],
        1: [(1.0, 4, 0.0, True)]
    }
}

# import gym, gym_walk
# P = gym.make('WalkThree-v0').env.P
P
# Slippery Walk Three: 
# stochastic environment (50% action success, 33.33% stays, 16.66% backwards)
# 3 non-terminal states, 2 terminal states
# only reward is still at the right-most cell in the walk
# episodic environment, the agent terminates at the left- or right-most cell
# agent starts in state 2 (middle of the walk) T-1-2-3-T
# actions left (0) or right (1)
P = {
    0: {
        0: [(1.0, 0, 0.0, True)],
        1: [(1.0, 0, 0.0, True)]
    },
    1: {
        0: [(0.5000000000000001, 0, 0.0, True),
            (0.3333333333333333, 1, 0.0, False),
            (0.16666666666666666, 2, 0.0, False)
        ],
        1: [(0.5000000000000001, 2, 0.0, False),
            (0.3333333333333333, 1, 0.0, False),
            (0.16666666666666666, 0, 0.0, True)
        ]
    },
    2: {
        0: [(0.5000000000000001, 1, 0.0, False),
            (0.3333333333333333, 2, 0.0, False),
            (0.16666666666666666, 3, 0.0, False)
        ],
        1: [(0.5000000000000001, 3, 0.0, False),
            (0.3333333333333333, 2, 0.0, False),
            (0.16666666666666666, 1, 0.0, False)
        ]
    },
    3: {
        0: [(0.5000000000000001, 2, 0.0, False),
            (0.3333333333333333, 3, 0.0, False),
            (0.16666666666666666, 4, 1.0, True)
        ],
        1: [(0.5000000000000001, 4, 1.0, True),
            (0.3333333333333333, 3, 0.0, False),
            (0.16666666666666666, 2, 0.0, False)
        ]
    },
    4: {
        0: [(1.0, 4, 0.0, True)],
        1: [(1.0, 4, 0.0, True)]
    }
}

# import gym, gym_walk
# P = gym.make('SlipperyWalkThree-v0').env.P
P

collapse

# Random Walk: 
# highly stochastic environment (50% action success, 50% backwards)
# 5 non-terminal states, 2 terminal states
# only reward is still at the right-most cell in the "walk"
# episodic environment, the agent terminates at the left- or right-most cell
# agent starts in state 3 (middle of the walk) T-1-2-3-4-5-T
# actions left (0) or right (1), which don't really make a difference since walk is random
P = {
    0: {
        0: [(1.0, 0, 0.0, True)],
        1: [(1.0, 0, 0.0, True)]
    },
    1: {
        0: [(0.5, 0, 0.0, True), (0.5, 2, 0.0, False)],
        1: [(0.5, 2, 0.0, False), (0.5, 0, 0.0, True)]
    },
    2: {
        0: [(0.5, 1, 0.0, False), (0.5, 3, 0.0, False)],
        1: [(0.5, 3, 0.0, False), (0.5, 1, 0.0, False)]
    },
    3: {
        0: [(0.5, 2, 0.0, False), (0.5, 4, 0.0, False)],
        1: [(0.5, 4, 0.0, False), (0.5, 2, 0.0, False)]
    },
    4: {
        0: [(0.5, 3, 0.0, False), (0.5, 5, 0.0, False)],
        1: [(0.5, 5, 0.0, False), (0.5, 3, 0.0, False)]
    },
    5: {
        0: [(0.5, 4, 0.0, False), (0.5, 6, 1.0, True)],
        1: [(0.5, 6, 1.0, True), (0.5, 4, 0.0, False)]
    },
    6: {
        0: [(1.0, 6, 0.0, True)],
        1: [(1.0, 6, 0.0, True)]
    }
}

# import gym, gym_walk
# P = gym.make('RandomWalk-v0').env.P
P
# Russell and Norvig's Gridworld: 
# stochastic environment (80% action success, 20.00% split evenly in right angles)
# 3x4 grid, 12 states 0-11
# -0.04 time step penalty, 
# +1 for landing in state 3 (top right corner), 
# -1 for landing in state 7 (below state 3)
# state 5 is a wall, agents attempting to get in that cell will bounce back
# episodic environment, the agent terminates when it lands in state 3 or 7
# agent starts in state 0 (top left corner)
# actions left (0), down (1), right (2), up (3)
P = {
    0: {
        0: [(0.9, 0, -0.04, False),
            (0.1, 4, -0.04, False)
        ],
        1: [(0.1, 0, -0.04, False), (0.8, 4, -0.04, False), (0.1, 1, -0.04, False)],
        2: [(0.1, 4, -0.04, False), (0.8, 1, -0.04, False), (0.1, 0, -0.04, False)],
        3: [(0.1, 1, -0.04, False), (0.8, 0, -0.04, False), (0.1, 0, -0.04, False)]
    },
    1: {
        0: [(0.2, 1, -0.04, False),
            (0.8, 0, -0.04, False)
        ],
        1: [(0.1, 0, -0.04, False), (0.8, 1, -0.04, False), (0.1, 2, -0.04, False)],
        2: [(0.1, 1, -0.04, False), (0.8, 2, -0.04, False), (0.1, 1, -0.04, False)],
        3: [(0.1, 2, -0.04, False), (0.8, 1, -0.04, False), (0.1, 0, -0.04, False)]
    },
    2: {
        0: [(0.1, 2, -0.04, False),
            (0.8, 1, -0.04, False),
            (0.1, 6, -0.04, False)
        ],
        1: [(0.1, 1, -0.04, False), (0.8, 6, -0.04, False), (0.1, 3, 0.96, True)],
        2: [(0.1, 6, -0.04, False), (0.8, 3, 0.96, True), (0.1, 2, -0.04, False)],
        3: [(0.1, 3, 0.96, True), (0.8, 2, -0.04, False), (0.1, 1, -0.04, False)]
    },
    3: {
        0: [(1.0, 3, 0, True)],
        1: [(1.0, 3, 0, True)],
        2: [(1.0, 3, 0, True)],
        3: [(1.0, 3, 0, True)]
    },
    4: {
        0: [(0.1, 0, -0.04, False),
            (0.8, 4, -0.04, False),
            (0.1, 8, -0.04, False)
        ],
        1: [(0.2, 4, -0.04, False), (0.8, 8, -0.04, False)],
        2: [(0.1, 8, -0.04, False), (0.8, 4, -0.04, False), (0.1, 0, -0.04, False)],
        3: [(0.2, 4, -0.04, False), (0.8, 0, -0.04, False)]
    },
    5: {
        0: [(1.0, 5, 0, True)],
        1: [(1.0, 5, 0, True)],
        2: [(1.0, 5, 0, True)],
        3: [(1.0, 5, 0, True)]
    },
    6: {
        0: [(0.1, 2, -0.04, False),
            (0.8, 6, -0.04, False),
            (0.1, 10, -0.04, False)
        ],
        1: [(0.1, 6, -0.04, False), (0.8, 10, -0.04, False), (0.1, 7, -1.04, True)],
        2: [(0.1, 10, -0.04, False), (0.8, 7, -1.04, True), (0.1, 2, -0.04, False)],
        3: [(0.1, 7, -1.04, True), (0.8, 2, -0.04, False), (0.1, 6, -0.04, False)]
    },
    7: {
        0: [(1.0, 7, 0, True)],
        1: [(1.0, 7, 0, True)],
        2: [(1.0, 7, 0, True)],
        3: [(1.0, 7, 0, True)]
    },
    8: {
        0: [(0.1, 4, -0.04, False),
            (0.9, 8, -0.04, False)
        ],
        1: [(0.9, 8, -0.04, False), (0.1, 9, -0.04, False)],
        2: [(0.1, 8, -0.04, False), (0.8, 9, -0.04, False), (0.1, 4, -0.04, False)],
        3: [(0.1, 9, -0.04, False), (0.8, 4, -0.04, False), (0.1, 8, -0.04, False)]
    },
    9: {
        0: [(0.2, 9, -0.04, False),
            (0.8, 8, -0.04, False)
        ],
        1: [(0.1, 8, -0.04, False), (0.8, 9, -0.04, False), (0.1, 10, -0.04, False)],
        2: [(0.2, 9, -0.04, False), (0.8, 10, -0.04, False)],
        3: [(0.1, 10, -0.04, False),
            (0.8, 9, -0.04, False),
            (0.1, 8, -0.04, False)
        ]
    },
    10: {
        0: [(0.1, 6, -0.04, False),
            (0.8, 9, -0.04, False),
            (0.1, 10, -0.04, False)
        ],
        1: [(0.1, 9, -0.04, False),
            (0.8, 10, -0.04, False),
            (0.1, 11, -0.04, False)
        ],
        2: [(0.1, 10, -0.04, False),
            (0.8, 11, -0.04, False),
            (0.1, 6, -0.04, False)
        ],
        3: [(0.1, 11, -0.04, False),
            (0.8, 6, -0.04, False),
            (0.1, 9, -0.04, False)
        ]
    },
    11: {
        0: [(0.1, 7, -1.04, True),
            (0.8, 10, -0.04, False),
            (0.1, 11, -0.04, False)
        ],
        1: [(0.1, 10, -0.04, False),
            (0.9, 11, -0.04, False)
        ],
        2: [(0.9, 11, -0.04, False), (0.1, 7, -1.04, True)],
        3: [(0.1, 11, -0.04, False),
            (0.8, 7, -1.04, True),
            (0.1, 10, -0.04, False)
        ]
    }
}

# import gym, gym_aima
# P = gym.make('RussellNorvigGridworld-v0').env.P
P
# Frozen Lake Gridworld: 
# highly stochastic environment (33.33% action success, 66.66% split evenly in right angles)
# 4x4 grid, 16 states 0-15
# +1 for landing in state 15 (top bottom corner) 0 otherwise
# states 5, 7, 11, and 12 are holes, agents die in holes, no penalty, just end of episode
# state 15 is the goal, reaching it ends the episode too
# agent starts in state 0 (top left corner)
# actions left (0), down (1), right (2), up (3)
P = {
    0: {
        0: [(0.6666666666666666, 0, 0.0, False),
            (0.3333333333333333, 4, 0.0, False)
        ],
        1: [(0.3333333333333333, 0, 0.0, False),
            (0.3333333333333333, 4, 0.0, False),
            (0.3333333333333333, 1, 0.0, False)
        ],
        2: [(0.3333333333333333, 4, 0.0, False),
            (0.3333333333333333, 1, 0.0, False),
            (0.3333333333333333, 0, 0.0, False)
        ],
        3: [(0.3333333333333333, 1, 0.0, False),
            (0.6666666666666666, 0, 0.0, False)
        ]
    },
    1: {
        0: [(0.3333333333333333, 1, 0.0, False),
            (0.3333333333333333, 0, 0.0, False),
            (0.3333333333333333, 5, 0.0, True)
        ],
        1: [(0.3333333333333333, 0, 0.0, False),
            (0.3333333333333333, 5, 0.0, True),
            (0.3333333333333333, 2, 0.0, False)
        ],
        2: [(0.3333333333333333, 5, 0.0, True),
            (0.3333333333333333, 2, 0.0, False),
            (0.3333333333333333, 1, 0.0, False)
        ],
        3: [(0.3333333333333333, 2, 0.0, False),
            (0.3333333333333333, 1, 0.0, False),
            (0.3333333333333333, 0, 0.0, False)
        ]
    },
    2: {
        0: [(0.3333333333333333, 2, 0.0, False),
            (0.3333333333333333, 1, 0.0, False),
            (0.3333333333333333, 6, 0.0, False)
        ],
        1: [(0.3333333333333333, 1, 0.0, False),
            (0.3333333333333333, 6, 0.0, False),
            (0.3333333333333333, 3, 0.0, False)
        ],
        2: [(0.3333333333333333, 6, 0.0, False),
            (0.3333333333333333, 3, 0.0, False),
            (0.3333333333333333, 2, 0.0, False)
        ],
        3: [(0.3333333333333333, 3, 0.0, False),
            (0.3333333333333333, 2, 0.0, False),
            (0.3333333333333333, 1, 0.0, False)
        ]
    },
    3: {
        0: [(0.3333333333333333, 3, 0.0, False),
            (0.3333333333333333, 2, 0.0, False),
            (0.3333333333333333, 7, 0.0, True)
        ],
        1: [(0.3333333333333333, 2, 0.0, False),
            (0.3333333333333333, 7, 0.0, True),
            (0.3333333333333333, 3, 0.0, False)
        ],
        2: [(0.3333333333333333, 7, 0.0, True),
            (0.6666666666666666, 3, 0.0, False)
        ],
        3: [(0.6666666666666666, 3, 0.0, False),
            (0.3333333333333333, 2, 0.0, False)
        ]
    },
    4: {
        0: [(0.3333333333333333, 0, 0.0, False),
            (0.3333333333333333, 4, 0.0, False),
            (0.3333333333333333, 8, 0.0, False)
        ],
        1: [(0.3333333333333333, 4, 0.0, False),
            (0.3333333333333333, 8, 0.0, False),
            (0.3333333333333333, 5, 0.0, True)
        ],
        2: [(0.3333333333333333, 8, 0.0, False),
            (0.3333333333333333, 5, 0.0, True),
            (0.3333333333333333, 0, 0.0, False)
        ],
        3: [(0.3333333333333333, 5, 0.0, True),
            (0.3333333333333333, 0, 0.0, False),
            (0.3333333333333333, 4, 0.0, False)
        ]
    },
    5: {
        0: [(1.0, 5, 0, True)],
        1: [(1.0, 5, 0, True)],
        2: [(1.0, 5, 0, True)],
        3: [(1.0, 5, 0, True)]
    },
    6: {
        0: [(0.3333333333333333, 2, 0.0, False),
            (0.3333333333333333, 5, 0.0, True),
            (0.3333333333333333, 10, 0.0, False)
        ],
        1: [(0.3333333333333333, 5, 0.0, True),
            (0.3333333333333333, 10, 0.0, False),
            (0.3333333333333333, 7, 0.0, True)
        ],
        2: [(0.3333333333333333, 10, 0.0, False),
            (0.3333333333333333, 7, 0.0, True),
            (0.3333333333333333, 2, 0.0, False)
        ],
        3: [(0.3333333333333333, 7, 0.0, True),
            (0.3333333333333333, 2, 0.0, False),
            (0.3333333333333333, 5, 0.0, True)
        ]
    },
    7: {
        0: [(1.0, 7, 0, True)],
        1: [(1.0, 7, 0, True)],
        2: [(1.0, 7, 0, True)],
        3: [(1.0, 7, 0, True)]
    },
    8: {
        0: [(0.3333333333333333, 4, 0.0, False),
            (0.3333333333333333, 8, 0.0, False),
            (0.3333333333333333, 12, 0.0, True)
        ],
        1: [(0.3333333333333333, 8, 0.0, False),
            (0.3333333333333333, 12, 0.0, True),
            (0.3333333333333333, 9, 0.0, False)
        ],
        2: [(0.3333333333333333, 12, 0.0, True),
            (0.3333333333333333, 9, 0.0, False),
            (0.3333333333333333, 4, 0.0, False)
        ],
        3: [(0.3333333333333333, 9, 0.0, False),
            (0.3333333333333333, 4, 0.0, False),
            (0.3333333333333333, 8, 0.0, False)
        ]
    },
    9: {
        0: [(0.3333333333333333, 5, 0.0, True),
            (0.3333333333333333, 8, 0.0, False),
            (0.3333333333333333, 13, 0.0, False)
        ],
        1: [(0.3333333333333333, 8, 0.0, False),
            (0.3333333333333333, 13, 0.0, False),
            (0.3333333333333333, 10, 0.0, False)
        ],
        2: [(0.3333333333333333, 13, 0.0, False),
            (0.3333333333333333, 10, 0.0, False),
            (0.3333333333333333, 5, 0.0, True)
        ],
        3: [(0.3333333333333333, 10, 0.0, False),
            (0.3333333333333333, 5, 0.0, True),
            (0.3333333333333333, 8, 0.0, False)
        ]
    },
    10: {
        0: [(0.3333333333333333, 6, 0.0, False),
            (0.3333333333333333, 9, 0.0, False),
            (0.3333333333333333, 14, 0.0, False)
        ],
        1: [(0.3333333333333333, 9, 0.0, False),
            (0.3333333333333333, 14, 0.0, False),
            (0.3333333333333333, 11, 0.0, True)
        ],
        2: [(0.3333333333333333, 14, 0.0, False),
            (0.3333333333333333, 11, 0.0, True),
            (0.3333333333333333, 6, 0.0, False)
        ],
        3: [(0.3333333333333333, 11, 0.0, True),
            (0.3333333333333333, 6, 0.0, False),
            (0.3333333333333333, 9, 0.0, False)
        ]
    },
    11: {
        0: [(1.0, 11, 0, True)],
        1: [(1.0, 11, 0, True)],
        2: [(1.0, 11, 0, True)],
        3: [(1.0, 11, 0, True)]
    },
    12: {
        0: [(1.0, 12, 0, True)],
        1: [(1.0, 12, 0, True)],
        2: [(1.0, 12, 0, True)],
        3: [(1.0, 12, 0, True)]
    },
    13: {
        0: [(0.3333333333333333, 9, 0.0, False),
            (0.3333333333333333, 12, 0.0, True),
            (0.3333333333333333, 13, 0.0, False)
        ],
        1: [(0.3333333333333333, 12, 0.0, True),
            (0.3333333333333333, 13, 0.0, False),
            (0.3333333333333333, 14, 0.0, False)
        ],
        2: [(0.3333333333333333, 13, 0.0, False),
            (0.3333333333333333, 14, 0.0, False),
            (0.3333333333333333, 9, 0.0, False)
        ],
        3: [(0.3333333333333333, 14, 0.0, False),
            (0.3333333333333333, 9, 0.0, False),
            (0.3333333333333333, 12, 0.0, True)
        ]
    },
    14: {
        0: [(0.3333333333333333, 10, 0.0, False),
            (0.3333333333333333, 13, 0.0, False),
            (0.3333333333333333, 14, 0.0, False)
        ],
        1: [(0.3333333333333333, 13, 0.0, False),
            (0.3333333333333333, 14, 0.0, False),
            (0.3333333333333333, 15, 1.0, True)
        ],
        2: [(0.3333333333333333, 14, 0.0, False),
            (0.3333333333333333, 15, 1.0, True),
            (0.3333333333333333, 10, 0.0, False)
        ],
        3: [(0.3333333333333333, 15, 1.0, True),
            (0.3333333333333333, 10, 0.0, False),
            (0.3333333333333333, 13, 0.0, False)
        ]
    },
    15: {
        0: [(1.0, 15, 0, True)],
        1: [(1.0, 15, 0, True)],
        2: [(1.0, 15, 0, True)],
        3: [(1.0, 15, 0, True)]
    }
}

# import gym
# P = gym.make('FrozenLake-v0').env.P
P
# take a look at the 64-states frozen lake
import gym
env = gym.make('FrozenLake8x8-v1')
P = env.env.P
P

3

에이전트의 목표: 반환값(보상의 총합)을 최대화할 수 있는 행동의 집합을 찾는 것, 정책이 필요하다.

  • 정책policy: 가능한 모든 상태를 포괄한 전체적인 계획.
  • 확률적 혹은 결정적
  • 정책을 비교하기 위해 시작 상태를 포함한 모든 상태들에 대해 기대 반환값을 계산할 수 있어야 한다.
  • 정책$\pi$를 수행할 때, 상태 s에 대한 가치를 정의할 수 있다.
    • 에이전트가 정책 $\pi$를 따르면서 상태 s에서 시작했을 때, 상태 s의 가치는 반환값의 기대치라고 할 수 있다.
    • 가치함수는 상태 s에서 정책$\pi$를 따르면서 시작했을 때의 반환값에 대한 기대치를 나타낸다. $$v_{\pi} (s) = \mathbb{E}_{\pi} [G_t|S_t = s]$$ $$v_{\pi} (s) = \mathbb{E}_{\pi}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{+3} + \dots |S_t = s]$$ $$v_{\pi} (s) = \sum_a \pi (a|s) \sum_{s',r} p(s',r|s,a)[r + \gamma v_\pi (s')] \forall s \in S$$

행동-가치 함수action-value function = Q 함수 = $Q^{\pi}(s,a)$

  • 상태 s에서 행동 a를 취했을 때, 에이전트가 정책$\pi$를 수행하면서 얻을 수 있는 기대 반환값
  • MDP 없이도 정책을 개선시킬 수 있게 해준다. $$q_{\pi} (s,a) = \mathbb{E}_{\pi} [G_t|S_t = s,A_t = a]$$ $$q_{\pi}(s,a) = \mathbb{E}_{\pi}[R_t + \gamma G_{t+1} | S_t = s, A_t = a]$$ $$q_{\pi}(s,a) = \sum_{s',r} p(s',r|s,a)[r+\gamma v_{\pi} (s')], \forall s \in S, \forall a \in A(s)$$

행동-이점 함수action-advamtage function = 이점함수advantage function = $A$

  • 상태 s에서 행동를 취했을 때의 가치와 정책 $\pi$에서 상태 s에 대한 상태-가치 함수 간의 차이 $$a_{\pi}(s,a) = q_{\pi}(s,a) - v_{\pi}(s)$$

이상적인 정책optimal policy

  • 모든 상태에 대해서 다른 정책들보다 기대 반환값이 같거나 더 크게 얻을 수 있는 정책
    • 벨만 이상성 공식(아래) $$v_{*}(s) = max_{\pi} v_{\pi} (s), \forall_s \in S$$ $$q_{*}(s,a) = max_{\pi} q_{\pi}(s,a), \forall s \in S, \forall a \in A(s)$$ $$v_{*}(s) = max_{a} \sum_{s',r} p(s',r|s,a)[r+\gamma v_{*} (s')]$$ $$q_{*}(s,a) = \sum_{s',r}p(s',r|s,a) [r + \gamma max_{a'} q_{*}(s',a')]$$

반복 정책 평가법iteractive policy evaluation = 정책평가법policy rvaluation

  • 임의의 정책을 평가할 수 있는 알고리즘
  • 상태 영역을 살펴보면서 반복적으로 에측치를 개선하는 방법 사용
  • 정책을 입력으로 받고, 예측문제prediction problem를 풀 수 있는 알고리즘에 대한 가치 함수를 출력으로 내보내는 알고리즘, 이때는 미리 정의한 정책의 가치를 계산..(?) $$v_{k+1}(s) = \sum_a \pi(a|s) \sum_{s', r} p(s',r|s,a) \big[ r+\gamma v_k (s') \big]$$
  • 정책 평가 알고리즘을 충분히 반복하면 정책에 대한 가치함수로 수렴시킬 수 있다.

  • 실제로 적용하는 경우에는 우리가 근사하고자 하는 가치 함수의 변화를 확인하기 위해서 기분보다 작은 임계값을 사용.

    • 이런 경우에는 가치 함수의 변화가 우리가 정한 임계값보다 작을경우 반복을 멈추게 된다.
  • SWF환경에서 항상 왼쪽 행동을 취하는 정책에 이 알고리즘이 어떻게 동작할까? $$v_{k+1} (s) = \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a) \big[ r + \gamma v_k (s') \big] $$

    • $\gamma$는 1이라 가정,
    • 항상 왼쪽으로 가는 정책 사용
    • $k$: 반복적 정책-평가 알고리즘의 수행횟수 $$ v^{\pi}_{1}(5) = p(s'=4|s=5, a=\text{왼쪽}) * [R(5,\text{왼쪽},4) + v^{\pi}_{0}(4)] +$$ $$p(s'=5|s=5, a=\text{왼쪽}) * [R(5,\text{왼쪽},5) + v^{\pi}_{0}(5)] + $$ $$p(s'=6|s=5, a=\text{왼쪽}) * [R(5,\text{왼쪽},6) + v^{\pi}_{0}(6)]$$ $$c^{\pi}_{1} (5) = 0.50 * (0+0) + 0.33 * (0+0) + 0.166 * (1+0) = 0.166 \dots \text{ 1번 정책 평가법을 사용했을 떄 상태에 대한 가치를 나타냄}$$

$\rightarrow$ Bootstraping 붓스트랩 방법: 예측치를 통해서 새로운 예측치를 계산하는 방법

# 정책(pi) 평가 알고리즘
def policy_evaluation(pi,P, gamma = 1.0, theta = 1e-10):
    prev_V = np.zeros(len(P),dtype = np.float64)
    while True:
        V = np.aeros(len(P),dtype = float64)
        for s in range(len(P)):
            for prob, next_state, reward, done in P[s][pi(s)]:
            V[s] +- prob * (reward + gamma * prev_V[next_state] * (nor done))
        if np.max(np.abs(prev_V - V)) < theta:
            break
        prev_V = V.copy()
    return V

Note: 정책-개선 알고리즘이 동작하는 방법, 상태-가치 함수와 MDP를 사용해서 행동-가치 함수를 계산하고, 원래 정책의 행동-가치 함수에 대한 탐용 정책을 반환

정책개선 공식$$\pi ' (s) argmax_a \sum_{s',r} p(s',r|s,a) \big[ r + \gamma v_{\pi} (s') \big]$$

# 정책 개선(new_pi) 알고리즘
def policy_improvement(V,P, gamma+1.0):
    Q = np.zeros((len{P}, len(P[0])), dtype = np.float64)
    for s in range(len(P)):
        for a in rnage(len(P[s])):
            for prob, next_state, reward, done in P[s][a]: # 여기서 done의 의미는 다음 상태가 종료 상태인지의 여부를 나타냄
                A[s][a] += prob * (reward + gamma * V[next_state] * nor done)
    new_pi = lambda s: {s: a for s, a in enumerate(np.argmax(np.argmax(Q, axis=1)))}[s]
    return new_pi

잃반화된 정책 순환generalized policy iteration, GPI - 정책 순환, 가치 순환

  • 예측된 가치 함수를 사용해서 정책을 개선시키고, 예측된 가치 함수도 현대 정책의 실제 가치 함수를 바탕으로 개선시키는 강화학습의 일반적인 아이디어

정책 순환policy iteration

# 정책 순환 알고리즘
def policy _iteration (P, gamma = 1.0, theta = 1e-10):
    random_actions = np.random.choice(tuple(P[0].keys()),len(P))
    pi = lambda s: {s:a for s, a in enumerate(random_actions)}[s] # 임의 행동집합 만들고 행동에 대한 상태 매핑
    while True:
        old_pi = {s: pi(s) for s in range(len(P))} # 이전 정책에 대한 복사본 만들기
        V = policy_evaluation(pi, P, gamma, theta)
        pi = policy_improvement(V, P, gamma)
        if old_pi = {s:pi(s) for s in range(len(P))}: # 새로운 정책이 달라진 점이 있나? 있으면 앞의 과정 반복적 시행
            break
    return V, pi # 없다면 루프 중단시키고 이상적인 정책과 이상적인 상태-가치 함수 반환

가치 순환value iteration, VI

  • 단일 반복 이후에 부분적인 정책 평가를 하더라도, 정책 평가시 한번 상태-영역을 훑은 이후에 대한 예측된 Q-함수에 탐용 정책을 취하면, 초기의 정책을 개선시킬 수 있다.

가치 순환 공식 $$v_{k+1} (s) = max_a \sum_{s',r} p(s',r|s,a) \big[ r + \gamma v_k (s') \big]$$

# 가치 순환 알고리즘
def value_iteration(P, gamma = 1.0, theta = 1e-10): # tehta는 수렴에 대한 임계값
    V = np.zeros(len(P),dtype = np.float64)
    while True:
        Q = np.zeros((len(P), len(P[0])), dtype = np.float64) # Q 함수가 0이어야 예측치가 정확해진다.
        for s in range(len(P)):
            for a in range(len(P[s])):
                for prob, next_state, reward, done in P[s][a]:
                    Q[s][a] += prob * (reward + gamma * V[next_state] * (not done)) # 행동-가치 함수 계산
        if np.max(np.abs(V - np.max(Q, axis = 1))) < theta: # 상태-가치 함수가 변하지 않으면 이상적인 V함수를 찾은 것이고, 루프가 멈춤
            break
        V = np.max(Q, axis=1) # 개선과 평가 단계의 혼합
    pi = lambda s: {s:a for s, a in enumerate(np.argmax(Q, axis=1))}[s]

4

멀티 암드 밴딧Multi-armed bandit, MAB

  • 상태 영역과 이에 따른 호라이즌이 1인 독특한 강화학습 문제
  • 여러 개의 선택지 중 하나를 선택하는 환경 $$G_0 = 1* 0 + 0.99 * 0 0.9801 * 0 + 0.9702 * 0 + 0.9605 * 0.9509 * 1$$ $$q(a) = \mathbb{E} \big[ R_t | A_t = a \big]$$
  • 행동 A에 대한 Q 함수는 A 가 샘플링 되었을 때의 기대 보상치를 나타낸다. $$v_* = q(a_*) = max_{a \in A} q(a)$$ $$a_* = argmax_{a \in A} q(a)$$ $$q(a_*) = v_*$$

전체 후회값total regret

  • 전체 에피소드를 통해서 얻은 보상의 총합과 전체 보상치 간의 오차를 줄이면서 에피소드 당 기대 보상치를 최대화하는 것
  • 에피소드별로 이상적인 행동을 취했을 때의 실제 기대 보상치와 현재 정책이 선택한 행동을 취했을 때의 기대 보상치 간의 차이를 존부 더한다.
  • 낮을수록 더 좋은 성능 $$T = \sum^{E}_{e = 1} \mathbb{E} \big[ v_* - q_* (A_e) \big]$$

MAB 환경을 풀기 위한 방법들

  1. 임의 탐색 전략random exploration strategy
    • 대부분 탐욕적으로 행동을 취하다가 입실론이라는 임계값의 확률로 행동을 임의로 선택
  2. 낙관적인 탐색 전략optimistic exploration strategy
    • 의사 결정 문제에서 불확실성을 수치적으로 표현하고, 높은 불확실성 상에서도 상태에 대한 선호도를 높이는 조금 더 체계적인 방법
  3. 정보 상태 영역 탐색 전략information state-space exploration strategy
    • 환경의 일부로써 에이전트의 정보 상태를 모델링, 상태 영역의 일부로 불확실성을 해석
      • 환경의 상태가 탐색되지 않은 미지의 경우와 이미 탐색된 경우일 때 다르게 보일 수 있다는 것을 의미
    • 상태 영역을 늘림으로써 복잡성이 증가하는 단점 존재

그리디 전략greedy strategy = 순수 착취 전략pure exploitation strategy

  • 탐욕적으로 행동을 취하는 전략은 항상 가장 높은 추정 가치를 얻는 행동을 취한다.
# 순수 착취 전략
def pure_exploitation(enc, n_episodes=5000):
    Q = np.zeros((env.action_space.n),dtype=np.float64)
    N = np.zeros((env.action_space.n), dtype=np.int)
    Qe = np.empty((n_episodes, env.action_space.n),dtype=np.float64)
    returns = np.empty(n_episodes, dtype=np.float64)
    actions = np.empty(n_episodes, dtype=np.int)
    name = 'Pure exploitation'
    for e in tqdm(range(n_episodes), # 메인 루프로 들어가면서 환경과 상호작용이 일어나는 구간
                  desc = 'Episodes for: ' + name,
                  leave=False):
        action = np.argmax(Q) # Q 값을 최대화할 수 있는 행동 선택
        _, reward, _, _ = env.step(action) # 환경에 해당 행동 적용 후 새로운 보상
        B[action] += 1
        Q[action] = Q[action] + (reward - Q[action])/N[action]
        Qe[e] = Q
        returns[e] = reward
        actions[e] = action
    return name, returns, Qe, actions

임의 전략random strategy = 순수 탐색 전략 pure exploration strategy

  • 착취하지 않고 탐색만 하는 전략,
  • 에이전트의 유일한 목표는 정보를 얻는 것
  • 착취없이 행동을 결정하는 간단한 방식
# 순수 탄색 전략
def pure_exploration(env, n_episodes=5000):
    Q = np.zeros((env.action_space.n),dtype=np.float64)
    N = np.zeros((env.action_space.n), dtype=np.int)
    Qe = np.empty((n_episodes, env.action_space.n),dtype=np.float64)
    returns = np.empty(n_episodes, dtype=np.float64)
    actions = np.empty(n_episodes, dtype=np.int)
    name = 'Pure exploration'
    for e in tqdm(range(n_episodes),
                  desc = 'Episodes for: ' + name,
                  leave=False):
        action=np.random.rsndit(len(Q))
        _, reward, _, _ = env.step(action) # 환경에 해당 행동 적용 후 새로운 보상
        B[action] += 1
        Q[action] = Q[action] + (reward - Q[action])/N[action]
        Qe[e] = Q
        returns[e] = reward
        actions[e] = action
    return name, returns, Qe, actions

착취는 목표이며, 탐색은 이 목표를 달성하기 위한 정보를 제공한다.

입실론 그리디 전략과 입실론 그리디 감가전략이 가장 많이 쓰이는 탐색 전략, 잘 동작하면서도 내부 구조가 단순하다는 이유로 선호받는다.

입실론-그리디 전략 epsilon-greedy strategy

  • 행동을 임의로 선택,
def epsilon_greedy(env,epsilon=0.01, n_episodes=5000):
    Q = np.zeros((env.action_space.n),dtype=np.float64)
    N = np.zeros((env.action_space.n), dtype=np.int)
    Qe = np.empty((n_episodes, env.action_space.n),dtype=np.float64)
    returns = np.empty(n_episodes, dtype=np.float64)
    actions = np.empty(n_episodes, dtype=np.int)
    name = 'Epsilon-Greedy {}'.format(epsilon)
    for e in tqdm(range(n_episodes),
                  desc='Episodes for: ' + name,
                  leave=False):
        if np.random.uniform() >epsilon: # 우선 임의로 숫자를 선택하고 이 값을 하이퍼파라미터인 epsilon과 비교
            action = np.argmax(Q)
        else:
            action = np.random.randit(len(Q))
            _, reward, _, _ = env.step(action) # 환경에 해당 행동 적용 후 새로운 보상
            B[action] += 1
            Q[action] = Q[action] + (reward - Q[action])/N[action]
            Qe[e] = Q
            returns[e] = reward
            actions[e] = action
    return name, returns, Qe, actions

입실론-그리디 감가 전략 decaying epsilon-greedy strategy

  • 처음에는 입실론을 1보다 작거나 같은 매우 큰 값으로 시작하고, 매 타임 스텝마다 그 값을 감가시키는 것
    • 선형적으로 감가
    • 기하급수적으로 감가

낙관적 초기화 전략optimistic initialization = 불확실성에 맞닿은 낙관성optimosm in the face of uncertainty

  • Q함수를 낙관적인 값인 높은 값으로 초기화함으로써 탐색되지 않은 행동에 대한 탐색을 할 수 있게 도와줘서
  • 에이전트는 환경과 상호작용 하면서 추정치는 낮은 값으로 수렴하기 시작하고
  • 정확해진 추정치는 에이전트가 실제로 높은 보상을 받을 수 있는 행동을 찾고 수렴할 수 있게 해준다.

소프트맥스 전략 softmax strategy

  • 행동-가치 함수에 기반한 확률 분포로부터 행동을 샘플링하는데, 이 때 행동을 선택하는 확률은 행동-가치 추정에 비례하도록 한다.
  • Q 함수에 대한 선호도를 매기고, 이 선호도를 기반한 확률 분포에서 행동을 샘플링하면 된다.
  • Q값의 추정치 차이는 높은 추정치를 가지는 행동은 자주 선택하고, 낮은 추정치를 가지는 행동을 덜 선택하는 경향을 만든다.

$$\pi(a) = \frac{exp\big( \frac{Q(a)}{\tau} \big) }{ \sum^{B}_{b=0} exp \big( \frac{Q(b)}{\tau} \big) }$$

  • $\tau$는 온도 계수,
  • $Q$값을 $\tau$로 나눠즈면 행동을 선택하는 선호도가 계산된다.

신뢰 상한 전략upper confidence bound. UCB

  • 낙관적 초기화 원칙은 그대로 유지하되, 불확실성을 추정하는 값을 계산하는데 통계적인 기법을 사용하고, 이를 탐색할 떄 일종의 보너스로 사용하늗 것

$$A_e = argmax_a \big[ Q_e(a) + c\sqrt{\frac{\ln e}{N_e(a)}} \big]$$

톰슨 샘플링 전략 thormpson sampling

  • 탐색과 착위 사이에서 균형을 잡는데, 베이지안 기법을 사용한 샘플링 기반 확류탐색 전략
  • 책의 예시에서는 Q 값을 하나의 가우시안 분포로 고려하여 구현한다.
    • 평균을 기준으로 대칭을 이루고, 가르치는 목적에 적합할만큼 간단하기 때문
    • 다른 분포도 사용될 수 있다.
    • 가우시안 분포를 사용하는 이유
      • 가우시안 평균이 Q값의 추정치이고, 가우시안 표준편차는 추정치에 대한 불확실성을 나타내는데 이 값은 매 에피소드마다 업데이트 된다.
  • 하지만 베타 분포를 더 많이 쓰이는 것처럼 보인다.

5

보상reward

  • 에이전트가 얻을 수 있는 단일 시점에서의 보상 신호

반환값return

  • 감가된 보상의 총합, 어떠한 상태를 통해서 계산할 수 있고, 보통은 에피소드가 끝날 때까지 계속 계산된다.

가치 함수value function

  • 반환값에 대한 기대치, 에이전트는 총 감가된 보상의 총합에 대한 기대치를 최대화하려고 할 것이고, 결국 이 기대치가 가치 함수가 된다.

랜덤 워크 환경; 어느쪽으로 가든 확률이 같은 환경을 가정

import warnings ; warnings.filterwarnings('ignore')

import gym, gym_walk, gym_aima
import numpy as np
from pprint import pprint
from tqdm import tqdm_notebook as tqdm

from itertools import cycle, count

import random
import matplotlib
import matplotlib.pyplot as plt
import matplotlib.pylab as pylab
SEEDS = (12, 34, 56, 78, 90)

%matplotlib inline
---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
/tmp/ipykernel_368341/1071994700.py in <module>
      1 import warnings ; warnings.filterwarnings('ignore')
      2 
----> 3 import gym, gym_walk, gym_aima
      4 import numpy as np
      5 from pprint import pprint

ModuleNotFoundError: No module named 'gym'

몬테카를로 예측Monte Carlo prediction, MC;

  • 몬테카를로 방법(Monte Carlo method) (또는 몬테카를로 실험)은 반복된 무작위 추출(repeated random sampling)을 이용하여 함수의 값을 수리적으로 근사하는 알고리즘을 부르는 용어이다.
  1. 에이전트는 정책 $\pi$를 이용해서 종료 상태 $\S_T$에 도달할 때까지 환경과 상호작용을 수행한다.
    • 여기서 수집된 상태 $S_t$, 행동 $A_t$ 다음에 얻을 수 있는 보상 $R_{t+l}$, 다음의 상태 $S_{t+l}$를 경험 투플experience tuple이라 부르고, 이 경험의 집합을 경로trajectory라고 한다.
  2. 모은 경로를 이용해서 방문하는 모든 상태 $S_t$에 관한 반화값$G_{t:T}$를 계산한다.
    • $t:T$의 의미는 t에서 t까지 보상을 더하고 감가한다는 말
  3. 경로 생성 후 모든 상태 $S_t$에 대한 반환값을 계산했다면, 각 에피소드 $e$와 이 에피소드가 끝나는 타임 스템 T에 대한 상태-가치 함수 $v_{\pi}(s)$를 각 상태 s에서 얻은 반환값에 대한 평균을 구함으로써 계산
    • 즉, 평균을 통해서 기대치를 추정하는 것 $$V_T (S_t) = V_{T-1}(S_t) + \alpha_t \big[ G_{t:T} - V_{T-1} (S_t) \big]$$

TD목표 TD Target

  • 단일 스텝에서의 보상$R_{t+l}$을 사용한다면, 다음 상태$S_{t+l}$를 관찰했을때 상태-가치 함수에 대한 추정치$V(S_{t+l}$를 다음 스템에서의 반환값$G_{t+l:T}$에 대한 추정치로 사용할 수 있다. $$V_{t+1}(S_t) = V_t(S_t) + \alpha_t \big[ R_{t+1} + \gamma V_t (S_{t+1}) - V_t (S_t) \big]$$

6

$52.$ 어느 전자제품의 수명이 확률변수 $X$ ~ $EXP(100)$라고 할 때,

(1) $P(X>30)$을 구하라.

(2) $P(X>110)$을 구하라.

(3) $P(X>110|X>80)$를 구하고 (1)의 결과와 비교하라.