TD, SARSA, 몬테카를로

MDP 모를 때 value 평가 → 몬테카를로, TD

몬테카를로

• MDP를 모른다 ⇒ 보상 함수 $r^a_s$와 전이 확률 $P^a_{ss’}$를 모른다. 단, 그 값을 모르는 것일 뿐 실제 고정된 $r^a_s, P^a_{ss'}$는 존재한다.
  • MDP = MRP + Agent. action변수가 추가됨. → MDP를 모른다. action과 관련된 정보를 모른다. 에이전트가 어떤 행동을 취할지, 그 행동을 취했을 때 어떤지에 대해 전혀 모른다.
  • 강화학습은 리턴을 최대화하는 것을 목표로 한다.
  • 리턴($\mathrm{G_t}$): t시점부터 미래에 받을 감쇠된 보상의 합. $\mathrm{G_t = R_{t+1}+\gamma R_{t+2} + \gamma^2R_{t+3}+\cdots}$
  • 보상함수($\mathrm{R }$): 상태 s에 도달했을 때 받게 되는 보상 값 $\mathrm{R_s}=\mathbb{E}[\mathrm{R_t|S_t=s}]$
    • MDP에서의 보상함수 ⇒ action 변수가 추가되기 때문에 $\mathrm{R^a_s}$으로 표기한다. 이때는 상태 s에서 액션 a를 선택했을때 받게되는 보상을 뜻한다. $\mathrm{R^a_s}=\mathbb{E}[\mathrm{R_{t+1}|S_t=s,A_t=a}]$
• ⇒ 특정 상태에서 어떤 행동을 했을 때의 보상 값과 특정 상태에서 그 다음 상태까지 도달할 확률을 모른다.
  • $r^a_s$를 안다는 것은 상태 s에서 액션 a를 해보기도 전에 얼마의 보상을 받을지 그 기댓값을 안다는 뜻이다.
  • ⇒ 상태 s에서 액션 a를 행하면 무조건 알수 있는 값인건가?
  • ⇒ 그렇기 때문에 몬테카를로 방법을 사용하여 일단 액션을 취해봐서 알게 되는건가?
• 액션을 취하면 어떤 값을 알 수 있게 되는가?
  • 고정된 $r^a_s, P^a_{ss'}$는 존재한다. 확률 분포 형태로 존재한다고 하자. 실제로 연속적인 액션을 취해보면 정해진 $P^a_{ss'}$에 의해 어떤 상태로 도달하게 되어 특정 에피소드가 만들어지고, 정해진 $r^a_s$에 따라 특정 보상 값들을 얻게된다. 이를 여러번 반복하면 실제 정해져있는 $r^a_s, P^a_{ss'}$에 가까운 함수를 알 수 있게 된다.
  • 몬테카를로는 특정 그림에 검은 칠을 한 다음에, 검은 칠을 하나씩 긁어서 해당 그림을 알게 되는 것과 같다.
• 에피소드가 끝날때마다 value값을 업데이트 한다.

TD

MC(MonteCarlo)의 단점

• value값을 업데이트 하기 위해서는 에피소드가 끝날때까지 기다려야한다.
  • 에피소드가 끝나야 리턴 값을 알 수 있기 때문이다.
  • 유한 개의 에피소드에서만 MC를 사용할 수 있다.

TD 아이디어

• 미래의 추측으로 과거의 추측을 업데이트하자.
• 한 step이 지나고(즉, 조금이라도 시간이 흐르면) 좀 더 정확한 추측을 할 수 있게 된다. → 이를 업데이트에 활용하자.
• ⇒ 즉, TD는 몬테카를로와 마찬가지로 직접 행해보고 보상함수와 전이확률을 알자, 인데, 대신 다 해보고 보상함수와 전이확률을 그려내보려고 하지말고 조금씩 해보면서 그림을 그려보자라는 아이디어이다.

MC의 이론적 근거 : $v_\pi(s_t)=\mathbb{E}[\mathrm{G_t}]$

→ 벨만 방정식 → $v_\pi(s_t)=\mathbb{E}[\mathrm{G_t}]=\mathbb{E}[r_{t+1}+\gamma v_\pi(s_{t+1})]$

 

TD와 SARSA의 차이점은 무엇인가?

• TD는 상태 가치함수를 계산하기 위한 방법이다. 조금씩 행해보면서 상태 가치함수를 추정하는 방법이다.
• SARSA는 TD기반의 정책을 찾는 방법이다. 정책은 액션의 sequence(일련의 과정?집합?)다. 최적의 정책을 찾으려면 각 상태에서의 액션에 대한 보상의 합이 최대여야 한다. 따라서 최적의 정책을 찾기 위해서는 액션 가치함수를 알아야 한다. 액션 가치함수를 알기 위해서는 상태 가치 함수를 알아야 하고, 상태 가치 함수를 알기 위해서는 TD를 이용한다.