Recall

지금까지 Agent, Environment가 action, state, reward로 상요작용하는 Markov Decision Process를 알아보았다. 강화학습에서는 이를 통해 Value Function,즉 주어진 state, action에서 reward를 극대화하는 policy를 찾는 것이 목적이다.

Bellman equation

Policy에 대해 살펴보기 전에 Value function에 대해서 더 살펴보기로 하자.
Value Function은 주어진 상태에서의 기댓값을 나타내는 State Value Function, 주어진 상태와 행동에 따른 기댓값을 나타내는 Action Value Function으로 나누어진다고 했다.

Bellman equation에 따라 두 개의 value function 사이의 관계를 정의할 수 있다.

Optimal Policy

위에 보는 것처럼 value function을 정의했으면, 이 value function을 최대화하는 policy 즉, Optimal Policy를 선정해야 한다.

위 State Value Function을 최대화하는 P(at|st) 를 찾아야한다. 이 때, Optimal Action Value Function을 안다고 가정했을 때 Policy는 다음과 같은 방법으로 찾을 수 있다.

1. Dynamic Programming

이미 주어진 혹은 알고있는 Markov Decision Process에 따라 Reward를 정의하고 제한된 환경에서 에이전트를 학습시키는 과정.

2. Model-Free Policy

MDP가 주어지지 않은 상황에서 environment와 상호작용하며 경험을 축적하고 이를 통해 Optimal Policy를 찾는 과정.

1) Monte Carlo

기본적인 Monte Carlo 방법은 큰 수의 법칙을 생각하면 될 것 같다.

Monte Carlo 방법은 무작위하게 탐색을 하는 과정으로 생각하면 되지만, 이때 탐색에서 앞서 말했던 입실론-greedy 방법을 통해 Policy를 최적화 시키고, 이에 따라 Q값 또한 최적화되게 된다.

2) Temporal Difference

Temporal Difference는 Monte Carlo와 같이 N번의 탐색을 통해 Optimal Policy를 찾아나가는 과정이지만, 무작위 탐색이 아닌 지금까지의 탐색을 토대로 더 나은 Q값을 찾아나가는 과정이다.

이렇게 해서 N-1번째 탐색으로 얻은 Q값을 토대로 N번째 Q값을 업데이트 하게 된다. 이 때 최적의 Q값과 Policy를 구해나가는 과정을 SARSA 알고리즘이라고 한다.

MC, TD를 비교해보면 MC방법은 탐색을 많이 하며 unbiased하지만 분산이 매우 커진다. 반면, TD는 과거의 탐색을 바탕으로 Q값을 업데이트 하므로 biased하지만 분산은 작아진다.