이제 드디어 실전에서도 적용 가능한 강화학습 알고리즘이 나옵니다. Sutton and Barto 교과서 챕터 4에서는, MDP 문제에서 p값들을 알고 있을 경우 Dynamic Programming 방법을 통해 최적 정책을 알아내는 것을 다룹니다. 본 챕터에서는 다음에 네 가지 개념만 숙지하시면 됩니다.

• Policy Evaluation: 어떤 정책이 주어지면, 그 정책 \(\pi\)에 따른 \(v_\pi\)값들을 구하는 것입니다.
• Policy Improvement: 벨만 방정식을 이용해 정책을 개선하는 것을 말합니다.
• Policy Iteration: 위의 두 가지의 반복을 통해 MDP 문제를 푸는 것입니다.
• Value Iteration: 위의 방식에서 굳이 정책의 \(v_\pi\)값을 구하지 않고 바로 v값들을 개선시켜 나가는 것입니다.

4.1 Policy Evaluation (Prediction)

출처: Sutton and Barto Textbook, p.75

Policy Evaluation 알고리즘은 정책 \(\pi\)를 인풋으로 받습니다. 그리고 파라미터 \(\theta\)는 언제 루프를 멈출지를 결정합니다. V값들이 \(\theta\)보다 많이 업데이트되지 않으면 루프를 멈추게 되므로, 이 값이 작을수록 더 정확한 V값들을 학습하게 됩니다.

초기화: 에피소드의 끝인 V(terminal)는 0으로 두고, 나머지 상태들의 V(s)값은 무작위로 초기화합니다.

루프:

먼저 \(\Delta\)값을 0으로 초기화합니다.

모든 상태 s에 대해 아래와 같이 업데이트를 합니다.

1. v라는 변수에 이전값 V(s)를 저장합니다.
2. V(s)를 벨만 방정식에 따라 업데이트를 합니다. (벨만 방정식은 챕터 3 참조)
3. \(|v - V(s)|\)는 해당 V(s)가 이번 턴에 얼마나 업데이트되었는지입니다. \(\Delta\)값은 결국 모든 s 중에서 가장 많이 업데이트된 V값의 변화량을 저장합니다.

파라미터 \(\theta\)보다 변화량 \(\Delta\)이 적으면 루프를 중단합니다.

결국 해당 정책에 따라 계속 에피소드를 돌리면서, 얻는 r값들이 저 벨만방정식(루프 안의 2)을 통해 V(s)값들을 업데이트하게 됩니다. 사실 이 부분은 실제 예를 보면 훨씬 더 명확히 이해되는 부분이 있습니다. Sutton and Barto 교과서 76페이지의 Example 4.1를 참조하시기 바랍니다.

4.2 Policy Improvement

다음은 정책을 개선하는 알고리즘입니다. Policy improvement theorem에 따르면, 두 정책 \(\pi\)와 \(\pi'\)가 있다고 가정할 때,

\(q_\pi(s, \pi'(s)) \geq v_\pi(s)\), for all \(s \in S\)이면, 정책 \(\pi'\)는 적어도 \(\pi\)와 같거나 더 낫습니다.

즉, \(v_{\pi'}(s) \geq v_\pi(s)\)가 성립됩니다.

책 78페이지에서는 이 정리(theorem)을 증명하는데 지면을 할애합니다. 수학적으로 관심있으신 분은 참조바랍니다.

이 정리를 따라서, Policy improvement 알고리즘은 아래의 업데이트를 모든 s와 그에 대한 모든 a에 대해 반복함으로써 이루어집니다.

쉽게 말해 새로운 정책 \(\pi'\)는, 각 상태(s)별로 가장 높은 q값을 주는 행동 a를 선택하는 것입니다. 알고리즘은 아래 4.3의 내에서 설명합니다.

4.3 Policy Iteration

위의 두 가지를 종합하면, 최적 정책을 찾는 policy iteration 알고리즘이 나옵니다.

출처: Sutton and Barto Textbook, p.80

1. 초기화: 모든 s에 대하여 V(s)값과 \(\pi(s)\)값들을 무작위로 초기화합니다.

2. Policy Evaluation: 4.1의 설명과 동일합니다. 주어진 정책에 대해 V값을 업데이트 합니다.

3. Policy Improvement:

policy-stable이란 변수의 값을 참(true)으로 초기화합니다.

각 상태 s에 대하여:

• a. old-action이란 변수에 이전 \(\pi(s)\)값을 저장합니다. 예전 정책이 해당 상태 s에서 하던 행동입니다.
• b. 새 \(\pi(s)\) 값을 업데이트합니다. 벨만 방정식을 통해, 바로 [다음의 보상 + 다음 상태의 V값 V(s')]가 가장 높은 행동을 선택합니다.
• c. 만약 예전 정책(old-action)과 b에서 업데이트한 정책에 따른 행동이 동일하지 않으면 policy-stable 변수를 거짓으로 변경합니다.

위의 a, b, c를 모든 상태 s에 대해 적용한 후, 하나의 s라도 \(\pi(s)\)값이 변했으면 policy-stable 변수가 거짓입니다. 그러면 2. Policy Evaluation로 돌아가 업데이트된 정책에 대한 V값을 업데이트하고 또 3으로 옵니다. 만약 하나의 s도 변화하지 않았으면 수렴한 것입니다.

결국 정책에 대해 V값을 업데이트하고, 그 V값을 이용해 각 s에 대한 최적의 a를 구해 정책을 업데이트하고, 또 다시 업데이트된 정책에 대해 V값을 업데이트하는 것을 반복합니다. 이 또한 구체적인 예시를 보는 것이 이해에 도움이 될 수 있으니 페이지 81-82를 참조 바랍니다.

4.4 Value Iteration

위의 Policy Iteration은 한번 V값을 업데이트할 때마다 정책을 업데이트합니다. 반면, Value Iteration은 V값을 수렴할 때까지 업데이트한 후, 마지막에 정책을 배웁니다.

Policy Iteration의 Policy Evaluation 파트에서 v값을 업데이트하는 식은 아래와 같습니다.

반면 Value Iteration에서의 v값 업데이트는 아래와 같습니다.

아주 비슷한데, Policy Iteration이 주어진 인풋 정책에 따른 행동 a에 대해서 V값을 배우는 반면, Value Iteration은 가능한 모든 정책 a들 중 최대값을 주는 V값을 배웁니다.

출처: Sutton and Barto Textbook, p.83

위는 Value Iteration 알고리즘의 유사코드입니다. 파라미터 \(\theta\)는 이전과 비슷하게, V값 업데이트가 \(\theta\)보다 많이 업데이트되지 않으면 루프를 멈추도록 합니다. 전체적으로 보면 루프(Loop) 부분이 V값을 업데이트하는 것이고, 수렴한 V값에 대해 최적 정책을 한번만 배웁니다. 마찬가지로 구체적인 예시에 대해서는 84페이지를 참조 바랍니다.

그러면 중요한 질문은, Policy Iteration과 Value Iteration 중에 누가 더 나은가입니다. 답은 환경에 따라 다르다는 것입니다. 일반적으로 Value Iteration이 빠른데, 환경과 할인율 \(\gamma\)에 따라 Policy Iteration이 훨씬 빠르기도 합니다.

4.5 Asynchronous Dynamic Programming

Asynchronous란 단어는 싱크가 맞지 않는다는 뜻입니다. 앞서 다룬 두 DP 알고리즘의 단점 중 하나는, 매 턴(step)마다 모든 상태(s)에 대해 계산을 해야한다는 것입니다. 바둑이나 Backgammon 게임처럼 엄청나게 많은 상태(state)가 가능한 문제에서는 엄청난 계산 부담이 발생합니다. Asynchronous DP는 간단히 말해서, 매 턴(step)마다 모든 상태(s)를 계산하지 않고, 그때 그때 다른 상태(s)들을 선별적으로 업데이트하는 것입니다. 어떤 상태(s)의 V값을 여러 번 업데이트하는 동안, 다른 상태(s')는 한번도 업데이트되지 않을 수 있습니다. 그러나 이 부류의 알고리즘들이 올바른 답으로 수렴하기 위해서는, 계속 모든 상태(s)들을 최소한 한 번씩은 계산해야만 합니다. 즉, 어떤 시점 t 이후부터는 업데이트되지 않는 s가 있게 되면 안됩니다. 이 부류의 알고리즘들은 좀더 유연하고, 에이전트가 MDP에서 행동함과 동시에 업데이트가 진행되는 것도 가능하게 합니다. 자세한 내용은 책의 범위를 벗어나기 때문에 다루지 않습니다.

4.6 Generalized Policy Iteration

위의 Policy Iteration, Value Iteration, 그리고 Asynchronous DP는 모두 policy evaluation과 policy improvement를 언제, 어떤 비율로 하느냐를 다르게 했을 뿐 기본적으로 하는 일은 같습니다. 이를 묶어서 Generalized Policy Iteration이라고 합니다.

4.7 Efficiency of Dynamic Programming

State space와 action space가 매우 큰 문제들에게 DP를 적용하기는 힘들겠지만, MDP를 푸는 다른 방법에 비해서 DP는 매우 효율적인 편입니다. State의 개수를 n, 액션의 개수를 k라 두면, DP의 효율성은 n과 k의 polynomial function입니다. 직접 검색할 경우 모든 가능한 정책의 경우의 수가 \(k^n\)이고, DP는 최적의 정책을 찾는 것을 보장(guarantee)한다는 것을 감안하면 효율적이라 할 수 있겠습니다. Linear Programming 방법도 MDP를 풀 수 있고, 어떤 경우 worst-case 수렴이 DP보다 빠르기도 하지만, LP는 DP에 비해 state space의 개수가 늘어남에 따라 적용 불가능한 시점이 백 배 정도 빨리 옵니다.

현대의 컴퓨터를 사용하면, 수백만개의 state를 가진 문제 정도는 DP로 풀 수 있습니다. 매우 많은 state space를 가진 문제에서 DP를 사용하려면 Asynchronous DP가 선호됩니다.