Optimal Policies and Optimal Value Functions
강화학습 문제를 해결한다는 말은 단순히 말하자면 보상을 많이받도록 하는 정책을 찾는다는 뜻이다. 그럼 더 좋은 정책이란 무엇일까? 다시말해, 현재 정책($\pi$)이 이전 정책($\pi'$)보다 좋다는 것은 어떻게 결정할 수 있을까? finite MDP에서 가치함수를 통해 다음과 같이 말할 수 있다.
모든 상태($s \in \mathcal{S}$)에서 이전 정책의 가치보다 현재 정책의 가치가 더 높거나 같다면($v_\pi(s) \ge v_{\pi'}(s)$), 현재 정책이 이전 정책보다 좋다.($\pi \ge \pi'$)
분명 가장 좋은 정책이 최소한 하나는 있을 것이다. 이를 최적의 정책(optimal policy)이라 하며, $\pi_\ast$라 정의한다. 최적의 정책이 있다면 그에 따른 최적의 가치도 있을 것이다. 이를 다음과 같이 정의한다.
- 최적의 상태 가치(optimal state-value function)
$$v_\ast(s) \doteq \max_{\pi} v_\pi(s)$$
- 최적의 행동 가치(optimal action-value function)
$$q_\ast(s,a) \doteq \max_\pi q_\pi(s, a)$$
이전 시간에 가치함수간의 관계식을 세운것처럼 최적의 가치함수 간의 관계도 동일하게 성립한다.
$$q_\ast(s, a) = \mathbb{E}[R_{t+1} + \gamma v_\ast(S_{t+1}) | S_t=s, A_t=a]$$
이전 처럼 최적의 가치함수에 대한 벨만 방정식이 정의된다. 다만 다른 점은, 최적의 정책은 가치함수가 최고인 값을 선택할 것이므로, max가 들어간다는 점이다. 이러한 방정식을 벨만 최적 방정식(Bellman optimality equation)이라 부른다.
$v_\ast$에 대한 벨만 최적 방정식
$q_\ast$에 대한 벨만 최적 방정식
finite MDP에서, 위 등식은 당연히 하나의 해답을 가지고 있다. 각 상태마다 다음과 같은 등식이 있는 것이며, 상태가 n개면 n개의 등식이 존재하는 연립방정식이 된다. 환경의 dynamics $p$까지 알 고 있다면 다양한 방법을 사용해서 수학적으로 풀 수 있을 것이다.
$v_\ast$를 알고 있다면 당연히 이 높은 값을 가진 상태를 선택해 행동하면 된다. 그러려면 일단 다음 상태들을 살펴봐야 하고 이는 한 step의 차이다. 그래서 이를 one-step-ahead search라고 볼 수 있다. 다른 용어로 탐욕적(greedy)으로 행동을 선택한다고 얘기한다. 단기적으로 행동하는 것일 수 있으나 $v_\ast$에 의해 한 step 앞만 보는 것만으로 장기적인 면을 고려한 최적의 행동으로 볼 수 있다.
$q_\ast$를 알고 있다면, 더 쉬운 문제가 된다. 다음 상태에 대해 볼 필요 없이, 행동 가치가 가장 높은 것을 선택하면 되기 때문이다. 그러다보니 환경의 dynamics 또한 몰라도 가치 비교가 충분히 된다.
결국 벨만 최적 방정식은 최적의 정책을 찾도록 해주기에 강화학습 문제를 풀었다고 할 수 있지만, 이 수식을 직접적으로 푸는 것은 좋지 않다. 이는 exhaustive search(모든 경우의 수를 다 보는 탐색 방법)과 같다. 위 방법이 가능했던 것은 다음 3가지 가정이 성립되었기 때문이다.
- 환경의 dynamics를 정확히 알고 있다.
- 문제를 풀기 위해 충분한 울트라 슈퍼 컴퓨터를 가지고 있다.
- Markov property를 만족한다.
바둑에서 1과 3은 사실 크게 중요하지 않다. 정확하게 무슨 일이 일어날지(dynamic) 알 수 있고, Markov property도 만족하기 때문이다. 하지만 바둑 게임의 경우의 수($361!$)는 너무나 어마어마 하기 때문에 슈퍼컴퓨터로도 계산할 수가 없다. 그러니 이를 근사(approximate)할 방법이 필요하다.
다양하게 많은 방법이 있을 것이다. 그 중 하나는 heuristic serach로, 트리 형태로 일정 경우의 수까지만 본 다음 선택하는 것으로 $A^\ast$ 같은 게 이에 속한다. 다른 방법으로 $dynamic programming$이 있는데, 이 방법이 더 Bellman optimality equation 방법에 가깝다. 많은 강화학습이 이러한 방정식을 근사해서 푼 것이며, 이후 챕터에서 다룰 예정이다.
