Model-Free Control

MDP를 모르는 상황에서 최적의 정책을 찾는 Model-Free Control 기법에 대한 리뷰입니다.

David Silver의 "Introduction to reinforcement learning" 강의 Lecture 5를 참고하였습니다.

Outline

---

1. On-policy Monte-Carlo(MC) control
2. On-policy Temporal-Difference(TD) learning
   • Sarsa: TD방법으로 액션-가치 함수(Q)를 학습
   • n-Step Sarsa: MC와 TD의 절충안
   • Sarsa(λ)
3. Off-policy Temporal-Difference(TD) learning
   • Q러닝

---

Model-Free Control 문제

• MDP model을 모르고, 경험은 샘플링할 수 있는 문제
• MDP model를 알지만, 상태 및 액션 공간이 매우 큰 문제

On-policy vs Off-policy

1. on-policy: action을 샘플링하는 정책과 학습하는 타겟 정책이 동일
2. off-policy: 타겟 정책이 아닌 다른 정책에서 action을 샘플링할 수 있게 함

On-policy Monte-Carlo(MC) Control

[Review] Policy Iteration

1. Policy evaluation - evaluate a given policy / find value function
2. Policy improvement - act greedily with respect to value function

Model-Free Policy Iteration with Monte-Carlo Evaluation

1. [Policy evaluation] Monte-Carlo Evaluation to find action-value function(Q) 
   • state-value function(V)는 MDP를 알아야하므로 action-value function(Q)를 사용
2. [Policy improvement] ϵ-greedy Exploration using action-value function(Q)
   • Q는 특정 상태에서 각 액션을 취했을 때의 가치를 나타내므로 정책 개선을 할 때 Q를 최대화하는 action을 선택
   • greedy한 방법으로만 액션을 선택하면 특정 액션은 탐색이 안될 수 있고, 이는 잘못된 결정을 하는데 원인이 됨. 따라서 ϵ-greedy Exploration을 이용하여 (1-ϵ)확률로 greedy하게, ϵ확률로 random하게 액션을 선택

Monte-Carlo Control Process

1. Sample kth episode
2. Update action-value function for each state and action in the episode
3. Improve policy based on new action-value function

On-policy Temporal-Difference(TD) Learning

Monte-Carlo vs SARSA

[Monte-Carlo]

• use Monte-Carlo for policy evaluation
• update Q every episode

[Sarsa]

• use Temporal-Difference for policy evaluation
• update Q every time-step (에피소드 내의 액션을 하나 선택할때마다 update)
• apply to incomplete sequences & update online
• Lower variance

n-Step Sarsa

Sarsa(TD) 방법으로 update를 하면 보상 한개의 정보 밖에 알 수 없기 때문에 bias가 높고 학습하는데 오랜 시간이 걸림.따라서 n step이 지난 후에 리턴을 구하고 이 값을 이용하여 액션-가치 함수 업데이트 함.

[n-step 리턴을 구하는 방법]

• [1-Step Sarsa = TD(0)]  다음 스텝의 보상 + 다음 상태에서의 value function
• [2-Step] 첫번째 보상 + 두번째 보상 + 두번째 상태의 value function
• [n-Step] n step에서 얻은 총 보상 + n번째 상태의 value function값
• [∞-Step = MC] 에피소드 끝까지 각 스템의 보상의 합

Sarsa(λ)

time-step에 상관없이 지나온 상태, 액션을 반영하여 Q를 업데이트 함. Forward view와 Backward view가 있는데, Backward view는 Forward view의 이론을 계산적으로 매 time-step마다 update할 수 있도록 함.

[Forward view Sarsa(λ)]

• 람다라는 weight를 이용하여 모든 n-Step까지의 return들의 가중평균된 합을 이용
• 람다가 0이면 Sarsa와 동일하고, 람다가 1이면 모든 weight이 0이 되어 MC와 동일
• [장점] 미래 n-step까지 갔을 때의 return값들을 반영하여 액션-가치를 업데이트할 수 있음
• [단점] MC와 같이 에피소드가 끝나야 update를 할 수 있음

[Backward view Sarsa(λ)]

• eligibility trace는 방문빈도와 람다를 이용하여 얼마나 최근에 방문했는지를 나타내는 값
• eligibility trace값을 이용하여 현재의 리턴을 과거의 모든 액션-가치들에 분배
• [장점] time-step마다 update할 수 있음

[Sarsa(λ) Algorithm] Backward view 이용

Off-policy Temporal-Difference(TD) learning

Q Learning

• 처음으로 강화학습이 딥러닝과 결합되어 멋진 성과를 보여준 연구
• 타겟 정책을 아닌 임의의 정책을 따라 액션을 선택하므로 벨만 최적방정식에 기반을 둠
• 환경에서 실제로 실행할 액션은 임의의 정책(행동 정책)에서 ϵ-greedy로 선택하고, Q값을 업데이트하기 위한 액션은 타겟 정책에서 greedy방법으로 선택

참고

https://www.youtube.com/watch?v=0g4j2k_Ggc4&list=PLqYmG7hTraZDM-OYHWgPebj2MfCFzFObQ&index=5

https://dnddnjs.gitbooks.io/rl/content/eligibility_traces.html