Monte Carlo methods

 

Prediction Task and Control Task 

• Prediction Task 

– With policy given, we try to predict the value function or Q function using the policy. 

– Why? because we want to evaluate the policy. 

– What is a good policy? One that gets a good return for the agent. 

– How can we get the return? From the Q function 

– Thus, by predicting a Q function, we predict the (expected) return, and that will evaluate the policy . 

– In prediction task, we don't make any change to the given policy.

 • Control Task 

– We are not given any policy here. We start off with a random policy. 

– Iteratively, we make changes to the policy, hoping to find the optimal policy

우리가 가지고 있는 이슈..

대부분의 환경의 dynamics를 알 수가 없음: model free 한 상황임

(reward, transition probability를 알 수가 없음)

→ 게임에 대해서만 알 수있지, 자율 주행 등과 같은 실제 상황에서는 알 수가 없음

→ 해결책: Monte Carlo methods

Monte Carlo methods

: n만큼의 실험을 통해 기대값을 계산함

→ V, Q값을 실험을 통해 추정함

 

 

대략 3번의 실험을 통해서(3.6이 정답) 3.3을 얻게됨

 

12페이지 파란색 오타 수정임

위의 프로세스를 코드로 보면 아래와 같음

 

 

 

여러번의 실험을 하면

각 path에 대한 행렬값과 결과값을 얻을 수 있음

 

→ [ V(1), V(2), V(3), Reward] = [0, 0, 0, 1]

→ [ V(2), V(3), Reward] = [0, 0, 1]

→ [ V(3), Reward] = [0, 1]

prediction

Types of Monte Carlo Prediction 

• First-visit Monte Carlo 

  – If a state is visited multiple times in an episode, 

     only consider the first visit to that state when calculating the value function. 

First visit일 때 채워야하는 코드

• Every-visit Monte Carlo 

  – If a state is visited multiple times in an episode, consider all visits to the

 

 

강화학습에서 design 해야될 3가지

1. state : A중 11로 쓰는지(True), 1로 쓰는지(False)에 대한 state도 포함
2. action : hit / stand
3. reward : win +1 / draw 0 / loss -1

 

state에 대한 예시 2가지

( 15, 9: 딜러, True )

( A, 4, 9: 딜러 )

아래의 경우에는 같은 state로 볼 수 있음

A case

1. ( 15, 8: 딜러, False )
2. ( 10, 5, 8: 딜러 )

B case

1. ( 15, 8: 딜러, False )
2. ( 8, 7, 8: 딜러 )

취할 action이 달라지면 다른 state,

같은 action을 취하게 되면 같은 state

→ a와 같은 state로 묶게 되면 훨씬 간소화 되는 경우가 많음

500,000만번 계산해서 기대값 구하는 코드

policy를 이미 정해놓았으므로, prediction task라고 할 수 있음

[참고 : every-visit Monte Carlo Prediction 코드]

Arithmetic mean vs. Incremental mean

• Arithmetic mean

• Incremental mean

유도식은 아래와 같음

 

즉, incremental mean을 사용했을 때는 smoothing(가중치 적용)되는 효과가 있음

 

 

 

100, 200, 300, 400, 500일 때

• Arithmetic mean : (100+200+300+400+500)/5 = 300
• Incremental mean: (100+½(200-100), 200+⅓(300-200), ….)

eg) 

alpha가 1/n 일 때는 incremental mean = arithmetic mean

alpha=0.3 일 때, 가중치가 적용된 평균임

v(s) = v(s) + 0.3 R(t) - 0.3V(s)

       = 0.7v(s) + 0.3 R(t)

Monte carlo prediction에서의 Q function

M번의 iteration이 있다고 할 때,

각 t번째의 episode에서

eg) 

state= [0,1,2,6,10,14,15]

action = [2,2,1,1,2,2]

reward = [0,0,0,0,0,1]

일 때 state1에서 2의 action을 취할 때의 reward는 0+0+0+0+1임

control

Monte carlo control에서의 Algorithm

M번의 iteration이 있다고 할 때,

각 t번째의 episode에서

노란색은 위의 prediction에서의 Q function과의 차이점을 나타냄

→ 이게 On-policy임

On-policy vs. Off-policy

On-policy: policy Pi를 계속 improve하는 것에 목적을 둠

• 단점: 더 좋은 policy에 대한 exploration을 하지 않음

Off-policy: policy를 다른 policy로 변화하면서 random하게 가끔씩 엉뚱한 policy를 try 함

• 단점1: risk를 가지고 있음 (의미없는 exploration이 발생할 수 있음)
• 단점2: exploration해서 나온 policy가 현재 내가 가야할 최적의 방향을 제시한다는 보장이 없음                                                 → 해결책: importance sampling
• 장점: 더 좋은 policy를 발견 할 수 있음 (exploration)
• 구현 방법: 동일한 state, action으로 시작하는것이 아니라,                                                                                   random한 state, action에서 시작하게 함으로써 off-policy를 구현할 수 있음 (exploring starts)

Exploring starts

exploring starts의 단점

1. initial state를 random하게 설정하는 것이 불가능할 수 있고
2. 가능하더라도 의미없는 초기 state가 설정될 수 있다.

On-policy monte carlo control 2가지 방법

1. Greedy policy

Q값이 높은 방향으로 움직임

2. Epsilon-greedy policy

Epsilon에 따라 움직임

초기에는 epsilon을 크게 잡아서 더 random하게 움직이게 하다가

점점 작은 epsilon을 잡아서 random성을 줄이는 것

epsilon=0 탐험 안함, epsilon이 1과 가까워질수록 탐험 많이 함

** 1번, 2번을 사용하는 이유: 자꾸 하려던 것만 계속 하는 것을 방지해주기 위해

단, Exploration-exploitation dilemma에 빠질 수 있음

 

On-policy monte carlo control with Epsilon-Greedy policy는 위의 algorithm과 

4번(노란색) 차이만 있음

4번이 코드에서는 아래와 같이 나타남.

random하게 선택한 값이 epsilon(0.5)보다 작으면, random하게 action을 취하는 것이고, 

그것보다 크면 Q값이 가장 높은 액션을 취하는 것임

off-policy에서 사용하는 2가지 policy

1. behavior policy(b)

→ To explore various state-action pairs, 

     the behavior policy b is set to an epsilon-greedy policy

2. target policy (pi)

Off-Policy Monte Carlo Control Algorithm

노란색만 그 위의 차이임

(1, 1, 1, 1)이 나오는데, nA(number of action=4)으로 나눠주면

(0.25, 0.25, 0.25, 0.25)가 return 됨

여기서 분자가 1인 이유는, target policy는 딱 1개만 존재하므로(argmax)

 

따라서, 25%씩  확률로 해서 하나의 action을 고르는 것임

(여기서 behavior policy는 random policy임 → coverage는 좋긴한데, 너무 random함)

(epsilon-greedy를 쓸 수 있음)

 

 

 

 

off-policy의 단점: 한번 try했던 policy가 가장 best임에도 불구하고,

random하게 생성된 policy로 진행이 되어 이전 best policy에 대한 가치를 제대로 반영 하지 못함

→ randomly하게 선택했을 때의 distribution과(behavior policy) 

    목표하는 것의 distribution(target policy)이 일치 하지 못할 때

→ 해결책: importance sampling을 사용하여 해결함