강화학습

정책 반복법 policy iteration , 가치 반복법

정지홍 2024. 12. 6. 20:44

강화학습에서의 목표는?

  • 최적의 정책을 찾는 것이다.
    • 우리는 정책 평가 , 정책 제어 , 반복적 정책 평가 에서 마지막 부분에서 특정한 정책을 주었을때의 정책을 평가했다.
      • 이번에는 위에서 했던 것을 조금 변경해서, 정책을 수정하면서 어떠한 정책이 좀 더 좋은지 비교하면서 개선하는 것에 대해서 해볼것임.
  • 최적의 정책을 찾기 위해서는 행동 가치 함수 , 벨만 최적 방정식 , 최적 정책 에서 나온 최적 정책을 활용해야한다.
  • 아래의 식에서 argmax 연산이 최적의 정책을 찾아줄것이다.
    • argmax는 greedy정책의 종류이며, 국소적인 후보중에서 최선의 action을 선택한다.

최적 정책에 관한 식
여기서는 '임의적인 최적의 정책'이니 다음과 같이 표기를 한다.

  •  μ(s)가 현재의 정책이고 μ'(s)이 새로운 정책이라고 함...
    • 그러면 모든 state인 s에서 μ(s) =  μ'(s)이라면, 정책 μ는 이미 최적 정책이다.
      • 다르게 말하면, 모든 state s에서 정책 μ가 갱신이 안되면, 이미 최적인것이다.
      • 즉, 모든 state에 대해서  μ(s) ≤  μ'(s) 가 성립.
    • 정리...
      • 정책은 항상 개선이 되며, 개선(갱신)이 이루어지지 않는다면 그것이 최적 정책이다.
  •  정책 μ0에서 시작하여 가치 함수를 평가한다. 그리고 최적인 정책인 V0을 찾는다. 그리고 탐욕화를 수행해서  μ1의 정책을 구한다. 그리고 이를  μ0과 비교하여 같지 않으면 갱신한다.  μ1에 대한 가치 함수구하고 비교하는 과정을 같아질때까지 반복한다.(즉, 갱신이 안될때까지) 이러한 과정을 거치는 것이 정책 반복법 policy iteration이다.
    • 즉, 크게 보면 평가와 개선의 반복이다.

 

 

  • argmax 함수
    • input으로 딕셔너리를 받아서, 가장 큰 value값을 가진 key를 return함.
def argmax( d ):
    max_value = max( d.values() ) # max를 이용해서 딕셔너리 값들을 반환하며 최대값을 찾음
    max_key = 0
    for k , v in d.items():
        if v == max_value:
            max_key = k
    return max_key
  • greddy_policy 함수
    • 가치 함수를 탐욕화한다.
      • 가치 함수를 탐욕화한다는 것은, 가치 함수의 이익값을 최대화하기 위해 현재 상태에서 가장 좋은 행동을 선택하도록 정책을 변경하는것
# greedy_poicy는 argmax를 이용하여, 가치함수를 탐욕화하는 함수이다.
def greedy_policy( V , env , gamma ): # 현재 가치 함수 , 환경 , 할인률
    pi = {} # 정책을 저장할 딕셔너리이다. 즉, 상태에서 어떠한 행동을 할지에 대한 행동 확률을 저장한다.
    for state in env.states(): # 환경에서의 모든 state를 순회
        action_values = {} # 각각 4가지 행동에 따른 가치를 저장하는 딕셔너리
        for action in env.actions(): # 모든 가능한 행동을 순회
            next_state = env.next_state( state , action ) # 주어진 action수행한 결과인 다음 state를 저장한다.
            r = env.reward( state , action , next_state ) # 다음 state에 대한 reward를 얻는다.
            value = r + gamma*V[ next_state ] # 기대 가치를 계산
            action_values[ action ] = value # action에 따른 다음 state의 기대 가치를 저장.
        max_action = argmax( action_values ) # 기대 가치가 최대인 행동을 선책한다.
        action_probabilities = { 0:0 , 1:0 , 2:0 , 3:0 } # 모든 행동에 대한 확률을 0으로 초기화.
        action_probabilities[ max_action ] = 1.0 # 최대의 가치를 가지는 행동에 대해서 1.0의 확률을 부여
        pi[ state ] = action_probabilities # 해당되는 state에 대한 정책을 저장

    return pi # 정책 반환
  • policy_iter
    • 정책 반복 알고리즘 구현.
      • 정책 반복 알고리즘은 정책이 갱신안될때까지 갱신을 반복수행하는 것이다.
# 정책 반복 알고리즘을 구현한 코드.
def policy_iter( env , gamma , threshold=0.001 ):
    pi = defaultdict( lambda: { 0:0.25 , 1:0.25 , 2:0.25 , 3:0.25 } ) # 초기의 정책을 균등하게 설정한다.
    V = defaultdict( lambda: 0 ) # 초기 가치 함수 V를 0으로 초기화
    while True: # 정책을 반복적으로 수행함.
        V = policy_eval( pi , V , env , gamma , threshold ) # 현재의 정책을 평가합니다. 즉, 현재 정책에 따라서, 다음의 상태 가치 함수 V를 계산
        new_pi = greedy_policy( V , env , gamma ) # next state에 대한 새로운 정책을 탐욕화한다.. 만약 갱신이 안되면 break
        if new_pi == pi:
            break
        pi = new_pi

    return pi

수행 결과...

 

 

 

가치 반복법

  • 정책 반복법에서는 평가와 개선을 '최대한'으로 하고 번갈아가며 수행한다.
    하지만 가치 밥복법은 평가와 개선을 '최소한'으로 수행한다.
    • 즉, 정책 반복법에서는 모든 state에 대해서 가치 함수를 여러번 갱신한다. 그리고 생신을 하고 난 후에는 탐욕화를 수행했다.
      하지만, 가치 반복법에서는 하나의 state에 대해서만 갱신후 탐욕화를 수행한다.

평가 단계에서의 가치 함수 갱신식 ( 탐욕화 수식은 개선을 의미 )
평가와 개선의 식을 하나로 표현하여, '개선' 및 '평가'를 동시에 수행하는 가치 반복법의 식을 구하였다.
갱신하는 식을 위와 같이 표현하는것도 가능하다. ( 가치 반복법 )

  • 위의 식에서, k번 갱신한 가치 함수를 V k라고 한다. 그러면 (k+1)번을 수행하였다면 V (k+1)로 표현한다.
    • k=0부터 시작하여, k=1,2,3.....으로 반복하니, 한 단계에서 한번의 계산만 수행한다. 즉, dp이다.
  • 위의 식을 통해서 최적 가치 함수를 구하면, 최적의 정책을 구할수있다. ( 행동 가치 함수 , 벨만 최적 방정식 , 최적 정책 )

 

 

위의 가치 반복법의 구현...

  • 첫번째는 그리디월드
  • 2번째는 탐욕법
  • 3번째는 갱신을 한번만 수행하는 코드
  • 4번째는 갱신이 수렴할때까지 반복하는 코드
import numpy as np

class GridWorld:
    def __init__( self ):
        self.action_space = [ 0, 1, 2 , 3 ]  # 행동 할 수 있는 가지 수
        self.action_meaning = { 0:'UP' , 1:'DOWN' , 2:'LEFT' , 3:'RIGHT' } # 위에서 정의한 행동 번호가 의미 하는 바
        self.reward_map = np.array( # 게임 맵
                    [ [ 0 , 0    , 0 ,  1.0 ] ,
                      [ 0 , None , 0 , -1.0 ] ,
                      [ 0 , 0    , 0 ,  0   ] ] )
        self.goal_state = ( 0 , 3 ) # 목표 지점
        self.wall_state = ( 1 , 1 ) # 벽 지점
        self.start_state = ( 2 , 0 ) # 시작 지점
        self.agent_state = self.start_state # 에이전트 초기 상태

    @property # 맵의 행 갯수
    def height( self ):
        return len( self.reward_map )

    @property # 맵의 컬럼 갯수
    def width( self ):
        return len( self.reward_map[0] )

    @property # 맵의 쉐잎
    def shape( self ):
        return self.reward_map.shape

    def actions( self ): # 행동할수 있는 범위 
        return self.action_space

    def states( self ):
       for h in range ( self.height):
            for w in range ( self.width):
                yield ( h , w ) # yield가 있는 라인은 함수를 호출한 쪽으로 프로그램의 제어를 넘겨줌을 의미 
                # yield는 return과 다르게 함수 종료가 아니라 일지중지이다. 그래서 다음에 함수 실행시 이전 상태를 기억하고 이어서 호출이 가능
    
    def next_state( self , state , action ):
        action_move_map = [ ( -1 , 0 ) , ( 1, 0 ) , ( 0 , -1 ) , ( 0 , 1 ) ]
        move = action_move_map[ action ] 
        next_state = ( state[0] + move[0] , state[1] + move[1] ) # 위치 이동에 대해서 계산을 수행
        ny , nx = next_state

        if nx < 0 or nx >= self.width or ny < 0 or ny >= self.height: # agent가 맵을 벗어나려는 경우
            next_state = state
        elif next_state == self.wall_state: # 벽에 부딪히는 경우
            next_state = state
        return next_state

    def reward( self , state , action , next_state ):
        return self.reward_map[ next_state ]
def argmax( d ):
    max_value = max( d.values() ) # max를 이용해서 딕셔너리 값들을 반환하며 최대값을 찾음
    max_key = 0
    for k , v in d.items():
        if v == max_value:
            max_key = k
    return max_key
# greedy_poicy는 argmax를 이용하여, 가치함수를 탐욕화하는 함수이다.
def greedy_policy( V , env , gamma ): # 현재 가치 함수 , 환경 , 할인률
    pi = {} # 정책을 저장할 딕셔너리이다. 즉, 상태에서 어떠한 행동을 할지에 대한 행동 확률을 저장한다.
    for state in env.states(): # 환경에서의 모든 state를 순회
        action_values = {} # 각각 4가지 행동에 따른 가치를 저장하는 딕셔너리
        for action in env.actions(): # 모든 가능한 행동을 순회
            next_state = env.next_state( state , action ) # 주어진 action수행한 결과인 다음 state를 저장한다.
            r = env.reward( state , action , next_state ) # 다음 state에 대한 reward를 얻는다.
            value = r + gamma*V[ next_state ] # 기대 가치를 계산
            action_values[ action ] = value # action에 따른 다음 state의 기대 가치를 저장.
        max_action = argmax( action_values ) # 기대 가치가 최대인 행동을 선책한다.
        action_probabilities = { 0:0 , 1:0 , 2:0 , 3:0 } # 모든 행동에 대한 확률을 0으로 초기화.
        action_probabilities[ max_action ] = 1.0 # 최대의 가치를 가지는 행동에 대해서 1.0의 확률을 부여
        pi[ state ] = action_probabilities # 해당되는 state에 대한 정책을 저장

    return pi # 정책 반환
def value_iter_onestep( V , env , gamma ):
    for state in env.states():
        if state == env.goal_state:
            V[ state ] == 0
            continue
        action_values = [] # 특정 state에서 특정한 action을 수행하는 경우의 기대 가치를 저장
        for action in env.actions():
            next_state = env.next_state( state , action )
            r = env.reward( state , action , next_state )
            value = r + gamma*V[ next_state ]
            action_values.append( value )

        V[ state ] = max(action_values)
    return V
def value_iter( V , env , gamma , threshold=0.001 ):
    while True:
        old_V = V.copy()
        V = value_iter_onestep( V , env , gamma )
        delta = 0
        for state in V.keys():
            t = abs( V[ state ] - old_V[ state ] )
            if delta < t:
                delta = t

        if delta < threshold:
            break

    return V

두개의 차이점은 정책반복법은 상태가치함수를 업데이트하고 이를 바탕으로 정책을 업데이트한다.
그리고 다시 상태가치함수를 업데이트하고 이를 바탕으로 정책을 업데이트한다.

이렇게 반복하다가 더 이상 정책이 업데이트가 되지않으면 그것을 최적 정책으로 한다.

 

가치 반복법은 상태 가치 함수를 계속 갱신하여 최적의 상태 가치 함수를 찾고, 최종적으로 이를 이용해 최적 정책 계산한다.

 

결과적으로는 두개 다 최적의 정책을 구하기 위함이다.