[Reinforcement Learning] Bellman Equation

Bellman Equation

벨만 방정식을 이해하기전, 몇 가지를 정의해보자

- s : state

- a : action

- R : reward

- $ \gamma $ : Discount factor

$ \gamma $ 를 제외한 용어들에 대해서는 지난 포스팅에 충분히 설명했다.

Bellman equation을 이해하기 전, 다음과 같은 용어들을 정의하고

$ \gamma $ 는 "언젠간 쓰겠지..." 라고 생각하고 넘어가자

 

---

원리

자세한 설명보다는 우선 원리를 이해하기 위해 몇가지 예를 들어보았다.

왼쪽 아래에 우리의 Agent가 있다.

AI가 미로를 통과해서 Goal 지점으로 가고 싶은데,

다음과 같은 규칙이 존재한다.

 

<규칙>

1. 회색 지점은 지나갈 수 없고

2. 해골로 가면 죽는다.

 

해당 규칙을 바탕으로 Reward는 다음과 같이 정의할 수 있다.

그럼 어떻게 AI가 학습해서 미로까지 경로를 찾아낼 수 있을까 ?

강화학습을 통하면, 우리는 복잡한 알고리즘을 찾지 않아도 충분히 학습으로만 원하는 동작을 수행시킬 수 있다.

핵심은 우리는 AI가 스스로 알아내도록 가만히 놔둘것이다.

 

---

우리의 Agent가 무작위로 갔다가 오면서 우연히 Goal에 도착했다고 해보자

그럼 Agent는

"오 +1점을 얻었네, 나는 이 블록에 도착하게 되었을까 ?"

"바로 전 행동이 무엇이었으며, 어떤 행동으로 블록에 도착하게 되었을까?" 를 생각해보게 된다.

 

---

생각해보면 Check 표시가 된 곳에서 오른쪽으로 한 칸 움직여서 도착하게 되었다.

그럼 Agent는 Check에서의 state를 valuable state 라고 알게 된다.

그럼 check 상태에 도달하면 우리는 한 칸만 움직이면 Reward를 받는 걸 알았으니까,

Check의 state역시 Reward : +1의 가치를 지닌다고 볼 수 있다.

왜냐면 check state으로 도착만 한다면+1의 보상으로 곧장 이어지니까 !!

 

---

다음 질문은,

"그럼 V = 1 state로 가기 위해서는 어떻게 행동해야했더라 ..?"

를 생각해보게 된다.

바로 여기가 될 것이다.

물론 아래가 될 수도 있을 것이다.

여튼 그럼 다시 Check state도 V = 1 의 가치를 지닌다고 볼 수 있겠다.

같은 논리로

의 가치를 평가할 수 있을 것이다.

 

---

근데 문제가 하나 있다.

Agent의 위치를 바꿔보자 

 

Agent가 여기서 시작한다면 선택지가 아래 혹은 옆 두가지가 있다.

둘다 높은 가치를 지니는 state인데 아래, 옆 중어디로 가야할까 ??

 

이러한 문제에 봉착하게 되어 해당 방식으로 state의 value를 평가하기에는 무리가 있다.

이걸 해결하기 위해선 Bellman Equation을 적용해야한다.

---

The Bellman Equation

벨만 방정식의 형태는 다음과 같다.

$$ V(s) = \underset{a}{max} (R(s,a)+\gamma V(s^{\prime})) $$

여기에서 $ s^{\prime} $ 는 앞으로의 상태를 나타낸다.

 

방정식을 해석해보면

• 우리가 s 상태에서 a 행동을 취한다면, 새로운 상태가 되어 Reward $ R(s,a) $ 를 얻게 된다. 
• 게임이 끝나는 상황이라면 Reward는 1 or -1 혹은 게임 중이라면, R = 0 이 될 수도 있다.
• 그리고 action을 통해 $ V(s^{\prime}) $ 의 가치를 지닌 $ s^{\prime} $ state로 가게 될 것이다.
• max 함수를 통해 다음 기대값들을 최대로 가져와줄 행동에 대해 action 하게 된다.

---

그렇다면 $ \gamma $ 의 역할을 무엇일까 ?

에어전트가 어디로 가야할지 모를때, 그 가치를 판단해주는 역할이다. 

좀 더 자세히 설명을 하자면

$ \gamma $ 는 "할인율"이라고 부른다.

 

흔히 경제와 비교해서 이 discount factor를 설명하곤 하는데,

step이 증가할 수록, 우리는 다음 경로가 최적의 경로가 아니라고 판단된다. 

따라서 각 보상에서 멀어질수록(멀어진다는 의미는 보상에 도달할때 까지 필요한 step이 증가...) 일종의 discount factor를 매겨서

보상과 떨어진 곳의 가치를 낮게 판단하는 것이다.

 

즉!!! step마다 !!! 감가를 맥인다 !!!! 에 주목하자.

앞으로 Bellman equation을 조금 더 복잡한 형태로 다룰 텐데 아무리 복잡한 형태라도

Step이 증가하면, 감가가 들어간다. 

---

다음식에 맞게 state의 value를 평가해보면

여기는 V = 1 이다.

왜냐면 해당 노란색 state에서 action을 통해 갖을 수 있는 $ max(R + V(s'))$의 값이 1 이기 때문이다.

해당 논리로 아래의 차트를 채워보면

( $ \gamma  = 0.9 $ 라고 가정)

 

로 Value들을 평가해볼 수 있을 것이다.

근데 사실 이것은 우리가 전체 맵을 볼 수 있으니까 그냥 이렇게 적을 수 있는데,

Agent에게 어떻게 이러한 Value map을 갖게 할 수 있을까 ??

걔네도 우리처럼 이렇게 쉽게 적을 수 있을까?

 

다음 포스팅으로 해당 질문의 답을 하도록 하겠다.