!! 여기서의 Control은
어떻게 optimal policy를 근사하는데 사용될 수 있는지 이다

Monte Carlo의 수렴성

배경

몬테카를로 방법은 모델을 활용할 수 없기에 (model-free)
state value 대신
action value (state-action value)를 추정하는 것이 유용함

state-action 쌍을 마주치는 것은
곧, 하나의 에피소드에서 state s를 마주치고
그 state s에서 action a가 선택되는 것

문제

여기서 유일한 문제는
많은 state-action 쌍에 대해 접촉이 발생하지 않을 수도 있다는 점.
policy 𝝅의 결과대로만 action을 선택하면 그에 대한 이득만 확인하게 되어
다른 action에 대한 경험을 얻지 못한다

현재 선호하는 action뿐만 아니라,
각 state로부터 선택할 수 있는 모든 action의 가치를 추정할 필요가 있다

수렴을 위한 조건

그러므로
MC 방법의 수렴성,
즉, 모든 state-action 쌍을 무한 번 마주치는 것을
쉽게 보장받기 위해서는
있을 법하지 않은 두 가지 가정을 해야한다

• episode가 시작 탐험 exploring starts을 갖는다
  • == episode 개수가 무한으로 갈 때 모든 state-action 쌍을 무한 번 마주치는 것을 보장
  • action value에 대한 policy evalutation은 연속적인 탐험이 보장되어야만 한다
    (maintaining exploration)
  • episode가 하나의 state-action 쌍에서 시작하고,
    그 외 다른 쌍들이 시작 쌍으로 선택될 확률이 0이 아님을 명시하는 것
• policy evalution이 무한 개의 episode에 대해 행해질 수 있다

Monte Carlo Control

있을 법하지 않은 가정이었으니
앞으로 이 가정들을 없애나갈 것이다

Without Infinite Policy evalutation

1. 추정 오차의 크기와 확률이 특정 경계값보다 낮을만큼 수렴되었을 때 중단
   하지만 최소 규모의 문제가 아니라면
   실제 문제에 유용하게 적용하기 위해
   너무 많은 에피소드를 필요로 할 수 있다

2. policy improvement 전에 evaluation을 완료하려는 노력을 포기하기
   매번의 평가 단계에서 value function은
   $q_{\pi}$를 '향해' 움직이지만,
   많은 단계를 거치기 전에
   실제로 가까워질 것이라 기대하지 않는다

Without Exploring start

모든 action이 무한히 선택되도록 보장하는 방법 2가지

• on-policy (활성 정책) : soft 관대한
  • 결정을 내리는데 사용되는 policy를 평가하고 향상시킨다
  • soft (관대한) 편
    • 모든 state와 action에 대해 ${\pi}(a|s) > 0$을 만족하면서
    • 결정론적인 optimal policy에 가깝게 이동한다는 뜻
  • 두 가지 policy를 사용
    • target policy : 학습 대상이자 optimal policy
    • behavior policy : 좀 더 탐험적이고 action 생성을 위한 policy
  • 서로 다른 policy를 사용하기에 분산이 더 크고 수렴 속도가 느리다
  • ex) Monte Calro ES, Epsilon-greedy policy
• off-policy (비활성 정책)
  • 자료를 생성하는데 사용되지 않는 policy를 평가하고 향상시킨다
  • Target policy와 동떨어진 데이터로부터 학습
  • target policy == behavior policy 인 특별한 경우에 off-policy는 on-policy를 포함한다
  • ex) Importance Sampling (중요도 추출법)

epsilon-greedy policy

on-policy 방법의 일종
대부분의 시간동안에는 최대의 action value 추정값을 갖는 action을 선택하지만
입실론 ${\epsilon}$의 확률로 이따금씩 무작위로 action을 선택하는 것을 의미한다

Weight Importance Sampling

Importance Sampling

어떤 분포로부터 얻어진 표본이 주어질 때
그 표본을 이용하여
또 다른 분포에서의 기댓값을 추정하는 방법

target policy와 behavior policy에서 발생하는
state-action의 궤적에 대한 (=$A_t, S_{t+1}, A_{t+1}... S_T$)
상대적 확률을 Importance Sampling ratio (중요도추출비율)이라 한다

이 확률에 따라 가중치를 부여하는 방식으로
off-policy에 importance sampling을 적용하겠다