[RL] MDP - Bellman equation

 

Bellman equation (벨만 방정식)

벨만 방정식은 Richard E. Bellman의 이름을 딴 것으로, 동적 프로그래밍(Dynamic Programming)이라는 수학적 최적화 방법과 관련된 최적성을 위한 필요조건을 의미한다. (동적 프로그래밍의 핵심 아이디어인 최적성 원리를 수학적으로 표현한 것)

 

동적 프로그래밍(Dynamic Programming) 의 핵심 아이디어

1. 최적성의 원리(principle of optimality) : "최적 경로의 부분 경로 또한 최적 경로이다"라는 것을 의미

2. 순환식(recursive equation) : 최적성의 원리를 수학적으로 표현한 것으로, 문제를 더 작은 하위 문제로 분할하고, 각 하위 문제의 해를 이용하여 원래 문제의 해를 구하는 방식을 나타냄 (동적 프로그래밍에서는 이러한 순환식을 이용하여 문제를 해결한다)

 

MDP - Bellman equation 관계 정리

강화학습에서의 MDP와 Bellman Equation에 대해서 다시 한번 정리해 보면,

1. 먼저, 강화 학습은 에이전트가 환경과 상호작용하며 보상을 최대화하는 방향으로 학습하는 과정이다. 이때 에이전트의 행동은 현재 상태뿐만 아니라 과거의 상태에도 영향을 받을 수 있다.

2. 이러한 강화 학습 문제를 수학적으로 모델링하기 위한 프레임워크로 MDP를 사용한다.(문제를 명확하게 정의할 수 있게 된다). 현재 상태와 행동에 따라 다음 상태와 보상이 결정되는 과정을 Markov Property(마르코프 성질)로 단순화(현재 상태만으로 다음 상태와 보상이 결정된다 )하여 표현하는 것이다.

3. 여기서 MDP의 목표는 각 상태에서 최적의 행동을 선택하여 장기적인 보상을 최대화하는 정책(Policy)을 찾는 것이다.

4. Bellman Equation은 MDP 문제를 푸는 핵심 방정식으로, Bellman Equation을 통해 MDP 문제를 표현하면, 복잡한 문제를 작은 하위 문제로 분할하여 해결할 수 있게 된다. (value function 또는 action-value function)

5. Bellman Equation은 선형 방정식이 아니기 때문에 일반해를 구할 수 없다. 따라서 수치 해석 기법을 사용하여 근사적으로 해를 구해야 한다.

6. Dynamic Programming, Q-Learning, SARSA 등의 수치 해석 기법을 적용하여 Bellman Equation을 풀 수 있다.

 

 

결론

결국, 우리가 원하는 것은

"에이전트가 환경과 상호작용하며 보상을 최대화하는 방향으로 학습"하는 것이고,

보상을 최대화하기 위한, 상태에 대한 기대되는 누적 보상의 합(maximum value function)은

$$V^*(s) = \max_{a \in A} V^\pi(s) = \max_{a \in A} E_\pi[\sum_{t=0}^{\infty}\gamma^t R_t | S_t = s]$$

가 되고,

이 최대 가치 함수(maximum value function)를 재귀적으로 표현하면,

$$V^*(s) = \max_{a \in A} E[R_t +  \gamma V^*(s_{t+1}) | S_t = s] = \max_{a \in A} \left( R_s^a + \gamma \sum_{s' \in S} P_{ss'}^a V^*(s') \right)$$

이렇게 표현이 되는 것이다.

마찬가지로,

보상을 최대화하기 위한, 행동에 대한 기대되는 누적 보상의 합(maximum Q-function)은

$$Q^*(s) = \max_{a \in A} Q^\pi(s,a) $$

가 되고,

이 최대 행동-가치 함수(maximum Q-function)를 재귀적으로 표현하면,

$$Q^*(s,a) = R_s^a + \gamma \sum_{s' \in S} P_{ss'}^a  V^*(s') = R_s^a + \gamma \sum_{s' \in S} P_{ss'}^a \max_{a' \in A} Q^*(s',a') $$

로 표현이 된다.