Q-Learning , Q-Learning과 벨만 최적 관계식 간의 관계

 

벨만 방정식(위) ❘ 벨만 최적 방정식 (아래)

Q함수에서 벨만 방정식의 백업 다이어그램 (왼쪽) ❘ Q함수에서 벨만 최적 방정식의 백업 다이어그램 ( 오른쪽)

샘플링 버전 벨만 최적 방정식의 백업 다이어그램

Q-Learning과 벨만 최적 방정식 간의 관계

• 위의 백업 다이어그램도 SARSA ( State-Action-Reward-State-Action ) 및 벨만 방정식과의 관계 와 같이 샘플링 버전으로 고려를 하였다.
  • 샘플링 버전: 모든 전이 데이터가 아니라 '샘플링된 데이터'만 사용하는것.

 

Q-learning에서의 갱신 식

 

 

 

Q-Learning

• 강화학습의 기법이며, agent가 주어진 env에서 최적의 action을 학습하게 하는 알고리즘이다.
• 특정한 state에서 특정한 action을 취하는 경우 얻게 되는 장기적인 reward의 기대값을 학습하며, 최적의 policy를 도출함.
• off-policy기법이니, 행동 정책('탐색'을 수행함)과 대상 정책이 따로 존재한다.
  • 행동 정책으로는 주로 Q함수를 e-greedy한 정책을 사용한다.
    • 행동정책이 결정되면, 이에 따라서 행동을 선택해서 샘플 데이터를 수집한다. 
      그리고 action을 수행할때마다, Q함수를 갱신한다.
• 장점
  • 모델이 필요가 없다. ( model-free )
  • 구현이 비교적으로 간단하며, 환경이 잘 정의되어 있으면 성능이 강력함.
  • 다양한 문제에 적용이 가능. ( 범용적 )
• 단점
  • state와 action의 공간이 크면, Q테이블이 너무 커짐. 그래서 메모리와 계산량 문제 발생.
    즉, 고차원 문제에 대한 비효율성.
  • 연속적인 state와 action에 대해서는 테이블 기반 방식이 적용이 어렵다.
  • 탐험과 탐사의 비율을 적당히 조절하지 않으면, 국소 최적화에 빠질 수 있다.
• 알고리즘 전체 구조...
  • 1. 초기화
    • 모든 state-action 쌍에 대한 Q값인 Q( s , a )를 초기화. 보통은 0이나 임의의 값이다.
  • 2. 반복
    • 2-1. 환경 초기 상태 설정
    • 2-2. 종료 조건이 만족될때(목적지 도달 or 시간 초과)까지 반복.
      • a. 행동 선택( 보통 e-greedy 사용하여 탐험하는 확률도 줌. )
      • b. 행동 수행 및 보상,새로운 state 관찰
      • c. Q값 갱신
      • d. state갱신
  • 3. 종료
    • 모든 episode가 끝나면, 학습된 Q값을 사용

 

from collections import defaultdict
import numpy as np
class QLearningAgent:
    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 )

    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 update( self , state , action , reward , next_state , done ):
        if done:
            next_q_max = 0
        else:
            next_qs = [ self.Q[ next_state , a ] for a in range( self.action_size ) ]
            next_q_max = max( next_qs )
        # q함수를 갱신
        target = reward + self.gamma * next_q_max
        self.Q[ state , action ] += ( target - self.Q[ state , action ] ) * self.alpha
        # 행동 정책과 대상 정책에 대해서 갱신을 수행함
        self.pi[ state ] = greedy_probabilities( self.Q , state , epsilon = 0 )
        self.b[ state ] = greedy_probabilities( self.Q , state , self.epsilon )

env = GridWorld()
agent = QLearningAgent()
episodes = 10000

for episode in range( episodes ):
    state = env.reset()

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