지난 강의에서 Prediction인 model-free env에서 policy가 주어졌을 때 value fn를 구하는 방법을 알아보았다면, 이제 최적의 policy를 구하는 Control를 공부한다.
On-policy MC/TD: 학습하고자 하는 policy와 실제 env 경험에서의 policy가 같을 때
Off-policy 학습하고자 하는 policy와 실제 env 경험에서의 policy가 다를 때
위 problems들은 다음의 문제를 가지고 있다.
- MDP가 알려지지 않고, 경험이 sampling 가능하다.
- MDP가 알려져있지만, 너무 사용하기에 크기 때문에 sampling이 힘들다.
Model-Free Control이 문제를 해결해준다.
- On-Policy Learning: Optimal Policy와 Behavior policy가 같은 경우
- Off-Policy Learning: Optimal Policy와 Behavior Policy가 다른 경우, 다른 agent가 행동한 policy 경험으로 수정
model-based env의 DP에서의 어떻게 Control 문제를 푸는지? evaluation -> improvement
- Policy evaluation단계에서 MC 방식을 통해 Value를 평가
- Policy improvement단계에서는 Greedy policy로 진행하면 문제가 해결되는 것이 아닌가?
MC 단계에서의 value fn 계산은 가능(Policy Evaluation)하지만
Value fn를 바탕으로 Greedy Policy가 진행 == 현재, 다음 state가 무엇인지 알고, 가장 큰 value state를 안다는 뜻
== MDP를 안다는 것이므로 뒤 질문의 답변은 불가능하다.
- MDP Model을 알아야 state마다의 value fn: V에 대한 greedy improvement를 알 수 있다.
- Policy Evaluation 단계에서 action에 대한 Q(s,a)를 학습했다고 하면, Q에 대한 greedy improvement는 가능하다.
- Policy evaluation단계에서 MC 방식을 통해 Q를 평가
- Policy improvement단계에서는 Greedy policy로 진행하면 exploration 문제 발생
그러나 모든 state를 보기 않고, greedy policy하게만 움직이면 exploration이 제한적이다.
왼쪽문을 열었더니 0,오른쪽 문을 열었더니 1, 그 뒤 greedy한 policy를 따라 오른쪽 문을 열었더니 3... 그러나 왼쪽문에 얼마의 reward가 있을지 모른다.
- greedy하게만 action을 선택하면 이런 문제들이 발생한다.
- 간단한 아이디어로 exploration 보장한다.
- 입실론(매우 작은 확률)로 랜덤하게 다른 action를 선택한다.
- 1-(입실론)의 확률로 greedy한 action를 선택한다.
- (입실론)의 확률로 다른 action를 랜덤으로 선택한다.
1. 모든 action를 explore함과 2. policy가 계속 발전함을 보장한다.
e-greedy policy를 통해 policy가 무한히 발전함을 보장하는 정리
- 어떤 e-greedy policy pi에 의해서, policy가 improvement가 되는가? true
Vpi'(s) >= Vpi(s) e-greedy policy인 pi'(s)로 action 선택 >= pi(s)를 따라갔을 때의 value
- Policy evaluation단계에서 MC 방식을 통해 Q를 평가
- Policy improvement단계에서는 e-Greedy policy로 진행하면 모든 문제가 해결
좀 더 효율적인 방식의 제안으로 화살표가 끝까지 안가고 중간까지만 가는 것을 확인
- Policy evaluation단계에서 MC 방식을 통해 수렴할때 까지(한 episode방식)갈 수도 있지만, 한 episode만 쌓고 바로 improvement 단계로 가서 Q를 평가
한 episode를 가지고 policy를 개선 가능한데 기다릴 이유가 없기 때문에 evaluation 단계 때 끝까지 가지 않고 개선
- Policy improvement단계에서는 e-Greedy policy로 진행
수렴하기 위한 성질 조건
Greedy in the Limit with Infinite Exploration(GLIE)
- 모든 state-action pair들이 무한히 많이 반복되어야 한다.
e-greedy이기 때문에 무한히 많은 state를 충분히 explore 가능
- 결국에 policy는 greedy policy로 수렴해야 한다.
exploitation 하는 과정
e를 1/k로 하면서 zero로 e가 줄게 만드면 GLIE의 MC Control 방식
MC Evaluation 단계
- N은 방문시마다 count + 1
- Q는 return 이용하여 update
MC Improvement 단계
- e = 1/k
- pi = e-greedy(Q)
- GLIE MC Control를 하면 optimal action-value function에 수렴한다.
4장에서의 Black Jack Prediction 문제는 policy가 주어졌을 때, value fn를 도출하였는데, 이번 장에서는
Control 문제로 Optimal Policy와 Optimal Value가 학습된 것을 관찰 가능하다.
2021/01/15 - [Reinforcement-Learning] - Lecture 4: Model-Free Prediction 에 state 조건, action, reward 설명
stick이 카드를 안받는 경우, hit이 카드를 받는 경우
GLIE MC control를 이용한 결과 그래프
- lower variance, online, incomplete 장점이 있는 TD를 MC 자리에 넣어주면 되지 않을까?
- Q(S,A)에 적용, e-greedy pi improvement, every time-step 특성으로 전환
Sarsa: S에서 A를 했을 때 R을받아 S'에 도착하여 A'를 S'에서 실행
TD이기 때문에 episode가 안끝나고 바로바로 사용 가능
one-step action을 하고, reward를 받고 Q(S,A)자리를 update
R + r(Q(S',A') = TD target(one-step 간 S'에서의 예측치)
TD target - Q(S,A) = TD error(TD target과 차이)
아까는 화살표가 한 episode였는데 이번에는 one-step으로 바뀜
- Policy evaluation단계에서 MC 방식이 아닌 Sarsa로 Q를 평가
- Policy improvement단계에서는 e-Greedy policy로 진행
첫 S에서 e-greedy policy로 A를 선택 => 선택한 A를 실행하고, reward와 S'을 관측 => S'에서 어떤 action를 할지 선택 이 과정을 계속 반복해서 통해서 Q를 update
- Sarsa는 Optimal action-value function에 수렴한다.
다음 조건을 만족해야만 한다.
- GLIE해야한다. 모든 state-action pair를 방문하고, 결국에는 e가 줄어들어서 greedy policy로 수렴해야한다.
- Robbins-Monro sequences: 얼만큼 update할지 나타내는 step-sizes a가 충분히 크다.
실제로 사용할 때 아래의 두 조건을 고려하지 않고 해도, 어느정도는 맞아들어간다.
Robbins-Monro sequences
- a를 무한히 더하면 무한이다. step-sizes a가 Q를 무한한 곳까지 데려갈 수 있도록 해야한다.
- a^2의 합이 무한보다 작다. Q value를 수정하는 것이 점점 작아져서 수렴하게 만든다.
x축: 0 바람이 안부는 칸, 1 한칸 올려주는 바람이 부는 칸, 2 두칸 올려주는 바람이 부는 칸
Goal: S부터 G까지의 최적의 길찾기 / reward: one-step갈 때마다 -1 / Undiscounted
x축: 총 몇번 update했나 / y축: G에 도달하는 episode
첫 episode는 랜덤하게 움직이기 때문에 2000번 움직여야 도달
우연히 한번 도달하기 시작하면 reward가 발생하고 정보가 전파되면서 훨씬 적은 time steps으로 G 도달 가능
Q table를 만들기 위한 칸의 개수는? 70 * 8(king's move branches) = 560개
n-Step: TD를 써서 n까지의 reward를 보고, 거기서 부터 bootstrapping하는 것
Qt(n)을 TD target에 삽입가능하고 결국 Qt(lamda)가 TD target 부분에 들어갈 수 있다.
episode가 끝나야 적용이 가능한 Foward-view Sarsa(lamda)
- Et(s,a): 어느 시점 t일 때, s에서 a를 했을 때 Eligibility traces 값
- TD(lamda)와 같이 online 알고리즘에 Eligibility traces 값을 삽입한다.
- Sarsa는 state-action pair Q(s,a)에 Eligibility traces를 사용한다.
Q(s,a) = Q(s,a) + a * (TD error) * Et(s,a)(Eligibility traces 값) : Backward-view Sarsa(lamda)
원래는 한 state에서 action을 한 뒤 그 칸만 update해주었지만, Sarsa(lamda)는 과거의 지나갔던 칸도 Eligibility traces 값이 존재하기 때문에 모든 state를 update
계산량이 많아지지만 정보전파가 빠르다.
- one-step Sarsa를 하면 도착하는 순간 reward를 받고, 이전 state만 update
- Sasa(lamda)는 따라온 모든 경로들에 대해서, Eligibility traces 값만큼 reward update
Behaviour policy: U(a|s)는 실제 action을 sampling하는 policy
Target policy: pi(a|s) ≠ U(a|s)는 내가 직접 원하는 Policy
summary: Target policy를 evaluate해서 state value fn인 V나 action value fn인 Q를 구하고 싶은 경우, pi(a|s)를 따라서 움직인 V,Q를 구하고 싶은데 다른 agent의 action을 관찰하는 것으로부터 현재 U(a|s)를 따라 움직인 경험이 주어진 상황
- 다른 인간 혹은 다른 agents의 관찰로부터 학습한다.
- 기존 On-policy는 한번 경험 쌓고 update한 뒤 버렸는데 반해, 과거의 policies를 효율적으로 재사용 가능하다.
- exploratory policy를 따르면서(다른 행동을 하면서) optimal policy를 찾을 수 있다.
- 1개의 policy를 따르면서 multiple policies를 따를 수 있다.
X가 확률분포 P에서 sampling 되는 값들
P: 명확한(주어진) 확률분포 / Q: 구하고 싶은 확률분포
X: states / f(X): 어떤 값을 도출하는 함수
P를 따를 때의 f(X)의 기댓값 = Σ (각 확률) * f(X)
=> 분모분자에 Q(X) 곱
=> Q를 밖으로 빼면
Q를 따를 때의 기댓값 = f(X) * { P(X) / Q(X) }
- Importance Sampling: 다른 분포로 부터 구하고 싶으면, 첫번째 분포에서의 확률에서의 비율을 곱해주면 된다.
- P확률분포를 실행하고서는 Q확률분포 기댓값을 구하는 것이 목적
- MC는 u(a|s)를 이용하여, episode가 끝난뒤 return Gt를 받는 것 대신, Gt를 얻을 때까지 나왔던 action 확률의 비율(u와 pi의 비율)을 action 수 만큼 곱해주면 correction이 된다.
Gt(pi/u): 다른 policy를 따랐음에도 이 policy를 따랐을 때의 return
action 수만큼 비율을 곱해주기 때문에 variance가 극도로 크기 때문에 상상 속에서만 존재하는 방법론(u≠0일때만 가능)
TD는 one-step마다 update하기 때문에 variance가 one-step의 action만 계산하면 되므로 MC 대신 사용
- action value인 Q(s,a)를 off-policy로 학습하고 싶다. 그러나 importance sampling은 사용하지 않는다.
- 어떤 behaviour policy(U(a|s))를 이용해서 action을 선택해 실행하면 St+1에 도착, TD target은 Rt+1 + rQ(St+1, A')로 next-step에서의 추측치인 Q가 사용(bootstrapping)된다.
TD target 자리에 TD learning의 behaviour policy 대신 Q learning의 target policy(pi(a|s)를 사용
TD learning에서는 behaviour policy = target policy 상태 였을 뿐더러, TD target에서의 추측치 또한 가정이기 때문에(물론 뒤에 계산에 target policy를 따름) Q learning에서 그 자리에 target policy넣어도 이상이 없다.
- U(a|s)도 pi(a|s)처럼 improve되었으면 하고, 그러면서 탐험적 행동도 해야됨
pi(a|s) = greedy하게 improve
U(a|s) = e-greedy하게 improve
위 두 조건을 만족시키는 상태가 Q-learning
- TD target: A'자리에 greedy Q가 대체되어 max가 앞으로 튀어나와 simplifies됨
그림) s'에서 policy가 한 action 한개였기 때문에 Sarsa는 점이 하나였다.
내가 할 수 있는 actions 중에 max 값 선택하여 update하기 때문에 밑에 점이 다양하다.
- Q-learning은 optimal action-value fn에 수렴하고, Sarsa max라고도 불린다.
배웠던 내용들을 목적에 따라 비교 복습
Q: 그럼 이전 장에서 배웠던 prediction을 통해 V를 구한 것들은 사용하지 않고, 결국 Q를 사용해 update하여 control 문제를 해결하는데 그렇다면 V는 왜 구하는 것인가?
아래는 교재 및 참고 블로그, 유튜브 강좌입니다.
deepmind.com/learning-resources/-introduction-reinforcement-learning-david-silver
Interested in learning more about reinforcement learning? Follow along in this video series as DeepMind Principal Scientist, cre
We research and build safe AI systems that learn how to solve problems and advance scientific discovery for all. Explore our work: deepmind.com/research
deepmind.com
www.youtube.com/watch?v=2h-FD3e1YgQ&list=LL&index=1&t=1878s
'논문 리뷰 > RL' 카테고리의 다른 글
| REINFORCE(MC-PG) + vanila Policy Gradient (0) | 2021.03.04 |
|---|---|
| Lecture 7: Policy Gradient (0) | 2021.01.23 |
| Lecture 6: Value Function Approximation (0) | 2021.01.19 |
| Lecture 4: Model-Free Prediction (0) | 2021.01.15 |
| Lecture 3: Planning by Dynamic Programming (0) | 2021.01.13 |
| Lecture 2: Markov Decision Processes (2) (0) | 2021.01.05 |
댓글