4강_Model Free Control

0. Review

Model free Control Examples

• MDP 로 모델링 된 많은 응용분야가 있음.

• game, robots, helicopter flight, Go, 등등

• But, 시뮬레이션 계산 비용 매우 비쌈 (실시간으로 계산되어야 하는 부분이 있기 때문)

On-policy learning

• 직접 경험

• 추정치를 학습하고 그 policy로 부터 얻어진 경험으로 policy 평가

Off-policy learning

• 추정치를 학습하고 다른 policy로 부터 얻어진 경험을 사용해 그 policy 평가

1. Generalized Policy Iteration

Policy Update

• 처음의 정책(Policy)를 라 하고, 정책 평가를 위한 값을 라고 하면, 업데이트 되는 정책을 라 할때, 업데이트 식은 다음과 같이 성립한다.

• 결국, 정책을 업데이트 하는 것은 State-Action value function(Q)을 최대화 하는 action을 찾는것.

Iteration

• 초기값 설정 : N(s,a) =0, G(s,a)=0,

• under ,

2. Importance of Exploration

Epsilon greedy

• 특정 클래스의 정책은 모든 (s,a) 쌍이 true value로 근사적으로 수렴하는지 확인하기 위해 시행.→ 즉, 현재의 정책이 충분히 좋은지 를 확인하기 위함.

• |A|가 행동의 개수라고 하면, -greedy 정책은 다음과 같이 정의

• 즉, 1-epsilon의 확률로 주어진 식을 최대화 하는 정책을 찾고, epsilon/|A| 의 확률로는 랜덤한 a를 선택한다.

GLIE

• Greedy in the Limit of Infinite Exploration

• 모든 State-Action 쌍이 무한히 visit 된다면, 행동 정책 함수는 확률 1을 갖는 greedy policy로 수렴한다. 즉, epsilon=0으로 줄이게 된다.

3. Monte Carlo Control

Pseudo code

4. Temporal Difference Methods for Control

SARSA Algorithm

• Convergence

• 유한개의 상태와 행동을 갖는 MDP의 SARSA는 Q(s,a)가 최적의 action-value function인 Q*(s,a)로 수렴한다. 단, 다음의 조건들을 가정했을 때 성립

1. 가 GLIE 조건을 만족

2. step-size 에 대해, 다음과 같은 조건 만족

Q-Learning

• State-Action Function Q의 추정치를 유지하고, bootstrap에 사용한다. → 가장 좋은 미래 행동의 value를 사용

• SARSA와 비교

• 즉, 다음 행동만을 사용해 state-Action function을 계산하는 SARSA와 달리, Q-learning은 부트스트랩(재표본추출기법)을 사용해 다양한 action을 하고, 그 중 Q를 최대화 하는 Action을 사용한다.

• Q-learning with epsilon greedy Exploration

5. Maximization Bias

• 추정치 의 value 는 bias 를 가질 수 있다.

Double Q- Learning

• unbiased estimator인 Q 함수를 2개로 분할해 하나는 action을 선택하고(Q1), 하나는 이를 평가하는 함수(Q2)가 존재한다. → bias 낮춤

• 편차를 최대화 했기 때문에 Q-learing 은 double Q-learning보다 훨씬 더 많은 시간을 suboptimal 을 찾는데 시간을 사용한다.