강화학습

SARSA ( State-Action-Reward-State-Action ) 및 벨만 방정식과의 관계

정지홍 2024. 12. 14. 09:19

Q함수에서 벨만 방정식의 백업 다이어그램
SARSA의 백업 다이어그램

SARSA와 벨만 방정식간의 관계

  • 환경의 상태전이 확률에 따른 모든 상태 전이를 고려함
  • 에이전트의 정책pi에 따른 다음 단계의 모든 행동을 고려함.
  • 위의 백업 다이어그램을 보면 알수있듯이, SARSA는 벨만 방정식의 샘플링 버전으로 볼 수있다.
    • 샘플링 버전: 모든 전이를 사용하는 것이 아닌 '샘플링한 데이터'를 사용함을 의미

 

 

SARSA

  • 대표적인 on-policy TD학습 알고리즘이다.( on-policy는 '대상 정책' == '행동 정책'이다. 서로다른 경우는 off policy다.)
    • agent는 환경과 상호작용하면서, 최적의 정책을 학습한다.
    • 학습을 위한 정보는 이름에서도 알수있다...!
      • State , Action , Reward , Next State , Next Action
  • Q러닝과 유사하게 Q-값을 업데이트 하면서 정책을 학습한다. 하지만 SARSA는 현재 정책을 따르는 행동을 학습한다.
    • 이를 on-policy 학습 방식이라고 함.
  • SARSA는 agent가 현재 정책에 따라서 action을 선택한다.
    • Q-러닝은 agent가 최적의 행동을 기준으로 학습.
  • SARSA는 policy를 평가하고 업데이트 하면서, 해당 정책을 유지한다.
    • Q-러닝은 학습 중에도 정책을 변경하거나 다른 방식의 행동을 선택할 수 있다.
    • ==>결과적으로는 SARSA는 agent가 실제로 사용하는 정책에 더 잘 적응하나, Q러닝은 보다 탐색적이며 이론적으로 최적 정책을 찾는데 유리함.
  • 장점
    • 안전성: 현재의 정책을 학습하니 정책이 수렴할 가능성이 높다. 
    • 현실적인 학습: 실제 행동에 기반한 학습이니, agent가 실질적으로 사용하는 policy에 적합한 학습을 수행함.
  • 단점
    • 탐색 부족: 현재의 정책을 따르니, 최적의 정책을 찾는데 좀 더 시간이 필요할 수 있다.
    • 수렴속도: Q러닝에 비해서 느릴수 있다.
  • 활용사례
    • 특정 게임에서 agent의 행동을 안전하게 학습
    • 로봇의 안전적이며 반복 가능한 동작을 학습
    • 자율주행에서 위험한 행동을 피하면서 정책을 학습 
  • on-policy에서 agent는 하나의 정책만을 가지고 있다.
    즉, "실제로 선택하게 되는 정책(행동 정책)"과 "평가,개선할 정책(대상 정책)"이 일치한다.

 

행동 가치 함수를 구하는 식. 이는 환경모델 필요x. [식1]
이것은 TD법의 갱신식이다. [식2]
Q함수를 대상으로 한 TD법의 갱신식이다. [식3]
e-greedy policy에 따라서 policy를 개선하는 식. 식[4]

  • SARSA에서 필요한것은 V(s)가 아니라 행동가치 함수인 Q함수( Q(s,a) )가 필요하다.
  • [식3]은 [식2]에서 상태가치 함수를 행동가치함수( Q함수 )로 바꾼것 이다.
  • [식3]은 state와 action을 하나의 data묶음으로 생각합니다.
    • t시점에서는 S t 와 A t를 하나의 data묶음으로....
      t+1시점에서는 S (t+1) 과 A (t+1)을 하나의 묶음으로 생각합니다.
  • 식[3]에서는 t시점의 data묶음과 reward, t+1시점의 data묶음을 얻으면 Q함수를 갱신합니다.
    그리고 갱신이 끝나면 개선을 합니다.
    • 갱신은 Q함수를 업데이트하고, 개선은 정책을 업데이트하는거임. ( 식[4] 참고 )
      • epsilon의 확률로 모험을..... 그 외에는 탐욕적인 행동을 취한다.
# 탐욕적으로 정책을 조정하게 하는 함수
# 즉, 행동가치함수인 Q함수의 값이 가장 큰 챌동만 하게 확률 분포를 만들어 준다.
def greedy_probabilities( Q , state , epsilon=0 , action_size=4 ):
    qs = [ Q [ (state , action) ] for action in range ( action_size ) ] # 현재 state에서 가능한 모든 action의 Q값을 뽑아냄.
    max_action = np.argmax( qs ) # Q깂이 가장 큰 값을 꺼내줍니다.
    base_probabilities = epsilon / action_size # 모든 행동에 대해서 기본 확률을 할당합니다.  여기서는 0.025이다.
    action_probabilities = { action: base_probabilities for action in range ( action_size ) } # 기본확률.. {0: 0.025, 1: 0.025, 2: 0.025, 3: 0.025}
    action_probabilities[ max_action ] += ( 1 - epsilon ) # {0: 0.025, 1: 0.025, 2: 0.025, 3: 0.925}과 같은 형식으로 출력됨.
    return action_probabilities
from collections import defaultdict , deque
import numpy as np

class SarsaAgent:
    def __init__( self ):
        self.gamma = 0.9 # 할인률
        self.alpha = 0.8 # 학습률
        self.epsilon = 0.1 # 탐험 확률
        self.action_size = 4 # 행동의 갯수. 상하좌우
        random_actions = { 0:0.25 , 1:0.25 , 2:0.25 , 3:0.25 } # 초기정책에 대한 설정
        self.pi = defaultdict( lambda: random_actions ) # 정책함수
        self.Q = defaultdict( lambda: 0 ) # 행동 가치 함수
        self.memory = deque( maxlen=2 ) # (S -> A -> R -> S -> A)를 위해서 deque를 사용. 선입선출이니 오래된 원소를 삭제하는 형식으로 최근 경험 데이터만 보관한다.
        
    def get_action( self , state ):
        action_probabilities = self.pi[ state ]
        actions = list( action_probabilities.keys() )
        probabilities = list( action_probabilities.values() )
        return np.random.choice( actions , p=probabilities )
        
    def reset(self):
        self.memory.clear()

    def update( self , state , action , reward , done ):
        self.memory.append( ( state , action , reward , done ) ) # 현재의 경험을 meomry에 추가
        if len( self.memory ) < 2: # memory가 출분하지 않으면 업데이트를 하지 않음.
            return
        state , action , reward , done = self.memory[0] # 메모리에서 현재의 data묶음을 가져옴
        next_state , next_action , _ , _ = self.memory[1] # 메모리에서 다음 스텝의 data묶음을 가져옴
        next_q = 0 if done else self.Q[ next_state , next_action ] # 다음 상태에서 Q값을 계산하기 위해서 Q값을 가져옴
        target = reward + self.gamma * next_q # next_q는 defaultdict타입이니 value값에만 gamma가 곱해짐. key의 형태는 (state ,actiom)형태이며, 해당값에 대한 value는 Q함수 값이다.
        self.Q[ state , action ] += ( target - self.Q[ state , action ] ) * self.alpha # 갱신을 합니다...
        self.pi[ state ] = greedy_probabilities( self.Q , state , self.epsilon ) # 그리고 개선을 합니다.
env = GridWorld()
agent = SarsaAgent()
episodes = 10000

for episode in range( episodes ):
    state = env.reset()
    agent.reset()
    while True:
        action = agent.get_action( state ) # 랜덤하게 어떠한 action을 할지 가져옵니다.
        next_state , reward , done = env.step( action ) # 전달받은 action을 수행합니다.
        agent.update( state , action , reward , done ) # 업데이트 합니다. SARSA알고리즘으로 Q값과 정책을 업데이트
        if done:
            agent.update( next_state , None , None , None )
            break
        state = next_state

 

 

off-policy에서의 SARSA ( expected SARSA )

  • on-policy와 Q-learning과 유사하지만, 기존의 SARSA와 다르게 학습중인 정책과 행동을 선택하는 정책이 다르다.
    그러니, 학습에 사용하는 행동(정책)이 실제로 선택된 action과 다를 수 있다.
  • 행동 선택 정책 Behavior policy
    • agent가  환경과 상호작용하면서 행동을 선택할 때 사용하는 정책이다.
    • 다양한 action을 시도할 수 있어서 여러 sample data를 수집하는 것이 가능하다.
    • 탐험을 허용하기 위해서 e-greedy policy등을 사용
  • 학습 대상 정책 target policy
    • agent가 학습하려는 최적 정책이다.
    • 보통은 greedy policy다.
  • 주의점
    • 행동 정책과 대상 정챍의 확률분포가 비슷해야 안정적이다.
      그래서 행동정책을 e-greedy policy를 사용하며, 학습 대상 정책을 greedy policy를 사용한다.
    • 두 정책이 서로 다르니 중요도 샘플링을 활용해서 가중치로 이를 보정한다.

 

 

두 정책의 차이로 인한 가중치. [식 5] pi는 대상 정책이며, b는 행동 정책이다.
대상 정책 π를 기반으로 t+1시점의 행동 A t+1를 샘플링(선택)하는 과정을 나타냄
Q함수를 대상으로 한 TD법의 갱신식이다. [식3]
이러한 과정을 통해서, off-policy의 SARSA 갱신식이 유도된다. 그래서 결국 action은 정책 b에 따라서 샘플링되고, 가중치 rho에 의해 TD목표가 보정된다.

class SarsaOffPolicyAgent:
    def __init__( self ):
        self.gamma = 0.9
        self.alpha = 0.8
        self.epsilon = 0.1
        self.action_size = 4
        random_actions = { 0:0.25 , 1:0.25 , 2:0.25 , 3:0.25 }
        self.pi = defaultdict( lambda: random_actions )
        self.b = defaultdict( lambda: random_actions )
        self.Q = defaultdict( lambda: 0 )
        self.memory = deque( maxlen=2 )
        
    def get_action( self , state ):
        action_probabilities = self.b[ state ] # 행동 정책에서 가져옴
        actions = list( action_probabilities.keys() )
        probabilities = list( action_probabilities.values() )
        return np.random.choice( actions , p=probabilities )

    def reset( self ):
        self.memory.clear()

    def update( self , state , action , reward , done ):
        self.memory.append( (state , action , reward , done ) )
        if len(self.memory ) < 2:Q
            return
        state , action , reward , done = self.memory[0]
        next_state , next_action , _ , _ = self.memory[1]

        if done:
            next_q = 0
            rho = 1
        else:
            next_q = self.Q[ next_state , next_action ]
            rho = self.pi[next_state][next_action] / self.b[next_state][next_action]
        target = rho*( reward + self.gamma*next_q )
        self.Q[ state , action ] += ( target - self.Q[ state , action] ) * self.alpha
        self.pi[ state ] = greedy_probabilities( self.Q , state , 0 )
        self.b[ state ] = greedy_probabilities( self.Q , state , self.epsilon )
env = GridWorld()
agent = SarsaOffPolicyAgent()
episodes = 10000

for episode in range( episodes ):
    state = env.reset()
    agent.reset()
    while True:
        action = agent.get_action( state ) # 랜덤하게 어떠한 action을 할지 가져옵니다.
        next_state , reward , done = env.step( action ) # 전달받은 action을 수행합니다.
        agent.update( state , action , reward , done ) # 업데이트 합니다. SARSA알고리즘으로 Q값과 정책을 업데이트
        if done:
            agent.update( next_state , None , None , None )
            break
        state = next_state