cdjs의 코딩 공부방

해석본은 아래 글에 찾아보시면 될 것 같습니다.

여기서는 풀이만 진행합니다.

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

sol) 처음 얻는 reward r0 = 0이고,

나머지 reward r1, r2, r3, ... , rt = 1이므로, 위 수식을 풀어 쓰면

0 + 𝛾 + 𝛾^2 + 𝛾^3 + .... = 𝛾 / (1-𝛾)

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

sol) 처음 얻는 reward r0 = 𝛾^2 / (1-𝛾)이고,

나머지 reward r1, r2, r3, ..., rt = 0이므로, 위 수식을 풀어 쓰면

𝛾^2 / (1-𝛾) + 0 + 0 + ... = 𝛾^2 / (1-𝛾)

그리고 0 < 𝛾 < 1이므로, 𝛾 / (1-𝛾) > 𝛾^2 / (1-𝛾) 이다.

즉, optimal action은 a1이다.

(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점]

sol)

value iteration은 그때그때 최선의 value를 갖는 action을 고른다.

그렇기 때문에, Q(s0, a1) < Q(s0, a2)인 동안은 Value값이 높은 Q(s0, a2)를 계속 고르게 된다.

우선 action a2를 취할 때, s2에서 모든 Vn(s2) = 0이므로 Q값인 Qn+1(s0, a2)는 𝛾^2 / (1-𝛾)가 된다.

그리고, action a1을 취할 때의 value iteration은 다음과 같이 update된다 : 

Qn+1(s0, a1) = 0 + 𝛾Vn(s1)

Vn+1(s1) = 1 + 𝛾Vn(s1)

즉,

Qn+1(s0, a1) = 0 + 𝛾(1 + 𝛾 + 𝛾^2 + ... + 𝛾^n)

                 = 𝛾 + 𝛾^2 + ... + 𝛾^n

                 = 𝛾 * (1-𝛾^n) / (1-𝛾)

그리고 딱 저 때의 n을 n*라고 두면, action a1을 취했을 때의 Q값이 a2를 취했을 때의 Q값보다 더 크거나 같아져야 하므로,

𝛾 * (1-𝛾^n*) / (1-𝛾) >= 𝛾^2 / (1-𝛾)

이것을 n*에 대해 정리하면 좌변과 우변의 1 / (1-𝛾) 는 사라지고,

𝛾 * (1-𝛾^n*) >= 𝛾^2 에서 양변의 𝛾를 나눠주면

1-𝛾^n* >= 𝛾

𝛾^n* <= 1-𝛾

n* >= log 𝛾 (1-𝛾)  (log 밑이 𝛾, 진수가 1-𝛾) (0 < 𝛾 < 1이므로)

   >= log (1-𝛾) / log(𝛾)  (log 밑은 e)

이로써 첫 번째 부등식을 만족함을 보였다.

두, 세번째 부등식도 그냥 풀어가다 보면 만족함을 보일 수 있겠으나, 문제에서 첫 번째 부등식이 성립함을 보이기만 해도 된다고 했으니 걸러버리겠다.

해석본은 아래 글에 있습니다. 여기서는 풀이만 하도록 하겠습니다.

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

optimal value function V(s) = R(s) + 𝛾Σ s'∈S P(s'|s)V(s') 이다.

이 때, action은 무조건 오른쪽으로 가는 것이고, deterministic한 상황이기 때문에 P(s'|s) = 1이 된다. (s'의 경우의 수는 1개이다.)

이를 정리하면,

V(s) = R(s) + 𝛾Σ s'∈S V(s')

이 때, s'은 s의 바로 오른쪽 (s=G일 때는 G)가 될 것이다.

이를 사용해 goal state G에서의 optimal value function을 구해 보면,

V(G) = R(G) + 𝛾Σ s'∈S V(G)

V(G) = 1 + 𝛾 + 𝛾^2 + 𝛾^3 + ....

       = 1/(1-𝛾)             (등비급수)

V(sₙ₋₁) = R(G) + 𝛾Σ s'∈S V(s')

         = 0 + 𝛾 + 𝛾^2 + 𝛾^3 + ....

         = 𝛾/(1-𝛾)

......

V(s₁) = 0 + 0 + 0 + ... + 𝛾ⁿ + 𝛾ⁿ⁺¹ + ....

       = 𝛾ⁿ / 1-𝛾

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

optimal policy의 경우, 0<𝛾인 모든 상황에서는 위의 '무조건 오른쪽으로 가는' action을 취할 것이다.

하지만 𝛾=0인 경우엔 0<𝛾인 경우와 비슷하게 무조건 오른쪽으로 가는 action만을 취하겠지만, 그 policy 말고 다른 policy 또한 optimal policy가 될 수 있다.

(오른쪽 왼쪽 오른쪽 오른쪽 오른쪽 .... 도 optimal policy라 할 수 있다.)

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

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

영향을 끼치지 않는다.

직관적으로 보자면, 어떤 상수 c를 더한다고 해도 결국 reward가 가장 큰 것을 G일 것이므로,

optimal policy는 언제나 오른쪽으로 가는 action을 취하는 policy이라는 점은 변하지 않는다.

optimal value function을 구하면,

c를 더한 V(s)를 new_V(s), 원래 V(s)를 old_V(s)라 할때,

new_V(s) = old_V(s) + c + 𝛾c + 𝛾^2c + .... 

            = old_V(s) + c/(1-𝛾)

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

우선 위의 방식으로 optimal value function을 구하면,

new_V(s) = a * (old_V(s) + c + 𝛾c + 𝛾^2c + .... )

            = a * old_V(s) + ac/(1-𝛾)

가 된다.

이 때 a>0이라면 optimal policy는 원래와 같이 goal state G로 곧장 가는, 무조건 오른쪽으로만 가는 policy가 될 것이다.

a=0이라면, 모든 reward가 0이 되므로 모든 value function과 policy가 optimal 해 진다. (바람직하진 못하겠지만)

a<0이라면, goal state G가 가장 낮은 reward를 갖게 되므로, goal state G를 거치지 않는 모든 policy는 모두 optimal policy가 될 것이다. (즉, G를 지나는 policy는 optimal 하지 못하다.)

또한, c의 값은 어떻게 변해도 아무런 영향을 끼치지 않는다.

Assignment 1 중에서 가장 쉬운 난이도 문제였습니다.

Value function의 공식을 알고 있는지,

Optimal policy와 Optimal value function의 개념을 알고 있는지,

그리고 value function의 공식을 응용할 수 있는지에 대해 묻는 문제들이었습니다.

사실상 공식에 대입하는 문제였네요 ㅎㅎ