Model-free control은 Agent가 관찰한 정보만으로 policy를 업데이트한다. Agent는 policy를 통해 행동을 확률적으로 선택하며, 이를 sampling이라고 한다.
모델을 완전히 알지 못하기 때문에 실제로 행동한 뒤 결과를 관찰한다. 모든 상태를 알고 예측하는 model-based와 다른 점이다.
On-policy는 직접 행동한 결과를 바탕으로 policy를 업데이트한다. Target policy와 behavior policy가 같다. 반면, Off-policy는 최종 목표인 target policy와 학습 과정에서 행동을 결정하는 behavior policy가 다른 경우를 말한다. 간접적인 경험을 통해 policy를 업데이트하는 방식이다.
대표적인 model-free contorl 알고리즘으로, on-policy는 SARSA, off-policy는 Q-learning이 있다.
ε-greedy
주어진 환경에서 최선의 선택만 하는 경우를 greedy 하다고 한다. Greedy 한 선택은 새로운 가능성을 탐색하는 대신 이미 알고 있는 정보를 반복한다. 예를 들어, 새로운 식당에 가보지 않고 항상 가던 식당만 찾는 식이다. 하지만 때로는 새로운 경험이 더 좋은 결과를 낳기도 한다.
따라서 이미 학습한 정보를 바탕으로 판단하되, 작은 확률로 랜덤한 행동을 하는 전략이 ε-greedy이다.
$\pi(a|s) \rightarrow \epsilon / m + 1 - \epsilon$ ; 최적의 행동
$\pi(a|s) \rightarrow \epsilon / m$ ; 랜덤한 행동
$m$은 전체 행동의 개수이며, $\epsilon$은 아주 작은 값이다. 위 확률을 통해 드물게 새로운 시도(exploration)를 하기도 된다.
SARSA
SARSA는 State-Action-Reward-State'-Action'을 줄인 말이다. 현재 state-action과 다음 state-action을 이용해 value function인 Q를 업데이트한다.
$Q(S_t, A_t)=Q(S_t, A_t)+\alpha [R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t, A_t)]$
TD(Temporal difference) learning과 같은 구조이다. 하지만 state value 대신 Q-function을 사용하고, 행동을 샘플링할 때 ε-greedy를 사용한다.
TD target: $ R_{t+1}+\gamma Q(S_{t+1},A_{t+1}) $
TD error: $ R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t, A_t) $
TD target은 현재 행동에 대해 보상과 미래 가치를 반영한 새로운 예측이다. TD error는 target과 현재 예측 사이의 차이다. TD error에 learning rate인 α를 곱해 Q-function에 반영한다.
모든 에피소드에 거쳐 Q-function을 업데이트하고 나면 ε-greedy를 이용해 최종 policy를 결정한다.
Q-learning
Q-learning은 off-policy로 target policy와 behavior policy가 다르다.
$Q(S_t, A_t)=Q(S_t, A_t)+\alpha [R_{t+1}+\gamma \underset{a}{max} Q(S_{t+1},a)-Q(S_t, A_t)]$
앞서 말했듯, 초반에는 다양하게 탐색하는 전략이 도움이 된다. 따라서 behavior policy는 ε-greedy를 이용해 랜덤한 변수를 준다. 하지만 충분히 학습한 agent는 돌발 행동보다 경험에 따른 최적의 선택을 내리는 것이 유리하다. 따라서 target policy는 완전히 greedy하게 결정을 내린다.
TD target: $ R_{t+1}+\gamma \underset{a}{max} Q(S_{t+1},a) $
TD error: $ R_{t+1}+\gamma \underset{a}{max} Q(S_{t+1},a)-Q(S_t, A_t) $
다시 말해, 학습 과정에서는 다양하게 탐색하지만 최종 목표는 최적의 행동을 선택하는 전략을 취했다.
Cliff Walking
Cliff walking은 SARSA와 Q-learning 특성을 비교하기 좋은 예시다.
잔디를 밟을 때마다 -1의 패널티가 주어지고, 절벽으로 떨어지면 -100의 페널티를 받는다. 최종 목적지에 도착하면 +1 보상을 받는다. 파란 실선을 따라가면 떨어질 확률이 줄어들지만 오래 돌아가야 한다. 빨간 점선을 따라가면 최소한의 페널티를 받지만, 한 번 실수해서 떨어지면 매우 큰 페널티를 받는다.
SARSA는 파란 실선을 학습하는 반면, Q-learning은 빨간 점선을 학습한다. Q-learning은 target policy가 최적의 행동만 결정한다고 가정했다. 따라서 매 순간 최적의 행동을 할 것이라고 믿고 위험하지만 빠른 길을 선택한다. SARSA는 target policy가 확률적으로 랜덤한 선택을 할 수 있다고 학습했다. 따라서 멀지만 안전한 길을 선택했다.