[강화학습] Stochastic Approximation

• 구하고자 하는 것은 아래와 같은 fixed point equation 이다.
  

• 위 식을 아래와 같이 근사한다.
  
• $x_k$는 기존 값
• $s_k$는 simulation으로 새로 수집한 데이터
• $\alpha_k$는 가중치

• $H_{x_k}$와 $s_k$는 상당히 다를 수도 있다.하지만 noise $w_k$가 특정 조건을 만족 할 시, fixed point 계산에는 큰 영향이 없게 된다.

Application : Bellman Equation

• 구하고자 하는 값은 이와 같다.
  

• single sample만 쓰도록 근사한다.(Robbins-Monro algorithm)
  
  

• Stepsize와 stepdirection 형태로 나타낼 수 있다.
  

Contraction 수렴 조건

아래 두 조건을 만족하고, H가 contraction mapping이면, $x_k$는 fixed point $x^*$로 수렴한다.

• Stepsize 조건
  

  • 이유
    

• noise 조건
  

monotonicity 수렴조건