Lecture 7: Markov Decision Processes - Value Iteration

요약

 Greedy나 DP 알고리즘 문제에서 많이 볼 수 있는 Search Problem에서는 특정 state $s$에서 action $a$를 취하면 확정적으로 새로운 state $s'$으로 간다. 하지만 여기서는 조금 더 현실세계의 특성을 반영하여 action $a$를 취했을 때, $s'$으로 갈 확률$T(s,a,s')$이 주어진다. 

 이번 장에서는 확률과정에서의 optimum path를 찾는 방법에 대하여 다룬다.

 

예제 설명 및 MDP

 이번 장에서는 설명을 위하여 동전을 던져서 앞뒤를 맞추는데, 도전할 경우에는 4원을 받고, 성공할 경우에는 다시 또 게임을 하고 실패할 경우에는 4원을 받고 끝나며, 도전을 포기할 경우에는 6원을 받고 끝나는 게임을 예로 들어 설명하겠습니다.

 이 게임에서 $4n$원을 받을 확률은 앞뒤를 맞출 확률이 1/2이므로 $1/2^n$으로 주어지게 됩니다. 이 때, 내가 받을 것으로 기대되는 reward를 utility라고 하며, 계속 도전할 경우의 utility는

$utility = 4 \times \frac{1}{2} + 8 \times \frac{1}{4} + 12 \times \frac{1}{8} + \dots $

으로 주어지며, 포기할 경우의 utility는

$utility = 6 \times 1$

로 주어지게 됩니다.

 이 장의 목표는 utility를 최대로 만드는 최선의 전략(policy)를 찾는 것입니다.

 또한, 위의 예제를 Markov Decesion Process(MDP) 로 나타내고 그림으로 표현하면 아래와 같이 표현할 수 있습니다. Transition이 현재의 상태에만 의존하기 때문에 Markov 모형이라 할 수 있습니다.

 

 

Discounting

 Discounting($\gamma$)이란 당장의 보상을 미래의 보상보다 더 선호하는 경향성을 나타내기 위한 파라미터로서, step이 지남에 따라 exponential하게 보상의 가치가 낮아진다는 가정이 들어가게 됩니다. 예를 들어, 3 단계 후의 utility 역시 $4 \times \frac{1}{2}$ 이지만, $\gamma$가 0.9인 경우의 utility는 $(0.9)^2 \times 4 \times \frac{1}{2}$ 가 됩니다. 즉, reward의 가치가 하락한 것을 알 수 있습니다. $\gamma = 1$인 경우에는 현재의 reward와 미래의 reward의 가치가 같으며, $\gamma = 0$인 경우에는 미래의 reward는 가치가 없는 극단적인 경우를 나타냅니다.

 

Policy evalution

 이제 state $s$에서 기대되는 utility를 최대화하기 위해 선택해야 하는 전략(policy)를 구하기 위해 몇가지 변수를 정의하겠습니다. $s$에서 policy $\pi(s)$를 따를 때, value of policy를 $V_\pi(s)$, Q-value of policy를 $Q_\pi(s,a)$라 하고 정의는 아래와 같습니다.

$V_\pi(s)=\begin{cases}0, & \mbox{if s is end} \\Q_\pi(s,a), & otherwise\end{cases}$

$Q_\pi(s,a)=\sum_{s'}T(s,a,s')[Reward(s,a,s')+\gamma V_\pi(s')]$

 위의 예제에서 $\pi = "도전"$인 경우의 Value of policy 는 아래와 같이 풀 수 있습니다.

$V_\pi(end) = 0$

$V_\pi(in) = \frac{1}{2}(4+V_\pi(end)) + \frac{1}{2}(4+V_\pi(in)) = 8$ (도전 후 실패한 경우 + 도전 후 성공한 경우)

 

 위의 예제처럼 아주 쉬운 경우에는 이처럼 손으로 풀리지만, state가 아주 많거나 관계가 복잡한 경우에는 손으로 깔끔하게 풀린다고 보장할 수 없다. 따라서 앞의 강의들에서 사용했던 머신러닝의 아이디어를 가져와서 최적의 $V_\pi(s)$ 값을 찾게 되는데, 이러한 방법을 Policy evaluation이라 한다. 

 적당히 $V_\pi(s)$값이 수렴할 때 까지 $V_\pi(s)$ 값을 여러 step에 걸쳐 update해 나갈건데,
1. t step에서의 value of policy를 $V_\pi^{(t)}(s)$라 하면, 먼저 $V_\pi^{(t)}(s)$를 모든 s값에 대하여 0인 벡터로 초기화 해준다.

 2. 그 후 각각의 state $s$에 대하여 아래와 같이 update를 해준다.

 $V_\pi^{(t)}(s) = \sum_{s'}T(s,a,s')[Reward(s,a,s')+\gamma V_\pi^{(t-1)}(s')] \equiv Q_\pi^{(t-1)}(s,\pi(s))$

 3. 위의 과정을 아래와 같이 변화량이 일정값 이하가 될때까지 반복해준다.

 $max_s \lvert V_\pi^{(t)}(s) - V_\pi^{(t-1)}(s) \rvert \le \epsilon$

 

Value iteration

 위에서 value of policy 값을 recurrent하게 구하는 방법을 알았으니, 이를 이용하여 이번에는 최적의 value $V_{opt}(s)$ 를 구할 것인데 이러한 방법을 value iteration이라 한다.

$V_{opt}(s)=\begin{cases}0, & \mbox{if s is end} \\Q_{opt}(s,a), & otherwise\end{cases}$

$Q_{opt}(s,a)=\sum_{s'}T(s,a,s')[Reward(s,a,s')+\gamma V_{opt}(s')]$

  코딩으로 구현하는 방법은 위의 policy evaluation과 같은데 과정 2의 업데이트 방식만 아래와 같이 바꿔주면 된다.

 $V_{opt}^{(t)}(s) = max_a \sum_{s'}T(s,a,s')[Reward(s,a,s')+\gamma V_{opt}^{(t-1)}(s')] \equiv max_a Q_{opt}^{(t-1)}(s,\pi(s))$

 

Python Code(클릭 시 github로)

# 도전시 +4원, 포기 시 +6
class MDP:
    #state : in, out
    def isEnd(self,state):
        return state == 'end'
    def actions(self):
        return ['bet','notBet']
    def succProbReward(self, state, action):
        # return (new state, prob, reward)
        #        (self.state, prob, money)
        result = []
        if state =='in':
            if action == 'bet':
                #실패
                result.append(('end',1/2,4))
                #성공
                result.append(('in',1/2,4))
            else:
                result.append(('end',1,6))
        else :
            result.append(('end',1,0))
        return result
    def discount(self):
        return 1
    def states(self):
        return ['in','end']
 
def valueIteration(mdp):
    V = {}
    for s in mdp.states():
        V[s] = 0
    def Q(state,action):
        return sum(prob*(reward+mdp.discount()*V[newState]) \
            for newState, prob, reward in mdp.succProbReward(state,action))
    while 1:
        newV = {}
        for state in mdp.states():
            if mdp.isEnd(state):
                newV[state] = 0
            else:
                newV[state] = max(Q(state, action) for action in mdp.actions())
        if max(abs(V[state]-newV[state]) for state in mdp.states()) < 0.001:
            break
        V = newV
        print(V)

MDP Modeling

 line6 : state $s$가 in 일때는 가능한 $a$가 bet과 notBet으로 주어집니다.

 line8 : $s = 'in'$인 경우, bet을 취할 경우에는 4원을 받고 1/2의 확률로 in으로, 1/2의 확률로 end로 가게 됩니다. $s='end'$인 경우에는, 확정적으로 reward가 없습니다.

 line23 : 위의 코드에서는 $\gamma = 1$, 즉, 미래의 reward와 현재의 reward의 가치가 같습니다.

 

Value iteration

 line30 : $V_{opt}(s)$를 모든 s에서 0으로 초기화합니다.

 line38 : $s='end'$인 경우에는 reward를 받을 수 없으므로 value of policy는 항상 0이 됩니다.

 line42 : 위에서 설명한 value iteration의 종료조건인 과정3을 나타냅니다. $V$ 값의 변화량이 0.001 이하가 되면 과정을 종료합니다.

 

위의 코드를 돌려보면 $V('in') = 8, V('out') = 0$으로 위에서 손으로 푼 결과와 같은 값을 얻을 수 있습니다. 따라서 Optimal policy $\pi('in')$은 'in'상태에 계속 머무르기 위한 '도전'이 됩니다.