(전공복습) 인공지능 2. MDP

차례

• 차례
• 들어가기 전에
• 비결정적 탐색(Nondeterministic Search)
• 마르코프 결정 과정(MDP)
  • MDP의 정의
  • 정책(Policy)
  • Discounting
    • Stationary Preferences
  • 무한한 게임
  • V-Function과 Q-Function
    • 벨만 방정식(Bellman Equation)
  • Value Iteration
  • Policy Evaluation
  • Policy Extraction
  • Policy Iteration
  • 동적 계획법(DP)
• 정리

들어가기 전에

이 글은 컴퓨터학과 이중전공생으로서 배운 것들을 다시 한번 정리하고자 남기는 글입니다. 불완전한 기억 등의 이유로 오류가 있을 수 있으며, 참조 내지 이정표로만 사용해주세요.
본 게시글은 고려대학교의 인공지능 강의를 기반으로 작성자의 추가적인 설명이 덧붙여진 글입니다. 또한 해당 강의는 UC 버클리 CS188을 기반으로 함을 밝힙니다.

비결정적 탐색(Nondeterministic Search)

지난 시간에 이야기한 것처럼, 실제 세상은 특정 행동(Action)에 대한 결과가 명확히 정해지지 않고, 무작위적인 요소가 가미되는 경우가 많다. 지난 시간에 언급한 Expectimax 역시 무작위적인 요소를 고려하는 알고리즘이다. 이러한 무작위적인 세계(Stochastic World)에서 유틸리티를 최대화하는 방법에 대해 알아보자.

마르코프 결정 과정(MDP)

일반적으로 마르코프(Markov)는 메모리가 없는 대상을 의미한다. 메모리가 없다는 말은, 미래가 오직 현재에 의해서만 결정된다는 것을 의미한다. 예를 들어 자판기를 생각해보자. 자판기에 돈을 넣을 때, 100원을 5번 넣든 500원을 1번 넣든 똑같이 500원이다. 500원이라는 현재가 중요한 거지, 그 500원까지의 역사(100원 5번이냐 500원 1번이냐)는 중요하지 않다. 반면, 자판기인데 반환 레버를 누르면 넣은 돈을 그대로 반환해주는 자판기를 생각해보자. 이 경우 100원 5개를 넣었다면 100원 5개를, 500원 1개를 넣었다면 500원 1개를 그대로 반환해야 한다. 이처럼 미래가 과거와 독립적이지 않다면, 이는 마르코프 상태가 아니다.

(물론, 이건 일반적인 1차(First Order) 마르코프 성질을 의미하는 것이다. N차 마르코프 성질은 가장 최근 N개의 상태를 고려하는 것으로 일반화할 수 있다. 0차 마르코프는 동전 던지기나 주사위 굴리기처럼 모든 상황이 독립적이다. 1차 마르코프는 바로 직전 상황만이 영향을 미친다. 2차 마르코프는 최근 2개 상황만이 영향을 미친다.)

MDP의 정의

MDP는 아래와 같은 요소로 정의될 수 있다.

• 상태(State) \(s \in S\)
• 행동(Action) \(a \in A\)
• 전이함수(Transition Function) \(T(s, a, s') = P(s' \vert s, a)\)
  • 모형(Model) 혹은 Dynamics라고도 하며, 현재 상태와 행동이 주어졌을 때, 다음 상태로 \(s'\)이 올 확률을 계산하는 함수이다.
• 보상함수(Reward Function) \(R(s, a, s')\)
  • \(s\) 상태에서 \(a\) 행동을 통해 \(s'\) 상태로 넘어갔을 때의 보상이다.
• 시작 상태(Start State) \(s_0\)와 (상황에 따라) 종료 상태(Terminal State) \(s_t\)

전이함수와 보상함수가 오롯이 현재 상태(\(s\))와 취할 행동(\(a\)), 이로 인한 미래(\(s'\))로만 결정된다는 것에 주의하자. 이것이 바로 마르코프 성질이다. 과거 상태들은 고려하지 않기 때문이다.

정책(Policy)

MDP에서 우리의 목적은 가장 좋은 정책(Policy)을 찾는 것이다. 정책이란 \(\pi: S \to A\)인 함수를 의미한다. 풀어서 설명하자면, 정책 \(\pi\)는 상태를 입력으로, 행동을 출력으로 가지는 함수이다. 좀 더 쉽게는, 정책은 상태에 따라 행동을 결정하는 규칙이다. 편의를 위해 최선의 정책을 \(\pi^*\)라고 하자.

Discounting

그렇다면 최선의 정책이 무엇일까? 우선, 보상이 커질수록 좋은 정책임은 자명하다. 또한, 보상을 되도록 빠르게 획득하는 것이 더 좋은 것이라고 할 수 있다. 이 두 가지를 어떻게 동시에 고려할까? 오늘 1000원을 받는 것과 내일 2000원을 받는 것, 둘 중 뭐가 더 좋을까?
이때 고려할 수 있는 것이 Discounting이다. Discounting이란 보상이 시간에 따라 \(\gamma\)배만큼 감소하는 것을 의미한다. 이를테면 \(\gamma = 0.5\)일 때, 현재의 1000원은 다음 단계의 500원, 그 다음 단계의 250원, 그 다음 단계의 125원과 같다. 한 스텝 늦게 보상을 받을 때마다 실질적인 가치가 절반씩 감소하는 것이다.

Stationary Preferences

Stationary Preferences란 아래를 만족하는 것을 의미한다.
\([a_1,a_2,...] \succ [b_1,b_2,...] \Leftrightarrow [r,a_1,a_2,...] \succ [r,b_1,b_2,...]\)
쉽게 이야기해서 지금 \(a \succ b\)이면, 나중에도 \(a \succ b\)여야 한다는 것이다. 1000원은 500원보다 값지다. 내일도, 모레도, 같은 시기에 받는 1000원과 500원은 항상 일관된 우선순위를 가져야 할 것이다.
이때, 성립하는 유틸리티는 두 가지가 있다.

• Additive: \(U([r_0, r_1, r_2, ...]) = r_0+r_1+r_2...\)
• Discounted: \(U([r_0, r_1, r_2, ...]) = r_0+\gamma r_1+ \gamma^2 r_2...\)

무한한 게임

무한한(종료되지 않는) 게임에서 우리는 무한한 유틸리티를 얻게 될까? 이는 불편한 일이다. 유틸리티 간 비교가 어렵고 비직관적이기 때문이다. 무한한 게임에도 불구하고 유틸리티를 유한하게 만드는 방법은 아래와 같은 것들이 있다.

• Finite Horizon: 일정 단계 후 게임을 강제로 종결시킨다. Depth Limited Search처럼 탐색 구간을 한정하는 것이다.
• Discounting: 앞서 언급한 Discounting도 보상을 수렴시킨다. \(0 < \gamma < 1\)이면 무한등비급수가 수렴하기 때문.
• Absorbing State: 어떤 정책을 세우든, 언젠가는 다른 상태로 가지 못하는 종료 상태에 도달한다는 것을 증명한다.

V-Function과 Q-Function

V-Function \(V^*(s)\)란 \(s\) 상태에서 시작해서 매 순간 최적으로 행동했을 때 얻게 될 보상의 기댓값을 의미한다.
Q-Function \(Q^*(s, a)\)란 \(s\) 상태에서 \(a\) 행동을 하는 것으로 시작해서 매 순간 최적으로 행동했을 때 얻게 될 보상의 기댓값을 의미한다.

벨만 방정식(Bellman Equation)

벨만 방정식이란 V-Function을 재귀적으로 정의하는 것을 의미한다. 벨만 방정식을 통해 최적의 정책 \(\pi^*\)를 계산할 수 있다.

우선, \(V^*(s) = \max _a Q^*(s,a)\)라고 할 수 있다. 풀어서 설명하자면, 상태 \(s\)에서 V-Function은 그 상태에서 Q-Function이 가질 수 있는 최댓값이라는 뜻이다. V-Function은 현재 상태부터 최적으로 행동했을 때의 보상 기댓값이고, Q-Function은 현재 상태의 행동은 정해져 있고, 그 이후부터 최적으로 행동했을 때의 보상 기댓값이므로 이는 자명하다.

그렇다면 \(Q^*(s,a)\)는 어떻게 정의할 수 있을까? \(Q^*(s,a) = \sum\limits_{s'}T(s,a,s')[R(s,a,s') + \gamma V^*(s')]\)이다.
식이 복잡한데 천천히 살펴보자. \(T(s,a,s')\)는 선택에 따른 확률을 나타내는 전이함수였다. \([R(s,a,s') + \gamma V^*(s')]\)는 선택에 따른 보상(\(R(s,a,s')\))과 그 이후에 얻게 될 보상(\(\gamma V^*(s')\))의 합, 즉 전체 보상을 의미한다. 정리하자면 다음과 같다: Q-Function은 \(s\)에서 \(a\)를 선택함에 따라 얻을 수 있는 경우의 수들의 가중합(기댓값)이다.

위 두 가지 식을 합치면, \(V^*(s) = \max _a\sum\limits_{s'}T(s,a,s')[R(s,a,s') + \gamma V^*(s')]\)이다. 이 과정은 사실상 가능한 Expectimax들을 계산하는 것과 다름없다.

Value Iteration

V-Function의 값을 반복적으로 계산하는 것을 Value Iteration이라 한다. 상기한 벨만 방정식은 재귀적인데(즉,\(V^*(s)\)의 계산에 \(V^*(s')\)이 쓰이는데), 따라서 아래와 같은 점화식으로 표현할 수 있다.

• \[V_0(s) = 0\]
• \[V_{k+1}(s) = \max _a\sum\limits_{s'}T(s,a,s')[R(s,a,s') + \gamma V_k(s')]\]

당연하지만, 이 계산을 매우 많은 수의 노드에 대해 수행하는 것은 큰 비용이 드는 일이다. 다행히도 V-Function의 \(\gamma\)가 1보다 작다는 가정 하에 수렴을 증명할 수 있다.

1. 임의의 \(k\)에 대해, \(k\)레벨의 탐색 트리와, 거기서 한 층 더 내려간 \(k+1\)레벨의 탐색 트리를 생각해 보자.
2. 만약 \(V_k(s)\)와 \(V_{k+1}(s)\)가 같다면 수렴한다고 할 수 있다.
3. 두 탐색 트리는 마지막 레이어를 제외하고는 완벽하게 동일할 것이다.
4. 그리고 그 마지막 레이어는 보상 \(R(s, a, s')\)의 값을 가져야 한다.
5. 따라서 마지막 레이어의 최대치는 \(R_{max}\), 최소치는 \(R_{min}\)이며, 동시에 \(\gamma^k\)만큼 Discount된 값을 가질 것이다.
6. 즉 \(V_k(s)\)와 \(V_{k+1}(s)\)는 최대 \(\gamma^k \max \vert R \vert\)만큼 차이날 것이다.
7. 우리는 \(\gamma\)가 1보다 작다고 가정하였으므로, \(\gamma^k \max \vert R \vert\)은 언젠가 0이 되어 수렴한다.

이 값이 언젠가는 수렴하겠지만, 값이 수렴할 때까지 모든 계산을 반복하는 것 역시 비효율적이다. 전체 \(S\)개의 상태에서, \(A\)개의 행동이 있다고 할 때, Value Iteration을 단 한 번 계산하는 데에 드는 시간 복잡도는 \(O(S^2A)\)이다. 모든 상태에 대해(\(O(S)\)), \(\sum\limits_{s'}\)를 구하면서(\(O(S)\)), 이를 모든 행동에 대해 수행해서 \(\max _a\)를 구해야 하기 때문이다(\(O(A)\)).

하지만, 조금 생각해보면 V-Function의 값이 수렴하기 한참 전에 \(\pi^*\)는 수렴했을 것이라는 점을 알 수 있다. 즉, 구체적인 보상의 기댓값이 수렴하기 전에도, 정책 자체는 대략적으로 정해지게 된다.

Policy Evaluation

Value Iteration의 목적은 Value, 즉 보상의 기댓값을 수렴시키는 것이었다. 그런데 위에서 말한 것처럼 대부분의 경우 구체적인 보상의 양은 그다지 중요하지 않다. 중요한 것은 정책(어떤 선택을 해야 하느냐)이지, 보상(그렇게 했을 때 정확히 얼마를 받느냐)이 아니다.

그렇다면 정책이 고정되어 있을 때, 그 정책의 보상 기댓값을 계산하는 것은 어떨까? 이를 Policy Evaluation이라고 한다. Value Iteration과 비슷하게, Policy Evaluation \(V^{\pi}(s)\)은 아래와 같은 점화식으로 나타낼 수 있다.

• \[V_{0}^{\pi}(s) = 0\]
• \[V_{k+1}^{\pi}(s) = \sum\limits_{s'}T(s,\pi(s),s')[R(s,\pi(s),s') + \gamma V_{k}^{\pi}(s')]\]

위 식은 사실 모든 행동에 대해 수행해서 최댓값(\(\max _a\))을 가져오는 대신 정책에 따라 정해진 행동(\(\pi(s)\))에 대해서 수행한다는 점을 제외하고는 Value Iteration과 동일하다. 즉 \(A\)개의 행동에 대해 수행하던 작업을 정해진 하나의 행동에 대해서만 수행하기 때문에 시간 복잡도는 \(O(S^2)\)이 된다.
또한, Value Iteration과 Policy Evaluation의 큰 차이점 중 하나는 선형성의 여부인데, Value Iteration은 \(\max\) 연산 때문에 비선형적이다. 하지만 Policy Evaluation은 선형 시스템(Linear System)이기 때문에 훨씬 쉽게 계산할 수 있다.

Policy Extraction

지금까지 배운 걸 잠시 정리해보자면 아래와 같다.

• V-Function: 최적의 정책에 따른 보상 기댓값을 나타내는 함수
• Q-Function: 초기 행동이 결정되어 있고, 그 이후 최적의 정책을 따랐을 때의 보상 기댓값을 나타내는 함수.
• Bellman Equation: V-Function을 재귀적으로 계산할 수 있도록 정의한 방정식.
• Value Iteration: 최적의 정책에 따른 실제 보상 기댓값.
• Policy Evaluation: 정해진 정책에 따랐을 때의 보상 기댓값.

여기에 더해, 이번엔 Policy Extraction에 대해 알아보자. Policy Extraction을 위와 같이 정리하자면, 현재 Value가 주어져 있을 때, 그 기댓값을 얻기 위한 정책이다.
조금 어려울 수 있는데, Value Iteration의 결과(Value)는 단순히 숫자임에 집중하자. Value Iteration(과 Policy Evaluation)은 보상의 양을 구하는 거지, 그 보상을 얻기 위해 어떻게 행동해야 하는지(정책)를 알려주지는 않는다. 즉, Value Iteration은 숫자(\(\max\))고, Policy Extraction은 그때의 정책(\(\arg \max\))이다. 따라서 Policy Extraction은 단순히 V-Function의 \(\max\)를 \(\arg \max\)로 바꾸기만 하면 된다.

• \[\pi^* (s) = \arg \max_a \sum\limits_{s'} T(s, a, s')[R(s, a, s') + \gamma V^*(s')]\]

물론 Value Iteration과 달리 이 값은 여러 번 계산할 필요가 없다. Value Iteration은 반복을 통해서 최적의 값을 계산하는 과정이고, Policy Extraction은 계산된 최적값을 얻기 위한 행동(정책)만을 알아내는 것이기 때문이다.

이때, 이전에 언급한 것처럼 V-Function의 뒷부분은 Q-Function이다. 따라서 최적의 기댓값(Value)이 아니라 초기 행동이 지정된 이후의 기댓값(Q-Value)을 알고 있다면 Policy Extraction 역시 더 간단하게 할 수 있다.

• \[\pi^* (s) = \arg \max _a Q^*(s,a)\]

Policy Iteration

드디어 Policy Iteration이다. Value Iteration은 최적의 보상 기댓값(Value)을 구하는 방법이었다. Policy Iteration은 최적의 정책(Policy)을 구하기 위한 방법이다. 물론 Value Iteration을 수행한 후 Policy Extraction을 수행해도 최적의 정책을 구할 수 있지만, 이는 지나치게 시간 복잡도가 높기 때문에 어렵다. Policy Iteration은 두 가지 단계를 반복해서 수행한다.

1. 현재 정책의 보상이 수렴할 때까지 평가한다(Policy Evaluation).
2. 수렴한 Value를 통해 새로운 정책을 도출한다(Policy Extraction).

정책이 수렴해서 더이상 변하지 않으면 Policy Iteration은 완료된다. Policy Iteration은 처음에 최적이 아닌 정책으로 시작해도, 반복된 갱신을 통해 Value Iteration보다 빠르게 최적의 정책을 찾을 수 있다는 장점이 있다.

동적 계획법(DP)

참고로, Value Iteration과 Policy Iteration 모두 동적 계획법(Dynamic Programming)으로 계산할 수 있다(상기 점화식들을 기억해보라).

정리

이번 게시글에서는 MDP에 대해 알아보았다. 아래 개념들에 대해 잘 숙지하자.

• V-Function: 최적 정책에 따른 보상 기댓값(Value)을 계산하는 함수.
• Q-Function: 초기 행동이 결정되어 있고, 그 이후 최적 정책대로 행동했을 때의 보상 기댓값(Q-Value)을 계산하는 함수.
• Bellman Equation: V-Function에 대한 재귀적인 정의.
• Value Iteration: 반복을 통해 V-Function을 수렴시키는 것.
• Policy Evaluation: 주어진 정책의 보상 기댓값을 계산하는 것.
• Policy Extraction: 주어진 보상 기댓값에 따른 정책을 계산하는 것.
• Policy Iteration: Policy Evaluation과 Extraction을 통해 정책을 수렴시키는 것.

다음에는 세계에 대한 정보가 없는 상황에서의 Online Planning 강화학습 방법론에 대해 알아볼 것이다.

• 2024 18
• 2023 143