CS234 Assignment 1 해석

CS234의 Assignment1의 해석입니다.

사실 풀이까지 쓰려고 했는데, 학교에다가 노트를 두고오는 바람에... 풀이는 나중에 사진으로 대체하겠읍니다..

한번 풀어보시기 바랍니다. 재밌음 ㅎㅎ

아래 Assignment의 pdf와 코딩 문제의 파일은 CS234 assignment 페이지 (http://web.stanford.edu/class/cs234/assignment1/index.html) 에서 다운로드 받을 수 있습니다.

1. Optimal Policy for simple MDP

1. Figure 1에 있는 간단한 n-state MDP를 보자. State s1에서 시작하는 Agent는 어떤 state si에서도 오른쪽 (a0) 또는 왼쪽 (a1)으로 가는 action을 취할 수 있다. 모든 Action은 deterministic(결정론적)이고, 언제나 성공한다. (가령 s2에서 왼쪽으로 가면 s1으로 가고, s1에서 왼쪽으로 또 가면 s1 자신으로 돌아온다.) State에서 Action을 취함으로써 Reward를 취할 수 있다.  goal state G에서 취한 모든 Action은 r(reward) += 1 을 얻고, G에 머무른다. 그 외의 나머지 행위는 reward 0을 얻는다. discount factor ᵞ < 1 이라고 가정한다.

 

(a) optimal action은 (최적의 action은) 어떤 state si에서든 G에 도달할 때 까지 오른쪽으로 가는 것이다 (action a0을 취하는 것이다). 이 때, 모든 state si와 goal state G에서의 optimal value function을 구하여라. [5점]

 

(b) optimal policy가 discount factor ᵞ의 영향을 받는지에 대해 서술하시오. [5점]

 

(c) 모든 reward 에 상수 c를 더한다고 생각해보자. (즉, G에서는 reward 1+c를, 나머지 state에서는 reward c를 받는다.)

이 때, 모든 si와 G에 대한 새로운 optimal value function을 구하시오. 상수 c를 더한 것이 optimal policy를 바꾸는가? 답을 설명하시오. [5점]

 

(d) 모든 reward에 상수 c를 더하고 상수 a를 곱한다고 해보자. (new_r = a * (c + old_r))  이 때 모든 si와 G에 대한 새로운 optimal value function을 구하여라. 이것이 optimal policy에 변화를 주었는가? 답을 설명하고, 만약 '그렇다'고 답했다면 optimal policy를 바꾸는 a와 c의 예시를 드시오. [5점]

 

2. Running Time of Value Iteration

이번 문제에서는 value iteration을 사용하여 optimal policy를 찾을 때 사용할 steps의 갯수를 제한하는 예시를 들 것이다. Figure 2에 나오는 discount factor ᵞ < 1 인 infinite MDP를 보자. 이 MDP는 state 3개로 구성되어 있고, state에서 action을 취할 때 reward를 얻는다. state s0에서 a1의 Action을 취하면 0의 reward를 얻은 뒤 s1으로 이동하고, 그 이후의 모든 action에 대해 r = +1을 얻는다. state s0에서 a2의 Action을 취하면 s2로 이동하고 즉시 ᵞ^2 / (1-ᵞ) 의 reward를 얻지만, s2는 그 이후의 모든 action에 대해 r = +0을 얻는다.

 

(a) time step t=0인 state s0에서 action a1을 취할 때, 최종 discounted return (위 수식 참고)은 무엇인가? [5점]

 

(b) time step t=0인 state s0에서 action a2를 취할 때, 최종 discounted return (위 수식 참고)은 무엇인가? optimal action은 무엇인가? [5점]

 

(c) 모든 state의 value를 0으로 초기화 했다고 가정하자. value iteration은 위의 수식 (n* ≥ log(1-ᵞ)/logᵞ ≥ 1/2 * log(1/1-ᵞ) * 1/(1-ᵞ)이 성립할 때 까지 sub-optimal action을 선택하는데, 이를 증명하여라.

따라서, value iteration은 1/(1-ᵞ)보다 빠르게 증가한다. (첫 번째 부등식이 옳다는 것만 보이면 된다.) [10점]

 

 

3. Approximating the Optimal Value function

finite MDP M = <S, A, T, R, ᵞ> 가 있다고 생각해보자. (S = state space, A = action space, T = transition probability, R = reward function, ᵞ = discount factor이다.)

Q* 을 optimal state-action function인 Q*(s, a) = Qπ*(s, a) (이 때, π*는 optimal policy이다.) 라고 정의하자.

또, ||x||∞ = max(|x(s, a)| 일 때 Q* 의 예측값인 Q˜을 가지고 있다고 가정하자. (이 때 Q˜는 l∞ norm ||Q˜ - Q*||∞ ≤ ε으로 제한되어 있다.)

만약 Q˜에 대한 greedy policy, π(s) = argmaxₐ∈AQ˜(s, a)를 따른다고 가정하자. 이 때, 우리는 다음을 보이고 싶다: Vπ(s) ≥ V*(s) − 2ε / (1 − γ)

(이 때 Vπ(s)는 π에 대한 greedy policy를 따르는 value function이고,  V*(s) = maxₐ∈AQ*(s, a)는 optimal value function이다.)

이것은 만약 우리가 거의 optimal한 state-action value function을 계산하여 그 대략의(approximate한) state-action value function에서 greedy policy를 뽑아낸다면, 그 policy는 실제 MDP에서도 잘 작동한다는 것을 보여준다.

 

(a) π*가 optimal policy이고 V*이 oprimal value function이라고 하고, 위에서 정의했듯 π(s) = argmaxₐ∈AQ˜(s, a)라고 하자. 모든 state s∈S에서 다음의 부등식, V*(s) − Q*(s, π(s)) ≤ 2ε을 만족함을 보여라. [10점]

 

(b) part 1의 결과를 사용하여, Vπ(s) ≥ V*(s) − 2ε/(1−γ)임을 증명하라. [10점]

 

이렇게, 위의 범위가 성립함을 보였다. figure 3에 나온 2-state MDP를 고려하자. 이 MDP의 state1은 두 가지 action이 가능하다. 첫 번째 action은 reward 0을 얻고 다시 자기 자신의 state s1으로 돌아로는 action이고, 두 번째 action은 reward 2ε를 얻고 state s2로 가는 action이다. state s2는 추후의 모든 time step에 대하여 reward 2ε를 얻으며 자기 자신으로만 갈 수 있다. (어떤 action을 취해도 reward 2ε를 얻고 state s2로 돌아온다.)

 

(c) 모든 state에 대하여, optimal value function V*(s)를 구하고, state s1와 각각의 action에 대한 optimal state-action value function Q*(s, a)를 구하여라. [5점]

 

(d) π(s) = argmaxₐ∈AQ˜(s, a)일 때, Vπ(s1) − V*(s1) = −2ε/(1−γ)를 만족시키는, (l∞ norm으로 측정된) ε error를 갖는 대략적의 state-action value function Q˜이 존재함을 보여라. (일관적인 tie break rule을 정의해야 할 수도 있다.) [10점]

 

4. Frozen Lake MDP

이제 OoenAI Gym을 사용하여 Frozen Lake environment에 대한 value iteration과 policy iteration을 구현할 것이다.

starter code 에 이 environment의 custom version을 제공하였다. (최상단의 링크에서 다운로드 가능)

 

(a) (코딩 문제) vi_and_pi.py를 읽고, policy_evaluation, policy_improvement, policy_iteration을 구현하라.

maxₛ |old_V(s) - new_V(s)|로 정의되는 stopping tolerance는 10⁻³이고, γ=0.9이다. optimal value function과 optimal policy를 return하여라. [10점]

 

(b) (코딩 문제) vi_and_pi.py에서 value_iteration을 구현하여라. stopping tolerance는 10⁻³이고, γ=0.9이다. optimal value function과 optimal policy를 return하여라. [10점]

 

(c) 각각의 방법 (vi와 pi)를 Deterministic-4x4-FrozenLake-v0과 Stochastic-4x4-FrozenLake-v0의 environment에서 실행시켜 보아라. 두 번째 environment에서, world의 dynamics는 무작위적이다. (world가 어떻게 움직이는지 랜덤이라는 뜻이다.) 이 무작위성은 반복의 횟수와 policy의 결과에 어떤 영향을 미치는가? [5점]

 

 

이해가 잘 되지 않는 부분이 있거나, 혹시라도 제가 잘못 해석한 부분이 있다면 댓글로 시정 요청 부탁드립니다.

(풀이는 나중에 올리도록 하겠습니다!)