💪🏻

Bellman Equation

생성일

2024/07/11 15:16

최종 수정일

2025/11/11 08:14

태그

강화학습

작성자

1. State-Value Function

•

vπ(s)=Eπ[Gt∣St=s]v_{\pi}(s) = E_{\pi} [G_{t} | S_t = s]vπ​(s)=Eπ​[Gt​∣St​=s]

•

A function representing the value of the current state sss, defined as the expected return when starting from state sss and following policy π\piπ.

2. Transformation using conditional expectation and marginalization

•

Expectation

◦

E(x)=∑xx⋅p(x)E(x) = \sum_x x \cdot p(x)E(x)=∑x​x⋅p(x) 

•

Marginalization

◦

Marginalization is a method for computing the probability density function of a specific variable when the joint probability density function is known.

◦

P(x)=∑yp(x,y)=∑yp(x∣y)⋅p(y)P(x) = \sum_y p(x,y) = \sum_y p(x|y)  \cdot p(y)P(x)=∑y​p(x,y)=∑y​p(x∣y)⋅p(y)

•

Law of Total Probability

◦

 ∪Bi=S,Bi∩Bj=∅\cup B_i = S , B_i \cap B_j = \emptyset∪Bi​=S,Bi​∩Bj​=∅ 

◦

P(A)=∑nP(A∩Bn)=∑nP(A∣Bn)∗P(Bn)P(A) = \sum_{n} P(A \cap B_n) = \sum_n P(A | B_n ) * P(B_n)P(A)=∑n​P(A∩Bn​)=∑n​P(A∣Bn​)∗P(Bn​)

•

Transformation of Expectation

◦

E(x)=∑xx∑yp(x∣y)⋅p(y)=∑yE(X=x∣Y=y)⋅p(y){\small E(x) = \sum_{x} x \sum_{y} p(x | y ) \cdot p(y) = \sum_y E(X=x |Y=y) \cdot p(y)}E(x)=∑x​x∑y​p(x∣y)⋅p(y)=∑y​E(X=x∣Y=y)⋅p(y) 

•

Extension to Conditional Expectation

◦

E(x∣z)=∑xx⋅p(x∣z)E(x|z) = \sum_x  x \cdot p(x | z)E(x∣z)=∑x​x⋅p(x∣z)

◦

E(x∣z)=∑yE(X=x∣Y=y,Z=z)⋅p(y∣z)E(x|z) = \sum_{y} E(X=x | Y=y , Z= z) \cdot p(y|z)E(x∣z)=∑y​E(X=x∣Y=y,Z=z)⋅p(y∣z)

•

Transformation of State Value Function

◦

∑aEπ[Gt∣St=s,At=a]⋅p(a∣s)\sum_a E_{\pi} [G_t | S_t = s, A_t = a ] \cdot p(a | s)∑a​Eπ​[Gt​∣St​=s,At​=a]⋅p(a∣s)

•

Replace each term to action Value Function and Policy

◦

Eπ[Gt∣St=s,At=a]=qπ(s,a), p(a∣s)=π(a∣s)E_{\pi} [G_t | S_t = s, A_t = a ] = q_{\pi} (s,a), \ p(a|s) = \pi(a|s)Eπ​[Gt​∣St​=s,At​=a]=qπ​(s,a), p(a∣s)=π(a∣s) 

◦

∑aπ(a∣s)⋅qπ(s,a)\sum_a \pi(a|s) \cdot q_\pi (s,a)∑a​π(a∣s)⋅qπ​(s,a)

3. Transformation using Reward, Return, Transition Probability

•

Expected reward for state-action pair

◦

Rsa=E[Rt+1∣St=s,At=a]=∑rr∑s′p(s′,r∣s,a)R^a_s = E[R_{t+1} | S_t = s, A_t= a] = \sum_r r \sum_{s'} p(s',r |s,a)Rsa​=E[Rt+1​∣St​=s,At​=a]=∑r​r∑s′​p(s′,r∣s,a)

•

Transition Probability

◦

Pss’a=∑rp(s′,r∣s,a)P^a_{ss’} = \sum_{r} p(s',r |s,a)Pss’a​=∑r​p(s′,r∣s,a)

•

Return

◦

Gt=Rt+1+γRt+2+⋅⋅⋅G_t = R_{t+1} + \gamma R_{t+2} + \cdot \cdot \cdotGt​=Rt+1​+γRt+2​+⋅⋅⋅

•

Express Action Value Function using Return

◦

Eπ[Gt∣St=s,At=a]=E[Rt+1+γGt+1∣St=s,At=a]E_{\pi} [G_t | S_t = s, A_t = a ] =  E[R_{t+1} +\gamma G_{t+1} | S_t = s, A_t = a]Eπ​[Gt​∣St​=s,At​=a]=E[Rt+1​+γGt+1​∣St​=s,At​=a]

•

Transformation using the action-value function expressed through marginalization and return

◦

∑aπ(a∣s)⋅∑s′,rEπ[Rt+1+γGt+1∣St=s,At=a,St+1=s′,Rt+1=r]⋅P(St+1=s′,Rt+1=r∣St=s,At=a){\small \sum_{a} \pi(a \mid s) \cdot \sum_{s',r} \mathbb{E}_\pi \left[ R_{t+1} + \gamma G_{t+1} \mid S_t = s, A_t = a, S_{t+1} = s', R_{t+1} = r \right] \cdot P\left(S_{t+1} = s', R_{t+1} = r \mid S_t = s, A_t = a \right)}∑a​π(a∣s)⋅∑s′,r​Eπ​[Rt+1​+γGt+1​∣St​=s,At​=a,St+1​=s′,Rt+1​=r]⋅P(St+1​=s′,Rt+1​=r∣St​=s,At​=a)

1.By the additivity of expectation and

2.By the Markov property,

the state-value function can be expressed as follows.

◦

 ∑aπ(a∣s)⋅∑s′,rp(s′,r∣s,a)⋅[r+γEπ[Gt+1∣St+1=s′]]\sum_{a} \pi(a \mid s) \cdot \sum_{s',r} p(s', r \mid s, a) \cdot \left[ r + \gamma \mathbb{E}_\pi \left[G_{t+1} \mid S_{t+1} = s'\right] \right]∑a​π(a∣s)⋅∑s′,r​p(s′,r∣s,a)⋅[r+γEπ​[Gt+1​∣St+1​=s′]]

3. Distribute

p(s', r | s, a)

◦

∑rr∑s′p(s′,r∣s,a)+γ∑s′,rp(s′,r∣s,a)Eπ[Gt+1∣St+1=s′]\sum_r r \sum_{s'} p(s', r | s,a) + \gamma \sum_{s',r} p(s', r | s,a) E_\pi [G_{t+1} | S_{t+1} = s']∑r​r∑s′​p(s′,r∣s,a)+γ∑s′,r​p(s′,r∣s,a)Eπ​[Gt+1​∣St+1​=s′]   

Replace with 1. Expected reward for state-action pair 2. Transition Probability

◦

∑aπ(a∣s)[Rsa+γ∑s′Pss′aVπ(s′)]\sum_{a} \pi(a \mid s) \left[ R_s^a + \gamma \sum_{s'} P_{s s'}^a V_\pi(s') \right]∑a​π(a∣s)[Rsa​+γ∑s′​Pss′a​Vπ​(s′)]

•

Expressed in terms of conditional expectation.

◦

Eπ[Rt+1+γVπ(St+1)∣St=s]\mathbb{E}_\pi \left[ R_{t+1} + \gamma V_\pi(S_{t+1}) \mid S_t = s \right]Eπ​[Rt+1​+γVπ​(St+1​)∣St​=s]

4. 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]

•

It is expressed as the expected return when taking action aaa in the current state sss and following policy π\piπ

•

Transformation using marginalization and expectation

◦

∑s′,rEπ[Rt+1+γGt+1∣St=s,At=a,St+1=s′,Rt+1=r]p(St+1=s′,Rt+1=r∣St=s,At=a){\small \sum_{s', r} \mathbb{E}_\pi \left[ R_{t+1} + \gamma G_{t+1} \mid S_t = s, A_t = a, S_{t+1} = s', R_{t+1} = r \right] p(S_{t+1} = s', R_{t+1} = r \mid S_t = s, A_t = a)}∑s′,r​Eπ​[Rt+1​+γGt+1​∣St​=s,At​=a,St+1​=s′,Rt+1​=r]p(St+1​=s′,Rt+1​=r∣St​=s,At​=a)

여기서 Markov Property에 의해,

S_t = s, A_t = a

조건은 식에 영향을 주지 않으므로 삭제가 가능하다. 더하여 기댓값의 가법성에 의해 식을 전개하면 아래와 같다.

◦

∑s′,rp(s′,r∣s,a)[r+γEπ[Gt+1∣St+1=s′]]\sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma \mathbb{E}_\pi \left[ G_{t+1} \mid S_{t+1} = s' \right] \right]∑s′,r​p(s′,r∣s,a)[r+γEπ​[Gt+1​∣St+1​=s′]]

위 식의 기댓값 파트를 다시 마진화를 사용하여 표현하면 아래와 같다.

◦

∑s′,rp(s′,r∣s,a)[r+γ∑a′Eπ[Gt+1∣St+1=s′,At+1=a′]p(At+1=a′∣St+1=s′)]\sum_{s', r} p(s', r | s, a) \left[ r + \gamma \sum_{a'} \mathbb{E}_\pi \left[ G_{t+1} \mid S_{t+1} = s', A_{t+1} = a' \right] p(A_{t+1} = a' \mid S_{t+1} = s') \right]∑s′,r​p(s′,r∣s,a)[r+γ∑a′​Eπ​[Gt+1​∣St+1​=s′,At+1​=a′]p(At+1​=a′∣St+1​=s′)]

Policy와 Action Value Function의 정의를 사용하여 식을 다시 표현하면 아래와 같다.

◦

∑s′,rp(s′,r∣s,a)[r+γ∑a′π(a′∣s′)qπ(s′,a′)]\sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma \sum_{a'} \pi(a' \mid s') q_\pi(s', a') \right]∑s′,r​p(s′,r∣s,a)[r+γ∑a′​π(a′∣s′)qπ​(s′,a′)]

그리고 이것은 기댓값의 정의에 의해 간략하게 표현할 수 있다.

◦

Eπ[Rt+1+γqπ(St+1,At+1)∣St=s,At=a]\mathbb{E}_\pi \left[ R_{t+1} + \gamma q_\pi(S_{t+1}, A_{t+1}) \mid S_t = s, A_t = a \right]Eπ​[Rt+1​+γqπ​(St+1​,At+1​)∣St​=s,At​=a]

Bellman Optimality Equation

Optimal Value Function/Optimal Policy

정의

•

v∗(s)=max⁡π vπ(s)v_*(s) = \displaystyle\max_\pi\ v_\pi (s)v∗​(s)=πmax​ vπ​(s)

모든 Policy에 대하여 State Value Function의 값을 최대로 하는 Policy를 적용하였을 때의 State Value Function

•

q∗(s)=max⁡π qπ(s)q_*(s) = \displaystyle\max_\pi\ q_\pi (s)q∗​(s)=πmax​ qπ​(s)

모든 Policy에 대하여 Action Value Function의 값을 최대로 하는 Policy를 적용하였을 때의 Action Value Function

•

π(a∣s)={1if a=arg⁡max⁡aq∗(s,a)0otherwise\pi_(a|s) = \begin{cases}
1 & \text{if } a = \arg\max\limits_a q_*(s, a) \\
0 & \text{otherwise}
\end{cases}π(​a∣s)={10​if a=argamax​q∗​(s,a)otherwise​

→

q_∗(s,a)

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

Optimal Value Function의 변형

•

Optimal State Value Function의 정의로 표현

◦

v∗(s)=max⁡aEπ[Gt∣St=s,At=a]v_*(s) = \max_a \mathbb{E}_\pi \left[ G_t \mid S_t = s, A_t = a \right]v∗​(s)=maxa​Eπ​[Gt​∣St​=s,At​=a]

•

Return/Expected Reward/Transition Probability를 활용한 변형

◦

max⁡aEπ∗[Rt+1+γGt+1∣St=s,At=a]\max_a \mathbb{E}_{\pi*} \left[ R_{t+1} + \gamma G_{t+1} \mid S_t = s, A_t = a \right]maxa​Eπ∗​[Rt+1​+γGt+1​∣St​=s,At​=a]

여기서 Optimal Policy를 적용하면 이는 Optimal Policy를 적용했을 때 앞으로 받을 Return의 기댓값이 되므로 Optimal State Value Function으로 변환 가능하다.

◦

max⁡aE[Rt+1+γv∗(St+1)∣St=s,At=a]\max_a \mathbb{E} \left[ R_{t+1} + \gamma v_*(S_{t+1}) \mid S_t = s, A_t = a \right]maxa​E[Rt+1​+γv∗​(St+1​)∣St​=s,At​=a]

위 수식을 기댓값의 정의에 의해 풀면 아래와 같다.

◦

max⁡a∑s′,rp(s′,r∣s,a)[r+γv∗(s′)]\max_a \sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma v_*(s') \right]maxa​∑s′,r​p(s′,r∣s,a)[r+γv∗​(s′)]

•

Expected reward for state-action pair

◦

Rsa=E[Rt+1∣St=s,At=a]=∑rr∑s′p(s′,r∣s,a)R^a_s = E[R_{t+1} | S_t = s, A_t= a] = \sum_r r \sum_{s'} p(s',r |s,a)Rsa​=E[Rt+1​∣St​=s,At​=a]=∑r​r∑s′​p(s′,r∣s,a)

•

Transition Probability

◦

Pss’a=∑rp(s′,r∣s,a)P^a_{ss’} = \sum_{r} p(s',r |s,a)Pss’a​=∑r​p(s′,r∣s,a)

를 사용하여 식을 정리하면 아래와 같다.

◦

max⁡a[Rsa+γ∑s′pss′aV∗(s′)]\max_a [R_s^a + \gamma \sum_{s'} p_{s s'}^a V_*(s')]maxa​[Rsa​+γ∑s′​pss′a​V∗​(s′)]

•

Optimal Action Value Function의 정의로 표현

◦

q∗(s,a)=E[Rt+1+γmax⁡a′q∗(St+1,a′)∣St=s,At=a]q_*(s, a) = \mathbb{E} \left[ R_{t+1} + \gamma \max_{a'} q_*(S_{t+1}, a') \mid S_t = s, A_t = a \right]q∗​(s,a)=E[Rt+1​+γmaxa′​q∗​(St+1​,a′)∣St​=s,At​=a]

•

기댓값의 정의를 활용해 변형

◦

∑s′,rP(s′,r∣s,a)[r+γmax⁡a′q∗(s′,a′)]\sum_{s', r} P(s', r \mid s, a) \left[ r + \gamma \max_{a'} q_*(s', a') \right]∑s′,r​P(s′,r∣s,a)[r+γmaxa′​q∗​(s′,a′)]

•

Expected Reward/Transition Probability를 활용한 변형

◦

Rsa+γ∑s′Pss′amax⁡a′q∗(s′,a′)=Rsa+γ∑s′P(s′∣s,a)v∗(s′)R_s^a + \gamma \sum_{s'} P_{s s'}^a \max_{a'} q_*(s', a') = R_s^a + \gamma \sum_{s'} P(s' \mid s, a) v_*(s')Rsa​+γ∑s′​Pss′a​maxa′​q∗​(s′,a′)=Rsa​+γ∑s′​P(s′∣s,a)v∗​(s′)