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)

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

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