Search
Duplicate

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

Notation
•
처음의 정책(Policy)를 π\pi라 하고, 정책 평가를 위한 값을 VπV^{\pi}라고 하면, 업데이트 되는 정책을 π′\pi^{'}라 할때, 업데이트 식은 다음과 같이 성립한다.
•
π′(s)=arg maxaR(s,a)+γ∑s′∈SP(s′∣s,a)Vπ(s′)=arg maxaQπ(s,a)\pi^{'}(s) = arg\ max_{a} R(s,a) + \gamma \sum_{s'\in S} P(s^{'}|s,a) V^{\pi}(s^{'}) = arg\ max_{a} Q^{\pi}(s,a)
•
결국, 정책을 업데이트 하는 것은 State-Action value function(Q)을 최대화 하는 action을 찾는것.

Iteration

•
초기값 설정 : N(s,a) =0, G(s,a)=0, Qπ(s,a)=0Q^{\pi}(s,a)=0 ∀s∈S,∀a∈A\forall {s\in S}, \forall {a \in A}
•
under π\pi, i=si,1,ai,1,ri,1,si,2,ai,2,ri,2,...,si,Tii=s_{i,1}, a_{i,1},r_{i,1}, s_{i,2}, a_{i,2},r_{i,2} , ..., s_{i,T_i}

2. Importance of Exploration

Epsilon greedy

•
특정 클래스의 정책은 모든 (s,a) 쌍이 true value로 근사적으로 수렴하는지 확인하기 위해 시행.→ 즉, 현재의 정책이 충분히 좋은지 QπQ^{\pi}를 확인하기 위함.
•
|A|가 행동의 개수라고 하면, ϵ\epsilon-greedy 정책은 다음과 같이 정의
•
π(a∣s)=[arg maxaQ(s,a),with prob(1−ϵ);a w.prob(ϵ/∣A∣)]\pi(a|s) = [arg\ max_a Q(s,a) , with\ prob (1-\epsilon) ; a \ w. prob (\epsilon/|A|)]
•
즉, 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.
πt(a∣s)\pi_{t}(a|s)가 GLIE 조건을 만족
2.
step-size αt\alpha_t에 대해, 다음과 같은 조건 만족

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

•
추정치 π^\hat{\pi}의 value V^π^\hat{V}^{\hat{\pi}}는 bias 를 가질 수 있다.

Double Q- Learning

•
unbiased estimator인 Q 함수를 2개로 분할해 하나는 action을 선택하고(Q1), 하나는 이를 평가하는 함수(Q2)가 존재한다. → bias 낮춤
•
편차를 최대화 했기 때문에 Q-learing 은 double Q-learning보다 훨씬 더 많은 시간을 suboptimal 을 찾는데 시간을 사용한다.
Made with