[인공지능] 17. Making Sequential Decisions

1. Markov Decision Process

  1) Episodic Decisions 

 - nondeterministic, partially observable한 상황에서는 다음 state를 확신할 수 없다. 따라서 observations e가 주어졌을 때 outcome은 outcome s'가 맞을 때의 확률로 나타낼 수 있다. 

 P(Result(a) = s' | a, e)

 - Utility function U(s)는 각 state의 좋은 정도를 나타내는 하나의 숫자이다.

주어진 evidence에서 어떤 action을 취했을 때의 expected utility 값은, 그 action을 취했을 때 나오는 outcome의 average utility value값이다. 

EU(a | e) = ∑(s') P(Result(a) = s' | a, e) U(s')

*EU: 평균 utility, evidence e를 관측했을 때 action a를 취하면 얼마나 좋을것인가? 

 

 - maximum expected utility (MEU)는 agent의 expected utility가 가장 최대화 되는 action을 고르는 과정을 말한다.

 arg max(a) EU(a|e)

 

 - episodic 하다고 가정한다. 즉 여러번 decision을 내려야 할 때, 이전 decision과 다음 decision이 관련이 없는 경우를 말한다. 

 

 

  2) Markov Decision Process

 - sequential decision problem에서 utility function은 sequence of states에 따라 달라진다. 

 - 각 state에서 agent는 reward, 보상을 받는다. 양수일 수도, 음수일 수도 있다.

 - 만약 sequential decision problem이 "fully observable"하고 "stochastic"한 환경이라면, 그리고 markovian transition model이며 additive rewards하면 이를 Markov decision process, MDP라고 부른다. (즉, nondeterministic할 수도 있다. 내가 action a를 취한다고 생각처럼 되는게 아님)

 

 - policy : agent가 도달해야 하는 state를 가기 위해 지나는 solution state sequence를 policy라고 한다. (=contingency plan)

 - policy의 quality는 이 state들의 expected utility로 구한다. 

 - optimal policy : 가장 큰 expected utility를 갖는 policy 

 

 

 3) Expected Utility

  - Stationarity : 만약 두 state sequences가 있고, 똑같은 state에서 시작하면, 두 sequence는 같은 방법으로 preference-ordered 될 수 있다.

 

 

  - utility to sequence를 부여하는 방법 

   ⓐ additive rewards : 그냥 보상을 주는 거임

   ⓑ discounted rewards 

   Uh([s0, s1, ....]) = R(s0) + γR(s1) + γ^2 R(s2) ...

  γ 는 discount factor로 0과 1사이의 값을 가진다. sequence의 뒤로 갈 수록 rewards가 감소한다. 가까운 미래 state의 reward가 더 중요하다고 보는 것!

 

 

  - expected utility는 state s 에서 시작한 policy π 를 수행하면서 구할 수 있다. 

U^π(s) = E [ ∑(t=0, INF) γ^t R(St) ] 

state s에서 시작한 policy π의 utility는, 각 state에 discount factor를 곱해가며 reward를 다 더한 값이다. 

 

 - R(s)는 state s에서의 "short term" reward이고, U^π(s)는 "long term" total reward이다. 

 

 

  4) Optimal Policy

 - optimal policy는 가장 큰 expected utility를 갖는 policy이다.

 π*_s = arg max(π) U^π(s) 

 

  - 만약 policy  π*_a가 a에서 시작하고, policy π*_b가 b에서 시작한다면, 이들이 세번째 state c에서 시작한다고 하더라도 optimal하다. 그래서 걍 시작하는 노드 안쓰고 simply하게  π*로 표기한다.

 

 - Utility funtion에서 U(s)가 utility U^π*(s) 즉 최적의 policy를 따른다면 agent는 항상 최적의 action을 고른다.

   *Maximum expected utility : maximized the expected utility를 만드는 action을 고른다.

 

  π*(s) = arg max ∑(s') P(s' | s, a) U(s') 

 

= (state s 에서 action a를 취했을 때 s' 가 될 확률) * (s'에서 시작했을 때의 expected Utility) 

즉 어떤 action을 취했을 때 expected utility가 가장 큰 action을 취하자

 

 

 

2. Value Iteration Algorithm 

 

 1) Bellman Equation

 : state의 utility는 그 state의 reward 더하기 최적의 action을 한다고 가정 했을 때의 next state의 expected discounted utility를 말한다. 이 공식이 bellman equation.

U(s) = R(s) + γ max ∑ P(s' | s , a) U(s')

      = 현재 state reward + 최적의 선택 시 s'에서의 expected utility

 

 2) Bellman Update 

 U_i+1(s) <- R(s) + γ max ∑ P(s' | s , a) U(s')

 달라보이지만 위 Equation에서 등호를 대입으로 바꾼 것 뿐.

처음에 Utility값을 다 0에 가까운 random한 값으로 초기화 한 뒤에 위 for문을 계속 돈다. 시작점에서부터 모든 state를 계속 반복하며 utility update. 반복하면 할 수록 utility가 수렴한다. 

 

 

  - equilibrium : utility값이 변하지 않는 안정적인 상태, 즉 solution/optimal policy. 

  - 마치 정보를 propagating한다고 생각하면 됨

 

  3) Convergence of Value Iteration Algorithm

 

  - Contraction 함수 : 두 개의 input을 넣었을 때, 처음 둘의 차이보다 함숫값의 차이가 더 작은 것. 

   |f(a) - f(b)| < a-b

     -> 이 contraction을 계속 반복해서 적용하면 언젠가 fixed point에 도달한다. 

 

  - Bellman equation and Bellman update

 

  - Bellman update는 contraction 함수이다. (factor = γ) 따라서 γ<1 인 이상 value iteration은 언제나 unique solution에 수렴한다. 

 

  || BU_i - BU || = || U_i+1 - U || <= γ ||U_i - U||

 

= || i번째 utility에 bellman update 적용시킨 결과 - solution에 bellman update ||

= ||i+1번째 utility (예상) - solution의 utility || 

<= γ || i번째 utility - solution의 utility ||

 

 

증명을 해보자

 

1. |max f(a) - max g(a)| <= max |f(a) - g(a)|  --- 그림 그려보면 앎. 차의 최대값과 최댓값의 차!

2.   | BU_i(s) - BU(s) | = | γ max ∑ P(s' | s , a) U_i(s') - γ max ∑ P(s' | s , a) U(s') |

                          <=  γ max | ∑ P(s' | s , a) U_i(s') - ∑ P(s' | s , a) U(s') |

                           = γ ∑ P(s' | s , a*) (U_i(s') - U(s'))

 

3. ||BU_i(s) - BU(s)|| = max|BU_i(s) - BU(s)| <= max γ ∑ P(s' | s , a*) (U_i(s') - U(s'))

                                                       <= max γ |U_i(s') - U(s')| =γ ||U_i - U||

 

4. ||BU_i(s) - BU(s)|| = ||U_i+1 - U || <= γ ||U_i - U||

 

 

 

 4) Error Bound of Value Iteration Algorithm

 

 - 모든 states의 utility는 +-Rmax/(1-γ)의 범위를 넘지 않는다. 

 - 따라서 maximum initial error ||U0-U|| <= 2Rmax/(1-γ) 이다. 

 - 우리가 N번 iterations한다고 가정하면 γ^N*2Rmax / (1-γ) <= ε 

   즉 N = log(2Rmax / ε(1-γ)) / log(1/γ)) 이다. 우리가 몇 번 반복해야 수렴하는지 알 수 있다. 

 

 * state sequence의 utility는 등비수열의 합이 된다(공비 : γ)

  따라서 모든 state sequence utility의 평균값은 등비수열의 합보다 작다. 

 

 - 만약 update가 작아서 utility가 별로 변하지 않았다면, 진짜 utility와 비교하였을 때, error도 작을 것이다.  (이미 충분히 수렴된 상태) 

  || U_i+1-U || < ε(1-γ)/γ 이면 || U_i+1-U || < ε 이다! 

 

 - 따라서 policy π_i는 Ui가 수렴하기 전에 어느정도 optimal된다. 즉, utility value들이 정확히 solution은 아니어도 policy는 optimal인 경우가 많다. 

 

 

 

 

 

 

 

3. Policy Iteration Algorithm 

 

 1) Policy Iteration Algorithm : initial policy π0에서 시작해 다음 두 단계를 따라간다.

    ⓐ policy evaluation : policy πi가 주어졌을 때, Ui = U^πi를 구해라. 즉 만약 πi가 실행된다면 각 state의 utility가 어떻게 되는지를 계산해라

    ⓑ policy improvement : 새로운 MEU policy π_i+1을 구한다. 즉 다음 iteration의 policy를 구한다. 어떻게?

 

      π_i+1 (s) = arg max ∑ P(s' | s, a) U^πi (s')

 

 i 일 때의 policy를 통해 그 때의 utility를 계산하고, 그걸 이용해 i+1 일 때의 policy를 구한다.

 

 

 2) Analysis 

- utility값에 변화가 없을 때 종료된다.

- utility function Ui는 bellman update의 fixed point이고, 그것이 따라서 bellman equation의 solution이다. π_i 는 무조건 optimal policy이다. (뭔소리야) 

 

- 유한한 state space에는 유한한 policy가 있으므로, policy iteration은 반드시 언젠가 종료된다. 

 

 

  3) Policy Evaluation 

 : bellman equation의 간소화 버전을 알아보자.

 

 - i번째 반복에서 policy πi 는 state s에서의 atcion πi(s)로 특정됨

 - Ui(s) = R(s) + γ∑ P(s' | s, πi(s)) U^i (s')

따라서 a 대신 πi(s) 에 대해서만 검사해 줌 . 모든 action에 따른 max값을 찾을 필요 없이, 그 policy에 따른 action만 고려한다.

 

 - n states가 있을 때 time O(n^3)로 풀림 (n개의 식, n개의 미지수가 있을 때 역행렬 구하기가 이 시간복잡도를 가짐)

 

 

  4) Modified Policy Iteration Algorithm

  - Ui(s) = R(s) + γ∑ P(s' | s, πi(s)) U^i (s')

  - U_i+1(s) <= R(s) + γ∑ P(s' | s, πi(s)) U^i (s')

 

 굳이 utility값을 정확하게 구하지 않더라도 policy가 고정되어있으므로 이게 훨씬 효율적이고 좋은 근삿값을 낸다.

 

 

 

  5) Asynchronous Policy Iteration Algorithm

 - 각 반복 때 우린 state의 부분집합 중 아무거나 골라서 update를 할 수 있음. 이런게 바로 asynchronous policy iteration. 즉 쉽게 말해 iterate 중간에 일부 state에 대해서만 policy/ utility value 업데이트를 함. (항상 다 하는게 아님)