Value Iteration
Last updated
Was this helpful?
Last updated
Was this helpful?
Value Iteration이 Policy Iteration과 다른 점은 Bellman Expectation Equation이 아니고 Bellman Optimality Equation을 사용한다는 것입니다. Bellman Optimality Equation은 optimal value function들 사이의 관계식입니다. 단순히 이 관계식을 iterative하게 변환시켜주면 됩니다. Policy Iteration의 경우에는 evaluation 할 때 수많은 계산을 해줘야하는 단점이 있었는데 그 evaluation을 단 한 번만 하는 것이 value iteration입니다. 따라서 현재 value function을 계산하고 update할 때 max를 취함으로서 greedy하게 improve하는 효과를 줍니다. 따라서 한 번의 evaluation + improvement = value iteration이 됩니다.
value iteration의 예를 살펴봅시다. 아래 그림은 terminal state가 하나인 gridworld이고 time step이 지나갈 때마다 -1의 reward를 받는 environment입니다. 아래 그림은 value iteration의 iteration숫자가 하나씩 늘어갈 때 각 state의 value function을 표시한 것 입니다. 변하지 않는 듯이 보이는 state들이 있지만 사실 같은 값으로 계속 update되고 있는 것입니다. V2의 (2,1)state의 value function -1을 보면 V2 = max(-1 + V(주변)) = -1
max를 취하고 terminal state가 계속 0의 value function을 가지기 때문에 (2,1) state는 계속 같은 값으로 업데이트가 됩니다. 그 이후로도 이와 같이 iteration을 진행하면 optimal value function을 구할 수 있고 그로 인해 optimal policy도 구할 수 있습니다.
이렇게 Dynamic Programming에 대해서 살펴보았습니다. 처음에 언급했다시피 DP는 MDP에 대한 정보를 다 가지고 있어야 optimal policy를 구할 수 있습니다. 또한 DP는 full-width backup(한 번 update할 때 가능한 모든 successor state의 value function을 통해 update하는 방법)을 사용하고 있기 때문에 단 한 번의 backup을 하는 데도 많은 계산을 해야합니다. 또한 위와 같은 작은 gridworld 같은 경우는 괜찮지만 state 숫자가 늘어날수록 계산량이 기하급수적으로 증가하기 때문에 MDP가 상당히 크거나 MDP에 대해서 다 알지 못할 때는 DP를 적용시킬 수 없습니다.
이때 등장하는 개념이 sample back-up입니다. 즉, 모든 가능한 successor state와 action을 고려하는 것이 아니고 Sampling을 통해서 한 길만 가보고 그 정보를 토대로 value function을 업데이트한다는 것입니다. 이렇게 할 경우 계산이 효율적이라는 장점도 있지만 "model-free"가 가능하다는 특징이 있습니다. 즉, DP의 방법대로 optimal한 해를 찾으려면 매 iteration마다 Reward function과 state transition matrix를 알아야 하는데 sample backup의 경우에는 아래 그림과 같이 <S,A,R,S'>을 training set으로 실재 나온 reward와 sample transition으로서 그 두 개를 대체하게 됩니다. 따라서 MDP라는 model을 몰라도 optimal policy를 구할 수 있게 되고 "Learning"이 되는 것 입니다. sample이라면 개념이 좀 어렵게 다가올 수도 있는데 처음에 강화학습이 trial and error로 학습한다 했던 것을 떠올려서 sample이 하나의 try라고 생각하면 이해가 잘 될 것 같습니다. 즉, 머리로 다 계산하고 있는 것이 아니고 일단 가보면서 겪는 experience로 문제를 풀겠다는 것입니다. DP를 sampling을 통해서 풀면서부터 "Reinforcement Learning"이 시작됩니다.
