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목표가 보정된다.
