[CS234] Lecture 13: Fast Learning III 정리 (1)

역시 지난 시간에 빠르게 훑고 지나갔던

MDP에서 Fast Learning을 적용하는 방법에 대해 설명하는 것으로

13강이 시작되었다.

 

PAC는 Probably Approximately Correct의 줄임말로,

Bandit 문제에 Bayesian Regret 등을 적용한 것처럼

MDP에 fast learning을 적용하는 방법의 이름인 것 같다.

 

좀 더 검색을 해보니, 기본적으로는 

머신러닝 알고리즘의 성능을 설명하기 위한 방법이라고 한다.

근데 fast learning이랑은 무슨 관계가 있는 거지?

 

Model Based Interval Estimation[MBIE]은 PAC의 일종이다.

모델을 기반으로 interval을 추정한다는 이름이 너무 열받는다.

어떻게 이렇게 하나도 감이 안오게 이름을 지을 수가 있지?

Interval이 무엇인지, Model은 무엇인지,

제목에서 유추할 수 있는 것이 하나도 없다.

 

다시금 PAC이 무엇인지 확인해보자.

그러면 MBIE가 도대체 무엇을 의미하는지 대충 감이 올 수도 있다.

강화학습에서 PAC란, 일정 과정(N steps) 이후에는

해당 알고리즘이 (1 - $\delta$)의 확률 이상으로 

V - $\epsilon$ 보다 큰 Q값을 가질 수 있는 행동을 취하는 것을

보장하는 것이다.

 

여기서 중요한 것은 V보다 큰 Q이다. 

어쨌든 현재 상태보다 나아지게 하는 행동을 취할 수 있도록 한다는 것이다.

 

교수님의 설명은 약간 감동적이기까지 하다.

그간 배웠던 Regret이 한 시점에서 출발해서

최종 지점까지의 차이가 얼마나 벌어지느냐에 대한 내용이었다면

PAC은 순간 순간에서 선택을 비교할 수 있다는 것이다.

 

사소한 대회가 있다고 가정하자. 그림대회 같은 거.

거기서 우승한 이력이 큰 도움이 되어 Harvard Law School에 입학해서는

법관으로 삶을 진행시켜나갈 수도 있다.

그림대회에서 우승하지 못해서 Harvard Law에 입학하지 못하고,

삶의 방향이 전혀 다른 쪽으로 이어질 수 있다.

삶의 마지막 순간에 "그 때 그림대회에서 우승했더라면..." 하는 식으로 후회하는 것

그것이 바로 Regret 알고리즘이다.

 

반면에 PAC은, 그림대회에서 우승하지 못했을 때

다음 그림대회에 참여할 수 있고 그렇지 않을 수도 있다.

그 차이를 생각하면서 행동을 선택하는 것이다.

눈물이 핑 도네.

 

위와 같은 조건들은 PAC이 될 수 있는 가능성을 가지고 있다.

다시 말해, PAC의 충분 조건이다.

1) Optimism

알고리즘을 통해 산출한 행동과, 그것을 포함해 계산한 Q가

최적의 Q값에서 $\epsilon$을 뺀 것보다 항상 커야 한다.

다시 말하자면, 늘 최적의 행동을 산출할 수 있어야 한다는 뜻이다.

어떻게 보면 굳이 언급할 필요도 없이 당연한 말 같다.

"매사 최선을 다하라" 같은 잔소리로 여겨질 수 있을 정도이다.

 

2) Accuracy

알고리즘으로 계산한 V값이 어떤 특정한 MDP에서 계산한 V 값과

상당히 유사해야 한다.

어떤 MDP인지에 대해서는 나중에 알려준다고 한다.

Accuracy라는 이름이 붙은 것을 생각해보면

V를 산출하는 방식에 관한 문제인 것 같은데, 아직 감이 오지 않는다.

 

3) Bounded Learning Complexity

$\epsilon, \delta$에 따라서 Q를 학습할 수 있는 횟수와

미지의 (s, a) pair를 선택할 수 있는 횟수가 제한되어야 한다.

끝없는 반복학습을 방지하기 위한 장치인가? 무슨 의미일까?

 

어쨌든 위 세 조건을 만족한다면 PAC을 만족시킬 준비가 되어 있는 셈이다.

이제 다시 MBIE-EB를 살펴보자.

MBIE-EB에서 Q는 위와 같이 변한다.

Q-Learning에서 배웠던 모습과는 상당히 변한 것을 알 수 있다.

Reward에는 보너스가 붙었고, 오른쪽 항은 아예 알아보기도 힘들다.

T는 상태 전환 확률 행렬이고, T에 곱해지는 것은 최적의 행동 값인데

T가 있다는 것은 모델이 주어졌을 때 사용가능하다는 뜻일까?

아리송하군. 눈물이 쏙 들어가네.

 

3번 조건과 같이, (s, a)에 방문할 수 있는 횟수도 제한이 되어 있다.

1~2번 조건도 녹아져 있을 테다.