💪🏻

Bellman Equation

생성일

2024/07/11 15:16

태그

강화학습

작성자

Bellman Equation

1. Value functions

Value function은 각 state s 또는 state-action pair (s,a)가 앞으로의 과정이 policy

\pi

를 따라 진행한다고 할 때, Return의 기댓값의 관점에서 그 가치를 평가하는 함수이다. 정리하자면 현재 state s 혹은 (s,a)가 앞으로 얼마나 많은 reward를 얻을 수 있는지 나타내는 함수이다.

2. State-value function

•

vπ(s)v_\pi(s)vπ​(s) = Eπ[Gt∣St=s]E_\pi[G_t|S_t = s] Eπ​[Gt​∣St​=s]

→ 현재 state s의 가치를 나타내는 함수로 현재 state s에서 시작하여 policy

\pi

를 따를 때 Return의 기댓값으로 표현된다. 만약 Return의 기댓값이 크다면, 그 state에서 앞으로 받게 될 평균적인 reward가 크다는 의미이므로 가치가 높다고 판단할 수 있다.

3. Action-value function

•

qπ(s,a)=Et[Gt∣St=s,At=a]q_\pi(s,a) =E_t[G_t|S_t=s, A_t=a]qπ​(s,a)=Et​[Gt​∣St​=s,At​=a]

→ 현재 state s에서 action a를 취했을 때의 가치를 나타내는 함수로 현재 state s에서 action a를 선택하고 이후에 policy

\pi

를 따라 진행할 때의 Return의 기댓값으로 표현된다. 만약 action-value function을 알 수 있다면 어떤 action이 가장 좋은 action인지 판단이 가능하기 때문에 policy 선택에 있어 유리하다. 반면 State-value function만을 사용해서는 policy

\pi

를 결정하는 것이 어렵다. 그리고 특정 state에서 가치를 평가할 때 state value function은 하나의 값으로 나오지만, action value function은 모든 action에 대해 고려해야 하므로 연산량이 많다는 단점이 있다.

→

v_\pi(s) = \sum_a\pi(a|s)q_\pi(s,a)

와 같이 Action value function을 활용하여 state-value function을 표현할 수 있다. 이때 현재 state s의 가치는 그 state에서 선택 가능한 모든 action에 대해 고려되어야 하므로 특정 action이 선택될 확률과 그때의 가치들인 q-function을 통해 표현 가능한 것이다.

4. Advantage function

•

Aπ(s,a)=qπ(s,a)−vπ(s)A_\pi(s,a) = q_\pi(s,a)-v_\pi(s)Aπ​(s,a)=qπ​(s,a)−vπ​(s)

→ state s에서 action a에 대한 Advantage function은 두 value function의 차이로 나타내며 action이 현재 state의 가치에 대해 평균 이상의 가치가 있는지, 이하인지를 나타내준다.

5. Dynamic Programming vs RL

•

DP에서는 MDP를 아는 상황(Model-based)이므로 π\piπ와 transition probability P를 알고 있는 상황이다. 따라서 직접 기댓값에 대한 연산이 가능하고 연산량이 적은 state-value function을 주로 사용한다.

•

RL에서는 MDP를 모르는 상황(Model-free)이므로 transition probability를 모르기 때문에, 기댓값 연산을 정확히 수행할 수 없으므로 sample을 통해 추정치를 계산한다.

6. Bellman expectation equation

•

State value function의 다양한 식 표현과 전개 방식

•

Action value function의 다양한 식 표현과 전개 방식

•

Bellman expectation equation 정리

7. Optimal value function and Policy

•

Optimal state-value function

v_*(s) = \displaystyle\max_\pi\ v_\pi (s)

→ 모든 Policy에 대하여 state value function의 값을 최대로 하는 Policy를 적용하였을 때의 State value function

•

Optimal action-value function

q_*(s,a) = \displaystyle \max_\pi\ q_\pi(s,a)

→ 모든 Policy에 대하여 action value function의 값을 최대로 하는 Policy를 적용하였을 때의 Action value function

: 결국 각각은 Optimal policy를 따랐을 때의 value function을 의미한다.

만약 각각의 state의 value를 최대로 하는 policy가 서로 다른 경우에는 policy를 선택할 수 없는 문제가 발생하나, MDP에서는 1) 모든 Policy에 대해서

\pi_*≥ \pi

인 적어도 하나의 Optimal policy가 존재한다 2) Optimal policy를 적용한 state value function은 항상 Optimal state value function과 같다. 3) Optimal policy를 적용한 action value function은 항상 Optimal action value function과 같다.

따라서 Optimal value function은 결국 Optimal policy를 따랐을 때의 value function과 같고 이것은 다른 모든 policy에 대해서 성립하므로 각각의 state 또는 state-action에서 Optimal value function이 서로 다르게 되는 문제는 발생하지 않는다.

•

Optimal Policy

Optimal Policy는

q_*(s,a)

를 최대화 하는 과정에서 찾을 수 있다. 따라서 아래와 같이 정의할 수 있다.

\pi_*(a|s) = \begin{cases} 1 & \text{if } a = \arg\max\limits_a q_*(s, a) \\ 0 & \text{otherwise} \end{cases}

→ 여기서

q_*(s,a)

를 최대로 하는 action을 선택하는 것은 각 state에 대해 action value function이 최대가 되는 action을 단순히 선택한다면 그것은 Optimal Policy가 아닐 수 있다. 따라서 Optimal action value function을 최대로 하는 action을 선택하도록 해야한다. 이때 optimal action value function은 각 state에 대해서 가능한 action의 수만큼 존재하며, 이는 해당 state에서 그 action을 선택하고 이후에 optimal policy를 따를 때의 해당 state-action pair의 value를 나타내는 값이기 때문이다.

→ MDP에서는 항상 deterministic optimal policy가 존재하며, 이는 곧 특정 state에서 선택하는 action이 명확히 하나로 결정된다는 의미이다.

8. Bellman optimality equation

•

Bellman optimality equation 정리