벨만 방정식(위) ❘ 벨만 최적 방정식 (아래)
Q함수에서 벨만 방정식의 백업 다이어그램 (왼쪽) ❘ Q함수에서 벨만 최적 방정식의 백업 다이어그램 ( 오른쪽)
샘플링 버전 벨만 최적 방정식의 백업 다이어그램
Q-Learning과 벨만 최적 방정식 간의 관계
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
