Value function & Bellman equation

2024.10.16 - [AI/강화학습] - Markov Decision Process

Markov Decision Process

강화학습의 기초 내용과 MDP에 관한 내용이 담긴 글이다.

 

본 포스팅은 충남대 김현 교수님의 강의자료를 바탕으로 쓴 글입니다. 

 

환경에 대한 모델, MDP 모델을 아는 상태에서 이 환경 모델을 이용해 최선의 정책을 찾는 것은 계획이다.

환경을 모를 때 s에서 a를 취해보고 정보를 얻어 환경과 지속적으로 상호작용하며 최선의 정책을 찾는 것은 강화학습이다.

 

1. Policy

어떤 State에서 Action a를 행하기 위해선, 수많은 a 중 하나를 '선택'해야 하는데, 이것이 Policy이다.

 

정책(Policy)는 agent가 어떤 s에서 어떤 a를 취할지 결정하는 함수인데,

• 각 state에서 하나의 a (action 확률이 100%) 만을 취하는 policy를 Deterministic Policy라고 한다. Stochastic Policy의 일종, pi(s) = a
• 각 state에서 어떤 a를 취할지 결정하기 위한 확률을 이용하는 것이 Stochastic Policy, pi(a|s)

 

2. Value Function

각 상태 또는 행동이 장기적으로 얼마나 좋은지 알려주는 함수는 가치함수이다.

• 상태가치함수 : 정책 pi가 주어졌을 때, 어떤 s에 대한 가치. 즉, s에서 시작해서 끝날 때까지 받은 return의 기댓값, v
• 행동가치함수 : 어떤 a에 대한 가치. 즉, s에서 a를 했을 때 끝날 때까지 받은 return의 기댓값, q

상태가치함수 + action -> 행동가치함수

• 아래쪽 Value가 위쪽에 비해 작은 이유 : 위쪽은 미래에 A와 B를 거쳐갈 확률이 높기에 보상으로 10을 받을 확률이 크다. 하지만 밑의 부분은 A또는 B를 거칠 확률이 낮고, 벽에 부딪히기에 보상이 적다.
• A/B state의 value는 왜 10/5보다 작거나 큰가? : 모든 state에 감가율을 곱해서 더해진 최종 누적 보상을 계산한 것이기에.

 

3. Bellman Equation

벨만 방정식, 이건 뭐하는 거냐면

우리는 아까 상태가치와 행동가치의 값을 보려면 Return 값을 알아야 했다. 끝까지 가야 한다는 거다.

근데 그건 너무 오래 걸리니까.. 다음 state와 연결해서 현재 상태가치나 행동가치를 추정할 수 없을까? 해서 탄생한 것이다.

 

따라서 State-value Bellman equation과 Action-value Bellman equation은 모두 현재의 value/action value와 다음 state들의 value/action value를 연결한 것으로 나타내는 것이다.

말로만 하면 이해가 어려울 수도 있으니 우선 벨만이 뭐 하는 애인지만 알고 넘어가자.

 

우선 상태가치 벨만 방정식부터 봐보자.

 

이게 상태가치함수를 다음 상태의 상태가치함수로 재귀적으로 표현한 것이다.

여기서 우리가 모르는 건 v(s)와 v(s_t+1)이다.

근데 둘 다 추정치인데 어떻게 추정치로 추정치를 구하지..?

우선 의문만 가지고 다음으로 넘어가자.

 

 

바로 행동가치 벨만 방정식을 살펴보겠다. 둘의 관계가 있으니까 이런다.

 

이것도 위와 같은 방식으로 해서 재귀적으로 나타냈다.

action이 추가된 거 말고는 정말 다 똑같다.

여기서도 현재 q와 다음상태 q는 모른다.

그리고 둘 다 추정치이다.

 

 

그럼 여기서 조금 더 발전해서, action을 고르는, policy pi가 주어질 때 state/action 가치는 어떻게 구해지냐면,

 

이렇게 하면 아까 위에서 봤던 state/action value function의 형태가 된다.

 

 

 

 

 

 

그럼 이제 다시 그림을 봐보겠다. 만약 이 그림에서 우리가 어떤 a를 취할 거고, 이때 r을 얼마나 받을지를 알게 된다면, 

위의 Bellman 방정식으로 이 state value를 계산할 수 있게 된다.

 

그럼 이제 약간의 변화가 생겼다.

state value function을 action value function으로 나타낼 수 있게 됐고,

action value function을 state value function으로 나타낼 수 있게 됐다.

 

 

이걸 가만히 살펴보면.. q자리에 q식을, v자리에 v식을 넣으면 위의 Bellman expectation equation이 되는 것을 알 수 있다.

그럼 이제 우리는 MDP 모델(pi가 주어질 때 어떤 a를 해서 어떤 s로 가게 되고, 이때 어떤 r을 받는지)을 알게 되면,

상태가치나 행동 가치를 알 수 있다고 한다!

 

예시로 보겠다.

 

이렇게, state들이 순환적으로 연결돼있고, 

state value는 정해지지 않은 상태이다.

 

V(A)를 나타낸 것처럼, 같은 방식으로 V(B), V(C), V(D)를 나타낼 수 있다.

그럼 미지수가 4개고, 식도 4개가 나와 딱 이 문제를 풀 수 있게 된다!

 

물론.. 미지수가 엄청나게 많아지면 불가능하겠지만

 

 

그럼, 앞의 방법에서 이제 현재 상태가치와 다음 상태가치의 관계는 어느 정도 이해했다.

근데 state가 너무 많아지면 이 방법으로 해결할 수 없단 말이지..

그래서 처음부터 다시 생각해봤다. agent의 목표가 무엇인지.

이는 가치함수의 값이 궁금한 게 아니다. 그저 최대 return을 얻을 policy를 찾는 것이다.

그래서 방향을 틀어서 optimal policy를 구하려 한다.

 

4. Optimally equation

어떤 상태에서는 policy1을, 어떤 상태에서는 policy2를 따르는 게 좋을 것이다. 상황마다 좋은 정책이 다르단 뜻이다.

그렇다면 새로운 정책, 즉 어떤 상태에서도 가장 좋은 정책을 찾을 순 없을까?

 

조금만 다르게 생각해보면, '항상 좋은 정책'을 찾기보다, 각 상태에서 좋은 policy를 갖고 오는 방법을 생각하는 것이다.

그럼 자연스럽게 어떤 policy보다 높은 expected return값을 갖는, optimal policy를 찾을 수 있게 될 것이다.

 

각 상태에서 가장 좋은 액션을 취하려면, v는 그대로 두고, q는 여러 q 중 가장 max 값을 찾으면 된다.

그리고 v는 정책*행동가치 였는데, 어차피 가장 큰 q를 구했고, 이걸 쓸 거라면 이걸 바로 v에 넣으면 된다.

 

이렇게 된다고 생각하면 된다.

 

 

 

 

v는 원래 정책과 곱해서 다 더하는 거였는데 그냥 max q를 구하는 식으로 바뀌었고,

 

q는 식의 형태는 그대로이다. 

 

 

 

그럼 실질적으로 그냥 expectation equation과 optimally equation이 뭐가 다른지 봐보자.

진짜 계산을 해보자는 말이다!

각 확률을 모두 0.5라 하자.

Bellman expectation

0.5*(1+1*2)+0.5*(1+1*4) = 4

0.5*(1+1*2)+0.5*(1+1*6) = 5

0.5*4+0.5*5 = 4.5

Bellman optimality

0.5*(1+1*2)+0.5*(1+1*4) = 4

0.5*(1+1*2)+0.5*(1+1*6) = 5

max(4, 5) = 5

 

 

이것도 계산하는 방법은 위와 같다.

단지 q를 먼저 계산하냐 v를 먼저 계산하냐가 다를 뿐!

 

 

 

 

 

 

그리고 이렇게 optimal value 중 가장 큰 값을 취한 optimal policy는 deterministic policy이다!

격자를 살펴보자면,

 

이렇게 되고, 예시 들어진 2행 5열의 값을 보면,

각 방향으로의 상태가치함수를 계산해보면

왼쪽 방향으로의 v가 가장 큰 16의 값을 가지고 있으므로 그 셀의 optimal value는 16이 되고, optimal policy는 왼쪽방향이 된다.

optimal policy는 당연히 여러 방향이 될 수 있고,

특히 A, B의 경우에는 4방향이 모두 optimal이다.