RL-6. Model-free Control

저번 강까지는 unknown MDP에서 value function을 예측하는 방법인 Model-free prediction을 배웠다. 이번 강에는 unknown MDP에서 value function을 optimize하는 방법인 Model-free control을 배울 것이다.

Monte-Carlo Control

• Policy Evaluation을 Monte-Carlo하게 업데이트할 때 Policy Improvement를 greedy하게 가져가면 exploration을 못한다.
• exploration을 하기 위해 e-greedy를 할 수 있다.
• 아래 그림처럼 Q까지 가지 않고 1-e만큼 업데이트한다.

episode마다 각각의 S, A에 대해 q(S, A)를 업데이트한다. $\epsilon$은 $1/k$로, $\pi$는 e-greedy(q)로 설정한다. state가 없었던 e-greedy bandit algorithm의 일반화 버전이라고 할 수 있다.

GLIE (Greedy in the Limit with Infinite Exploration)

학습을 하면서 충분한 exploration을 했다면 greedy policy로 수렴하는 것을 의미

e-greedy에서도 $\epsilon$이 시간이 지남에 따라 0으로 수렴한다면 이 때도 greedy policy로 수렴함

Temporal-Difference Learning For Control

TD Advantages

• Lower Variance
• Online
• Can learn from incomplete sequences

Natural Idea: use TD instead of MC for control

• Apply TD to q(s, a)
• Use, e.g., e-greedy policy improvement
• Update every time-step

MC Control과 다르게 TD Control은 policy evaluation을 샘플링하여 SARSA형태로 업데이트한다. policy가 GLIE하다면 SARSA는 optimal action-value function으로 수렴할 것이다.

Off-policy TD and Q-learning

Dynamic Programming

state-value를 업데이트하는 policy evaluation은 다음 state에서 policy에 따른 action 확률 분포에 따른 기댓값으로 value를 업데이트한다.

state-value를 업데이트하는 value iteration은 다음 state에서 best action을 취했을 때의 기댓값으로 value를 업데이트한다.

action-value를 업데이트하는 policy evaluation은 다음 state에서 action을 취했을 때의 action-value와 다음 state에서의 reward로 업데이트한다.

action-value를 업데이트하는 value iteration은 다음 state에서 최고의 action을 취했을 때의 action-value로 업데이트한다.

TD Learning

위의 DP와 유사한 model-free TD 알고리즘은 다음 3개이다.

• state-value iteration은 최종적으로 expectation 값을 바로 쓰는 것이 아니기에 model-free TD 알고리즘이 존재하지 않는다.

On and Off-Policy Learning

On-policy learning

• Learn about behavior policy $\pi$ from experience sampled from $\pi$

Off-policy learning

target policy로 v, q를 평가함
behavior policy $\mu(a | s)$로 학습함

왜 중요할까?

• 사람을 관측하거나 다른 에이전트로부터 학습하기 위해
• 과거의 경험을 재활용할 때
• 하나의 policy를 따르면서도 여러 개의 policy를 학습할 수 있음
• exploratory한 policy를 따르면서도 greedy policy를 학습할 수 있음

Q-learning은 greedy policy의 value를 예측한다.

Q-learning Control Algorithm

random하게 샘플링된 액션을 취하는 policy를 갖고 있어도 optimize 할 수 있다.

Q-learning은 optimal로 반드시 수렴한다.

Overestimation in Q-learning

클래식한 Q-learning은 잠재적인 문제가 있다. 항상 본인의 생각 하에 최적의 값만을 선택하기 때문에 본인이 믿는 것은 과하게 믿을 수 있고 안 믿는 것은 과하게 안 믿을 수 있다. 각각 overestimate, underestimate라고 한다.

• 이 문제를 해결하기 위해서는 evaluation과 selection을 분리해야 한다.

Double Q-learning

evaluation과 selection을 분리하기 위해 Double Q-learning 방법론이 나왔다.

action-value function을 2개를 만들어서 돌아가면서 업데이트를 하는 것이다. 2명이 머리를 합친 효과를 주고 1명의 생각에 과하게 오버핏되지 않는다.

아타리 게임에서 Double DQN이 DQN보다 훨씬 나은 모습을 보인다.

이 아이디어는 다른 곳에서도 그대로 쓰일 수 있다. (e.g. Double SARSA)

Off-Policy Learning: Importance Sampling Corrections

off-policy는 다른 폴리시 $\mu$에서 생성된 경험으로부터 현재의 정책 $\pi$를 학습하는 것을 의미

Behavior가 $\mu$일 때 위 수식처럼 나타낼 수 있다. 즉, policy $\mu$를 따를 때 위 수식에서 마지막 값을 샘플링하여 사용 가능하다.

Monte-Carlo, TD, SARSA 총 3가지 방법에 대해 Importance Sampling을 적용할 수 있다. Q-learning은 Importance Sampling의 버전 중 하나이다.

MC

TD

Summary

저번 강에서 우리는 현재의 policy $\pi$를 예측하는 법을 배웠다. 이번 강에서는 policy improvement 방법에 대해 배웠다.

Q-learning은 value iteration과 유사하며 greedy policy를 추정한다.

Expected SARSA는 policy iteration과 유사하며 behavior를 evaluate하고 ㅕupdate하는 것을 반복한다.

만약, 우리가 다른 policy를 추정하고자 한다면 이것을 off-policy라고 한다.

Q-learning은 greedy target policy를 사용한다.

SARSA는 behavior로부터 stochastic하게 샘플된 것을 target policy로 사용한다. 여기에서 Expected SARSA는 임의의 target policy로 확장시킨 버전이다.

Double Learning은 policy 안에서 evaluate, select의 책임을 2개로 분리한다. target policy와 value function간의 상관관계가 필요하지 않다. greedy policy를 사용하는 Q-learning의 경우에 이 Double Learning이 useful하다.