3 Inseok Kong Schedule

Machine Learning 17: RL Basics, Value Iteration, Policy Iteration

강화 학습을 마르코프 결정 과정으로 정식화하고, 가치 함수와 벨만 방정식, 최적 정책을 정의한 뒤, 이를 푸는 가치 반복과 정책 반복, 그리고 데이터로부터 전이 확률을 추정하는 방법을 정리한다.

강화 학습이란

지도 학습에서는 라벨 \(y\)가 각 입력에 대한 명확한 “정답”을 주었다. 그러나 순차적 의사결정과 제어 문제에서는 이런 명시적 감독을 주기가 매우 어렵다. 예를 들어 네 발 로봇에게 걷는 법을 가르치려 할 때, 처음에는 어떤 행동이 “올바른지” 알 수 없으므로 흉내 낼 정답을 줄 수 없다.

강화 학습(reinforcement learning, RL) 에서는 대신 보상 함수(reward function) 만 준다. 보상은 에이전트가 잘하고 있는지 못하고 있는지를 알려 준다. 네 발 로봇이라면 앞으로 가면 양의 보상, 뒤로 가거나 넘어지면 음의 보상을 줄 수 있다. 시간에 걸쳐 어떤 행동을 골라야 큰 보상을 얻는지 알아내는 것은 학습 알고리즘의 몫이다. 강화 학습은 자율 헬리콥터 비행, 다리 달린 로봇의 보행, 휴대전화 네트워크 라우팅, 공장 제어 등에 성공적으로 쓰였다.

마르코프 결정 과정

정의

마르코프 결정 과정(Markov decision process, MDP) 은 튜플 \((S, A, \{P_{sa}\}, \gamma, R)\)이다.

  • \(S\): 상태(state)의 집합. 헬리콥터라면 가능한 모든 위치와 자세.
  • \(A\): 행동(action)의 집합. 헬리콥터라면 조종간을 밀 수 있는 모든 방향.
  • \(P_{sa}\): 상태 전이 확률. 각 \(s \in S\), \(a \in A\)에 대해 \(P_{sa}\)는 상태 공간 위의 분포로, 상태 \(s\)에서 행동 \(a\)를 했을 때 다음 상태의 분포다.
  • \(\gamma \in [0, 1)\): 할인율(discount factor).
  • \(R: S \times A \to \mathbb{R}\): 보상 함수. 상태만의 함수 \(R: S \to \mathbb{R}\)로 쓰기도 한다.

진행은 다음과 같다. 상태 \(s_0\)에서 행동 \(a_0\)를 고르면 다음 상태가 \(s_1 \sim P_{s_0 a_0}\)로 무작위로 정해지고, 다시 \(a_1\)을 고르면 \(s_2 \sim P_{s_1 a_1}\)이 되는 식이다.

\[s_0 \xrightarrow{a_0} s_1 \xrightarrow{a_1} s_2 \xrightarrow{a_2} s_3 \xrightarrow{a_3} \cdots\]

목표: 할인된 보상의 기댓값

상태와 행동의 열을 거친 총 보상(total payoff) 은 \(R(s_0, a_0) + \gamma R(s_1, a_1) + \gamma^2 R(s_2, a_2) + \cdots\)이다. 이후로는 간단히 상태 보상 \(R(s)\)를 쓴다. 상태-행동 보상으로의 일반화에 특별한 어려움은 없다. 목표는 다음 기댓값을 최대화하도록 행동을 고르는 것이다.

\[\mathbb{E}\left[ R(s_0) + \gamma R(s_1) + \gamma^2 R(s_2) + \cdots \right]\]

시각 \(t\)의 보상은 \(\gamma^t\)만큼 할인되므로, 양의 보상은 되도록 빨리 얻고 음의 보상은 되도록 미루는 것이 유리하다. 경제 문제라면 \(\gamma\)를 이자율로 해석할 수 있다. 오늘의 1달러가 내일의 1달러보다 가치 있다.

정책과 가치 함수

정책(policy) 은 상태를 행동으로 보내는 함수 \(\pi: S \to A\)이다. 상태 \(s\)에서 항상 \(a = \pi(s)\)를 하면 정책 \(\pi\)를 실행한다고 한다. 정책 \(\pi\)의 가치 함수(value function) 는 상태 \(s\)에서 시작해 \(\pi\)를 따랐을 때 할인된 보상 합의 기댓값이다.

\[V^\pi(s) = \mathbb{E}\left[ R(s_0) + \gamma R(s_1) + \gamma^2 R(s_2) + \cdots \mid s_0 = s, \pi \right]\]

\(\pi\)는 확률변수가 아니므로 이 조건 표기는 엄밀하지 않지만 문헌에서 표준적으로 쓴다.

벨만 방정식

고정된 정책 \(\pi\)의 가치 함수는 벨만 방정식(Bellman equations) 을 만족한다.

\[V^\pi(s) = R(s) + \gamma \sum_{s' \in S} P_{s \pi(s)}(s') V^\pi(s')\]

첫째 항은 상태 \(s\)에서 시작하자마자 받는 즉시 보상이다. 둘째 항의 합은 \(\mathbb{E}_{s' \sim P_{s \pi(s)}}[V^\pi(s')]\), 즉 첫 행동 \(\pi(s)\) 이후 도착하는 상태 \(s'\)에서 시작한 할인된 보상 합의 기댓값이다. 따라서 둘째 항은 첫 스텝 이후의 미래 보상이다.

유한 상태 MDP(\(\lvert S \rvert < \infty\))에서는 상태마다 이런 식이 하나씩 있으므로, 미지수 \(V^\pi(s)\)가 \(\lvert S \rvert\)개인 \(\lvert S \rvert\)개의 선형 연립방정식이 된다. 이를 풀면 \(V^\pi\)를 효율적으로 구할 수 있다.

최적 가치 함수와 최적 정책

최적 가치 함수(optimal value function) 는 어떤 정책으로든 얻을 수 있는 최선의 기대 보상이다.

\[V^*(s) = \max_\pi V^\pi(s)\]

최적 가치 함수에도 벨만 방정식이 있다.

\[V^*(s) = R(s) + \max_{a \in A} \gamma \sum_{s' \in S} P_{sa}(s') V^*(s')\]

둘째 항은 모든 행동 \(a\)에 대해, 행동 \(a\) 이후 얻는 미래 할인 보상 합의 기댓값을 최대화한 것이다. 이 최대를 달성하는 행동으로 정책을 정의한다.

\[\pi^*(s) = \arg\max_{a \in A} \sum_{s' \in S} P_{sa}(s') V^*(s')\]

모든 상태 \(s\)와 모든 정책 \(\pi\)에 대해 다음이 성립한다.

\[V^*(s) = V^{\pi^*}(s) \ge V^\pi(s)\]

등호는 \(\pi^*\)의 가치 함수가 최적 가치 함수와 같다는 뜻이고, 부등호는 \(\pi^*\)가 다른 어떤 정책보다 못하지 않다는 뜻이다. 즉 \(\pi^*\)가 최적 정책이다. 주목할 점은 \(\pi^*\)가 모든 상태에 대해 동시에 최적이라는 것이다. 시작 상태마다 다른 최적 정책이 있는 것이 아니라, 하나의 \(\pi^*\)가 모든 \(s\)에서 최대를 달성한다. 따라서 초기 상태와 무관하게 같은 정책을 쓸 수 있다.

가치 반복과 정책 반복

이 절에서는 상태와 행동이 유한하고(\(\lvert S \rvert < \infty\), \(\lvert A \rvert < \infty\)) 전이 확률 \(\{P_{sa}\}\)와 보상 \(R\)을 안다고 가정한다.

가치 반복

가치 반복(value iteration) 은 다음과 같다.

  1. 모든 상태 \(s\)에 대해 \(V(s) := 0\)으로 초기화한다.
  2. 수렴할 때까지 모든 상태에서 다음을 갱신한다.
\[V(s) := R(s) + \max_{a \in A} \gamma \sum_{s'} P_{sa}(s') V(s')\]

최적 가치 함수의 벨만 방정식을 이용해 추정치를 반복적으로 갱신하는 것이다. 갱신 방식은 두 가지다. 동기식 갱신(synchronous update) 은 모든 상태의 새 값을 먼저 계산한 뒤 한꺼번에 덮어쓴다. 이때 알고리즘은 현재 가치 함수 추정을 새 추정으로 보내는 “벨만 백업 연산자(Bellman backup operator)”를 반복 적용하는 것으로 볼 수 있다. 비동기식 갱신(asynchronous update) 은 상태를 어떤 순서로 돌며 하나씩 갱신한다.

어느 방식이든 \(V\)는 \(V^*\)로 수렴한다. \(V^*\)를 구하면 위의 \(\pi^*\) 식으로 최적 정책을 얻는다.

정책 반복

정책 반복(policy iteration) 은 다음과 같다.

  1. \(\pi\)를 무작위로 초기화한다.
  2. 수렴할 때까지 반복한다.
    • (a) \(V := V^\pi\)로 둔다. 보통 선형 연립방정식 풀이기로 계산한다.
    • (b) 각 상태 \(s\)에 대해 \(\pi(s) := \arg\max_{a \in A} \sum_{s'} P_{sa}(s') V(s')\)로 둔다.

내부 루프는 현재 정책의 가치 함수를 계산하고(정책 평가), 그 가치 함수로 정책을 갱신한다(정책 개선). (b)에서 얻는 정책을 \(V\)에 대해 탐욕적인(greedy) 정책이라 한다. (a)는 앞서 본 대로 고정 정책에 대한 벨만 방정식, 즉 \(\lvert S \rvert\)개 미지수의 선형 연립방정식을 푸는 것이다.

유한 번의 반복 안에 \(V\)는 \(V^*\)로, \(\pi\)는 \(\pi^*\)로 수렴한다. 행동 공간과 정책 공간이 유한하므로 정책이 최적 정책에 도달하면 더 이상 바뀌지 않기 때문이다. 반면 가치 반복은 \(V^*\)로 수렴하지만 유한 번의 반복으로 정확한 \(V^*\)에 도달하지는 못하고 항상 0이 아닌 오차가 남는다.

어느 쪽이 나은가

둘 다 표준 알고리즘이며 어느 쪽이 낫다는 보편적 합의는 없다. 작은 MDP에서는 정책 반복이 매우 빠르고 적은 반복으로 수렴하는 경우가 많다. 그러나 상태 공간이 크면 \(V^\pi\)를 명시적으로 구하려고 큰 선형 연립방정식을 (그것도 여러 번) 풀어야 하므로 어려워진다. 이런 문제에서는 가치 반복이 선호되며, 실제로는 가치 반복이 더 자주 쓰이는 편이다.

둘 사이의 연결

정책 반복의 (a) 단계를 선형 풀이기 대신 반복적인 벨만 갱신으로 할 수도 있다. 다음 절차 \(\mathrm{VE}(\pi, k)\)는 \(V^\pi\)를 근사한다.

\[V(s) := R(s) + \gamma \sum_{s'} P_{s \pi(s)}(s') V(s') \quad (k\text{번 반복})\]

초기값은 0(선택 1)으로 하거나 주 알고리즘의 현재 \(V\)(선택 2)로 할 수 있다. 이 갱신이 가치 반복과 다른 점은 탐욕적 행동 대신 \(\pi\)의 행동을 쓴다는 것뿐이다. 정책 반복의 변형으로, \(V = \mathrm{VE}(\pi, k)\)를 계산한 뒤 탐욕적으로 정책을 갱신하는 과정을 반복한다고 하자.

\(k = 1\)이고 선택 2를 쓰면 이 변형은 가치 반복과 의미상 같다. 즉 가치 반복은 정책 평가 1스텝과 정책 개선 1스텝을 번갈아 하고, 이 변형은 평가 \(k\)스텝과 개선 1스텝을 번갈아 한다. 두 갱신이 똑같이 유용하고 비용이 같다면 최적 균형은 \(k \approx 1\)이므로 이 변형이 가치 반복보다 빠르지 않다. 반면 \(k\)스텝의 평가를 한 스텝씩 \(k\)번 하는 것보다 훨씬 빨리 할 수 있다면 묶어서 하는 것이 이득이다. 정책 반복이 바로 이 점을 활용한다. 선형 풀이기는 \(k = \infty\)인 \(\mathrm{VE}\)의 결과를 훨씬 빨리 준다. 상태 공간이 커서 선형 풀이기도 빠르지 않으면 이 이점이 사라지고 가치 반복이 낫다.

MDP의 모델 학습

전이 확률 추정

지금까지는 전이 확률과 보상을 안다고 가정했다. 현실의 많은 문제에서는 이를 데이터로 추정해야 한다(\(S\), \(A\), \(\gamma\)는 보통 안다). 예를 들어 역진자(inverted pendulum) 문제에서 여러 번의 시행을 했다고 하자.

\[\begin{aligned} &s_0^{(1)} \xrightarrow{a_0^{(1)}} s_1^{(1)} \xrightarrow{a_1^{(1)}} s_2^{(1)} \xrightarrow{a_2^{(1)}} s_3^{(1)} \xrightarrow{a_3^{(1)}} \cdots \\ &s_0^{(2)} \xrightarrow{a_0^{(2)}} s_1^{(2)} \xrightarrow{a_1^{(2)}} s_2^{(2)} \xrightarrow{a_2^{(2)}} s_3^{(2)} \xrightarrow{a_3^{(2)}} \cdots \end{aligned}\]

\(s_i^{(j)}\)는 시행 \(j\)의 시각 \(i\)의 상태이고 \(a_i^{(j)}\)는 그때의 행동이다. 각 시행은 MDP가 종료될 때까지(막대가 넘어질 때까지) 또는 충분히 긴 유한 시간 동안 진행한다. 이 “경험”으로부터 전이 확률의 최대우도 추정은 다음과 같다.

\[P_{sa}(s') = \frac{\#\text{times we took action } a \text{ in state } s \text{ and got to } s'}{\#\text{times we took action } a \text{ in state } s}\]

상태 \(s\)에서 행동 \(a\)를 한 번도 하지 않아 “0/0”이면 \(P_{sa}\)를 모든 상태 위의 균등분포 \(1 / \lvert S \rvert\)로 둘 수 있다. 분자와 분모의 횟수를 저장해 두면, 시행이 늘어날 때 횟수만 누적해 추정치를 효율적으로 갱신할 수 있다. 보상 \(R\)을 모르면 상태 \(s\)에서 관측된 보상의 평균을 \(R(s)\)의 추정치로 쓴다.

모델 학습과 가치 반복의 결합

모델을 추정한 뒤에는 가치 반복이나 정책 반복으로 추정된 MDP를 풀면 된다. 전이 확률을 모를 때의 학습 알고리즘 하나는 다음과 같다.

  1. \(\pi\)를 무작위로 초기화한다.
  2. 반복한다.
    • (a) MDP에서 \(\pi\)를 몇 번의 시행 동안 실행한다.
    • (b) 누적된 경험으로 \(P_{sa}\)(필요하면 \(R\)도)의 추정치를 갱신한다.
    • (c) 추정된 전이 확률과 보상으로 가치 반복을 해서 새 가치 함수 \(V\)를 얻는다.
    • (d) \(\pi\)를 \(V\)에 대한 탐욕적 정책으로 갱신한다.

간단한 최적화로 이 알고리즘을 훨씬 빠르게 할 수 있다. (c)의 가치 반복을 \(V = 0\)이 아니라 직전 반복에서 얻은 해로 초기화하면 좋은 출발점이 되어 더 빨리 수렴한다. 연속 상태 공간에서 모델을 학습하는 방법은 20강에서 다룬다.

정리

  • 강화 학습은 정답 행동 대신 보상 함수만 주고, 할인된 보상 합의 기댓값 \(\mathbb{E}[\sum_t \gamma^t R(s_t)]\)를 최대화하는 정책을 찾는다. 문제는 MDP \((S, A, \{P_{sa}\}, \gamma, R)\)로 정식화한다.
  • 정책 \(\pi\)의 가치 함수는 벨만 방정식 \(V^\pi(s) = R(s) + \gamma \sum_{s'} P_{s \pi(s)}(s') V^\pi(s')\)를 만족하며, 유한 MDP에서는 선형 연립방정식으로 풀린다.
  • 최적 가치 함수는 \(V^*(s) = R(s) + \max_a \gamma \sum_{s'} P_{sa}(s') V^*(s')\)를 만족하고, 이 최대를 달성하는 탐욕적 정책 \(\pi^*\)가 모든 상태에서 동시에 최적이다.
  • 가치 반복은 벨만 최적 방정식을 반복 적용해 \(V^*\)로 수렴한다(동기식/비동기식).
  • 정책 반복은 정책 평가(선형 풀이)와 탐욕적 정책 개선을 번갈아 하며 유한 번 안에 \(\pi^*\)에 도달한다. 작은 MDP에서는 정책 반복이, 큰 상태 공간에서는 가치 반복이 유리하다.
  • 정책 평가를 \(k\)스텝 벨만 갱신으로 바꾼 변형은 \(k = 1\)일 때 가치 반복과 같아 두 알고리즘을 잇는다.
  • 전이 확률을 모르면 시행 경험의 횟수 비율로 \(P_{sa}\)를 최대우도 추정하고, 모델 추정·가치 반복·탐욕적 정책 갱신을 반복한다.