Bellman equation derivation - Revision history

IssaRice: /* Law of total probability */

2019-09-01T04:03:45Z

Law of total probability

← Older revision		Revision as of 04:03, 1 September 2019
Line 9:		Line 9:
	The law of total probability states that if <math>B</math> is an event, and <math>C_1, \ldots, C_n</math> are events that partition the sample space, then <math display="inline">\Pr(B) = \sum_{j=1}^n \Pr(B \cap C_j) = \sum_{j=1}^n \Pr(B \mid C_j)\Pr(C_j)</math>.		The law of total probability states that if <math>B</math> is an event, and <math>C_1, \ldots, C_n</math> are events that partition the sample space, then <math display="inline">\Pr(B) = \sum_{j=1}^n \Pr(B \cap C_j) = \sum_{j=1}^n \Pr(B \mid C_j)\Pr(C_j)</math>.

	For fixed event <math>A</math> with non-zero probability, the mapping <math>B \mapsto \Pr(B \mid A)</math> is another valid probability measure. ~~In other words, define~~ <math display="inline">\Pr_A</math> by <math display="inline">\Pr_A(B) := \Pr(B \mid A)</math> for all events <math>B</math>. Now the law of total probability for <math display="inline">\Pr_A</math> states that <math display="inline">\Pr_A(B) = \sum_{j=1}^n \Pr_A(B \mid C_j)\Pr_A(C_j)</math>. We also have		For fixed event <math>A</math> with non-zero probability, the mapping <math>B \mapsto \Pr(B \mid A)</math> is another valid probability measure, so the law of total probability also applies to it. Define <math display="inline">\Pr_A</math> by <math display="inline">\Pr_A(B) := \Pr(B \mid A)</math> for all events <math>B</math>. Now the law of total probability for <math display="inline">\Pr_A</math> states that <math display="inline">\Pr_A(B) = \sum_{j=1}^n \Pr_A(B \mid C_j)\Pr_A(C_j)</math>. We also have

	:<math>\Pr_A(B \mid C_j) = \frac{\Pr_A(B \cap C_j)}{\Pr_A(C_j)} = \frac{\Pr(B\cap C_j \mid A)}{\Pr(C_j\mid A)} = \frac{\Pr(B \cap C_j \cap A)/\Pr(A)}{\Pr(C_j \cap A)/\Pr(A)} = \frac{\Pr(B\cap (C_j\cap A))}{\Pr(C_j \cap A)} = \Pr(B \mid C_j,A)</math>		:<math>\Pr_A(B \mid C_j) = \frac{\Pr_A(B \cap C_j)}{\Pr_A(C_j)} = \frac{\Pr(B\cap C_j \mid A)}{\Pr(C_j\mid A)} = \frac{\Pr(B \cap C_j \cap A)/\Pr(A)}{\Pr(C_j \cap A)/\Pr(A)} = \frac{\Pr(B\cap (C_j\cap A))}{\Pr(C_j \cap A)} = \Pr(B \mid C_j,A)</math>

IssaRice: /* Law of total probability */

2019-09-01T04:01:08Z

Law of total probability

← Older revision		Revision as of 04:01, 1 September 2019
Line 9:		Line 9:
	The law of total probability states that if <math>B</math> is an event, and <math>C_1, \ldots, C_n</math> are events that partition the sample space, then <math display="inline">\Pr(B) = \sum_{j=1}^n \Pr(B \cap C_j) = \sum_{j=1}^n \Pr(B \mid C_j)\Pr(C_j)</math>.		The law of total probability states that if <math>B</math> is an event, and <math>C_1, \ldots, C_n</math> are events that partition the sample space, then <math display="inline">\Pr(B) = \sum_{j=1}^n \Pr(B \cap C_j) = \sum_{j=1}^n \Pr(B \mid C_j)\Pr(C_j)</math>.

	For fixed event <math>A</math> with non-zero probability, the mapping <math>B \mapsto \Pr(B \mid A)</math> is another valid probability measure. In other words, define <math>\Pr_A</math> by <math>\Pr_A(B) := \Pr(B \mid A)</math> for all events <math>B</math>. Now the law of total probability for <math>~~P_A~~</math> states that <math display="inline">\Pr_A(B) = \sum_{j=1}^n \Pr_A(B \mid C_j)\Pr_A(C_j)</math>. We also have		For fixed event <math>A</math> with non-zero probability, the mapping <math>B \mapsto \Pr(B \mid A)</math> is another valid probability measure. In other words, define <math display="inline">\Pr_A</math> by <math display="inline">\Pr_A(B) := \Pr(B \mid A)</math> for all events <math>B</math>. Now the law of total probability for <math display="inline">\Pr_A</math> states that <math display="inline">\Pr_A(B) = \sum_{j=1}^n \Pr_A(B \mid C_j)\Pr_A(C_j)</math>. We also have

	:<math>\Pr_A(B \mid C_j) = \frac{\Pr_A(B \cap C_j)}{\Pr_A(C_j)} = \frac{\Pr(B\cap C_j \mid A)}{\Pr(C_j\mid A)} = \frac{\Pr(B \cap C_j \cap A)/\Pr(A)}{\Pr(C_j \cap A)/\Pr(A)} = \frac{\Pr(B\cap (C_j\cap A))}{\Pr(C_j \cap A)} = \Pr(B \mid C_j,A)</math>		:<math>\Pr_A(B \mid C_j) = \frac{\Pr_A(B \cap C_j)}{\Pr_A(C_j)} = \frac{\Pr(B\cap C_j \mid A)}{\Pr(C_j\mid A)} = \frac{\Pr(B \cap C_j \cap A)/\Pr(A)}{\Pr(C_j \cap A)/\Pr(A)} = \frac{\Pr(B\cap (C_j\cap A))}{\Pr(C_j \cap A)} = \Pr(B \mid C_j,A)</math>

IssaRice at 03:56, 1 September 2019

2019-09-01T03:56:10Z

← Older revision		Revision as of 03:56, 1 September 2019
Line 4:		Line 4:

	The core idea of the proof is to use the law of total probability to go from marginal to conditional probabilities, and then invoke the Markov assumption.		The core idea of the proof is to use the law of total probability to go from marginal to conditional probabilities, and then invoke the Markov assumption.

			==Law of total probability==

	The law of total probability states that if <math>B</math> is an event, and <math>C_1, \ldots, C_n</math> are events that partition the sample space, then <math display="inline">\Pr(B) = \sum_{j=1}^n \Pr(B \cap C_j) = \sum_{j=1}^n \Pr(B \mid C_j)\Pr(C_j)</math>.		The law of total probability states that if <math>B</math> is an event, and <math>C_1, \ldots, C_n</math> are events that partition the sample space, then <math display="inline">\Pr(B) = \sum_{j=1}^n \Pr(B \cap C_j) = \sum_{j=1}^n \Pr(B \mid C_j)\Pr(C_j)</math>.
Line 20:		Line 22:

	This is the basic trick of the proof; we keep conditioning on different things (actions, next states, rewards) and using the law of total probability.		This is the basic trick of the proof; we keep conditioning on different things (actions, next states, rewards) and using the law of total probability.

			==Start of proof==

	By definition, <math>v_\pi(s) = \mathbb E_\pi[G_t \mid S_t = s]</math>. Now rewrite <math>G_t = R_{t+1} + \gamma G_{t+1}</math> and use the linearity of expectation to get <math>\mathbb E_\pi[R_{t+1} \mid S_t=s] + \gamma\mathbb E_\pi[G_{t+1}\mid S_t = s]</math>. From here, we can work separately with <math>\mathbb E_\pi[R_{t+1} \mid S_t=s]</math> and <math>\mathbb E_\pi[G_{t+1}\mid S_t = s]</math> for a while.		By definition, <math>v_\pi(s) = \mathbb E_\pi[G_t \mid S_t = s]</math>. Now rewrite <math>G_t = R_{t+1} + \gamma G_{t+1}</math> and use the linearity of expectation to get <math>\mathbb E_\pi[R_{t+1} \mid S_t=s] + \gamma\mathbb E_\pi[G_{t+1}\mid S_t = s]</math>. From here, we can work separately with <math>\mathbb E_\pi[R_{t+1} \mid S_t=s]</math> and <math>\mathbb E_\pi[G_{t+1}\mid S_t = s]</math> for a while.

			==Simplifying expectation for reward term==

	Using the law of total probability while conditioning over actions, we have		Using the law of total probability while conditioning over actions, we have
Line 50:		Line 56:

	:<math>\mathbb E_\pi[R_{t+1} \mid S_t=s] = \sum_a \pi(a\mid s) \sum_{s',r} p(s',r \mid s,a) r</math>		:<math>\mathbb E_\pi[R_{t+1} \mid S_t=s] = \sum_a \pi(a\mid s) \sum_{s',r} p(s',r \mid s,a) r</math>

			==Simplifying expression for return term==

	Now we do a similar series of steps for <math>\mathbb E_\pi[G_{t+1}\mid S_t = s]</math>. Conditioning over actions,		Now we do a similar series of steps for <math>\mathbb E_\pi[G_{t+1}\mid S_t = s]</math>. Conditioning over actions,
Line 67:		Line 75:
	:<math>\sum_a \pi(a \mid s) \sum_{s',r} p(s',r\mid s,a) \sum_g g \Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>		:<math>\sum_a \pi(a \mid s) \sum_{s',r} p(s',r\mid s,a) \sum_g g \Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>

	This is basically what we want, except we want to say that <math>\sum_g g \Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \mathbb E_\pi[G_{t+1} \mid S_{t+1}=s']</math>, since the latter expression equals <math>v_\pi(s')</math>. Thankfully, we can say this, because of the Markov assumption. Actually proving this is a little complicated; see ~~[https://math.stackexchange.com/questions/3143290/writing-action-value-function-in-terms-of-state-value-function-for-a-markov-deci this question] for some details. I think~~ the following works: It suffices to show <math>\Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \Pr(G_{t+1} = g \mid S_{t+1}=s')</math>. Conditioning over actions in the <math>t+1</math> timestep, we have <math>\sum_{a'} \Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)\Pr(A_{t+1}=a' \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>. But the action is chosen by the policy, which depends only on the state, so <math>\Pr(A_{t+1}=a' \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \pi(a' \mid s')</math>. As for <math>\Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>, recall that <math>G_{t+1} = R_{t+2} + R_{t+3} + \cdots</math> so has only rewards starting on timestep <math>t+2</math>. Since we are working with an MDP, the environment's dynamics are completely determined by the state and action on timestep <math>t+1</math>, i.e. on <math>s'</math> and <math>a'</math> (NOTE: Sutton and Barto's text seems to have a small error here, where they describe the Markovian property as "That is, the ~~probability~~ of each possible value for <math>S_t</math> and <math>R_t</math> depends only on the immediately preceding state and action, <math>S_{t-1}</math> and <math>A_{t-1}</math>, and, given them, not at all on earlier states and actions." -- the last part should probably say "not at all on earlier states, actions, and rewards". Otherwise I'm not sure how to prove that we can ignore the conditioning on <math>R_{t+1}=r</math>). So this is equal to <math>\Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s')</math>. Thus we have <math>\sum_{a'} \Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s')\pi(a'\mid s')</math>. Now we can reverse the conditionalization, i.e. we marginalize to obtain <math>\Pr(G_{t+1} = g \mid S_{t+1}=s')</math>.		This is basically what we want, except we want to say that <math>\sum_g g \Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \mathbb E_\pi[G_{t+1} \mid S_{t+1}=s']</math>, since the latter expression equals <math>v_\pi(s')</math>. Thankfully, we can say this, because of the Markov assumption. Actually proving this is a little complicated; see the section at the end of this page.

	So we end up with		So we end up with

	:<math>\sum_a \pi(a \mid s) \sum_{s',r} p(s',r\mid s,a) v_\pi(s')</math>		:<math>\sum_a \pi(a \mid s) \sum_{s',r} p(s',r\mid s,a) v_\pi(s')</math>

			==Finishing the proof==

	So now we have		So now we have
Line 78:		Line 88:

	This completes the proof. I'm pretty confused why Sutton and Barto seem to think abbreviating all these steps without comment is a good idea.		This completes the proof. I'm pretty confused why Sutton and Barto seem to think abbreviating all these steps without comment is a good idea.

			==Using the Markov assumption==

			I think the following works: It suffices to show <math>\Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \Pr(G_{t+1} = g \mid S_{t+1}=s')</math>. Conditioning over actions in the <math>t+1</math> timestep, we have <math>\sum_{a'} \Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)\Pr(A_{t+1}=a' \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>. But the action is chosen by the policy, which depends only on the state, so <math>\Pr(A_{t+1}=a' \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \pi(a' \mid s')</math>. As for <math>\Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>, recall that <math>G_{t+1} = R_{t+2} + R_{t+3} + \cdots</math> so has only rewards starting on timestep <math>t+2</math>. Since we are working with an MDP, the environment's dynamics are completely determined by the state and action on timestep <math>t+1</math>, i.e. on <math>s'</math> and <math>a'</math> (NOTE: Sutton and Barto's text seems to have a small error here, where they describe the Markovian property as "That is, the probability of each possible value for <math>S_t</math> and <math>R_t</math> depends only on the immediately preceding state and action, <math>S_{t-1}</math> and <math>A_{t-1}</math>, and, given them, not at all on earlier states and actions." -- the last part should probably say "not at all on earlier states, actions, and rewards". Otherwise I'm not sure how to prove that we can ignore the conditioning on <math>R_{t+1}=r</math>). So this is equal to <math>\Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s')</math>. Thus we have <math>\sum_{a'} \Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s')\pi(a'\mid s')</math>. Now we can reverse the conditionalization, i.e. we marginalize to obtain <math>\Pr(G_{t+1} = g \mid S_{t+1}=s')</math>.

			See [https://math.stackexchange.com/questions/3143290/writing-action-value-function-in-terms-of-state-value-function-for-a-markov-deci this question] for a similar manipulation.

IssaRice at 03:41, 1 September 2019

2019-09-01T03:41:36Z

← Older revision		Revision as of 03:41, 1 September 2019
Line 67:		Line 67:
	:<math>\sum_a \pi(a \mid s) \sum_{s',r} p(s',r\mid s,a) \sum_g g \Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>		:<math>\sum_a \pi(a \mid s) \sum_{s',r} p(s',r\mid s,a) \sum_g g \Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>

	This is basically what we want, except we want to say that <math>\sum_g g \Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \mathbb E_\pi[G_{t+1} \mid S_{t+1}=s']</math>, since the latter expression equals <math>v_\pi(s')</math>. Thankfully, we can say this, because of the Markov assumption. Actually proving this is a little complicated; see [https://math.stackexchange.com/questions/3143290/writing-action-value-function-in-terms-of-state-value-function-for-a-markov-deci this question] for some details. I think the following works: It suffices to show <math>\Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \Pr(G_{t+1} = g \mid S_{t+1}=s')</math>. Conditioning over actions in the <math>t+1</math> timestep, we have <math>\sum_{a'} \Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)\Pr(A_{t+1}=a' \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>. But the action is chosen by the policy, which depends only on the state, so <math>\Pr(A_{t+1}=a' \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \pi(a' \mid s')</math>. As for <math>\Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>, recall that <math>G_{t+1} = R_{t+2} + R_{t+3} + \cdots</math> so has only rewards starting on timestep <math>t+2</math>. Since we are working with an MDP, the environment's dynamics are completely determined by the state and action on timestep <math>t+1</math>, i.e. on <math>s'</math> and <math>a'</math>. So this is equal to <math>\Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s')</math>. Thus we have <math>\sum_{a'} \Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s')\pi(a'\mid s')</math>. Now we can reverse the conditionalization, i.e. we marginalize to obtain <math>\Pr(G_{t+1} = g \mid S_{t+1}=s')</math>.		This is basically what we want, except we want to say that <math>\sum_g g \Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \mathbb E_\pi[G_{t+1} \mid S_{t+1}=s']</math>, since the latter expression equals <math>v_\pi(s')</math>. Thankfully, we can say this, because of the Markov assumption. Actually proving this is a little complicated; see [https://math.stackexchange.com/questions/3143290/writing-action-value-function-in-terms-of-state-value-function-for-a-markov-deci this question] for some details. I think the following works: It suffices to show <math>\Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \Pr(G_{t+1} = g \mid S_{t+1}=s')</math>. Conditioning over actions in the <math>t+1</math> timestep, we have <math>\sum_{a'} \Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)\Pr(A_{t+1}=a' \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>. But the action is chosen by the policy, which depends only on the state, so <math>\Pr(A_{t+1}=a' \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \pi(a' \mid s')</math>. As for <math>\Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>, recall that <math>G_{t+1} = R_{t+2} + R_{t+3} + \cdots</math> so has only rewards starting on timestep <math>t+2</math>. Since we are working with an MDP, the environment's dynamics are completely determined by the state and action on timestep <math>t+1</math>, i.e. on <math>s'</math> and <math>a'</math> (NOTE: Sutton and Barto's text seems to have a small error here, where they describe the Markovian property as "That is, the probability of each possible value for <math>S_t</math> and <math>R_t</math> depends only on the immediately preceding state and action, <math>S_{t-1}</math> and <math>A_{t-1}</math>, and, given them, not at all on earlier states and actions." -- the last part should probably say "not at all on earlier states, actions, and rewards". Otherwise I'm not sure how to prove that we can ignore the conditioning on <math>R_{t+1}=r</math>). So this is equal to <math>\Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s')</math>. Thus we have <math>\sum_{a'} \Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s')\pi(a'\mid s')</math>. Now we can reverse the conditionalization, i.e. we marginalize to obtain <math>\Pr(G_{t+1} = g \mid S_{t+1}=s')</math>.

	So we end up with		So we end up with

IssaRice at 03:38, 1 September 2019

2019-09-01T03:38:25Z

← Older revision		Revision as of 03:38, 1 September 2019
Line 67:		Line 67:
	:<math>\sum_a \pi(a \mid s) \sum_{s',r} p(s',r\mid s,a) \sum_g g \Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>		:<math>\sum_a \pi(a \mid s) \sum_{s',r} p(s',r\mid s,a) \sum_g g \Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>

	This is basically what we want, except we want to say that <math>\sum_g g \Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \mathbb E_\pi[G_{t+1} \mid S_{t+1}=s']</math>, since the latter expression equals <math>v_\pi(s')</math>. Thankfully, we can say this, because of the Markov assumption. Actually proving this is a little complicated; see [https://math.stackexchange.com/questions/3143290/writing-action-value-function-in-terms-of-state-value-function-for-a-markov-deci this question] for some details. I think the following works: It suffices to show <math>\Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \Pr(G_{t+1} = g \mid S_{t+1}=s')</math>. Conditioning over actions in the <math>t+1</math> timestep, we have <math>~~\Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) =~~\sum_{a'} \Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)\Pr(A_{t+1}=a' \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>. But the action is chosen by the policy, which depends only on the state, so <math>\Pr(A_{t+1}=a' \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \pi(a' \mid s')</math>. As for <math>\Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>, recall that <math>G_{t+1} = R_{t+2} + R_{t+3} + \cdots</math> so has only rewards starting on timestep <math>t+2</math>. Since we are working with an MDP, the environment's dynamics are completely determined by the state and action on timestep <math>t+1</math>, i.e. on <math>s'</math> and <math>a'</math>. So this is equal to <math>\Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s')</math>. Thus we have <math>\sum_{a'} \Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s')\pi(a'\mid s')</math>. Now we can reverse the conditionalization, i.e. we marginalize to obtain <math>\Pr(G_{t+1} = g \mid S_{t+1}=s')</math>.		This is basically what we want, except we want to say that <math>\sum_g g \Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \mathbb E_\pi[G_{t+1} \mid S_{t+1}=s']</math>, since the latter expression equals <math>v_\pi(s')</math>. Thankfully, we can say this, because of the Markov assumption. Actually proving this is a little complicated; see [https://math.stackexchange.com/questions/3143290/writing-action-value-function-in-terms-of-state-value-function-for-a-markov-deci this question] for some details. I think the following works: It suffices to show <math>\Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \Pr(G_{t+1} = g \mid S_{t+1}=s')</math>. Conditioning over actions in the <math>t+1</math> timestep, we have <math>\sum_{a'} \Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)\Pr(A_{t+1}=a' \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>. But the action is chosen by the policy, which depends only on the state, so <math>\Pr(A_{t+1}=a' \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \pi(a' \mid s')</math>. As for <math>\Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>, recall that <math>G_{t+1} = R_{t+2} + R_{t+3} + \cdots</math> so has only rewards starting on timestep <math>t+2</math>. Since we are working with an MDP, the environment's dynamics are completely determined by the state and action on timestep <math>t+1</math>, i.e. on <math>s'</math> and <math>a'</math>. So this is equal to <math>\Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s')</math>. Thus we have <math>\sum_{a'} \Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s')\pi(a'\mid s')</math>. Now we can reverse the conditionalization, i.e. we marginalize to obtain <math>\Pr(G_{t+1} = g \mid S_{t+1}=s')</math>.

	So we end up with		So we end up with

IssaRice at 03:37, 1 September 2019

2019-09-01T03:37:28Z

← Older revision		Revision as of 03:37, 1 September 2019
Line 67:		Line 67:
	:<math>\sum_a \pi(a \mid s) \sum_{s',r} p(s',r\mid s,a) \sum_g g \Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>		:<math>\sum_a \pi(a \mid s) \sum_{s',r} p(s',r\mid s,a) \sum_g g \Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>

	This is basically what we want, except we want to say that <math>\sum_g g \Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \mathbb E_\pi[G_{t+1} \mid S_{t+1}=s']</math>, since the latter expression equals <math>v_\pi(s')</math>. Thankfully, we can say this, because of the Markov assumption. Actually proving this is a little complicated; see [https://math.stackexchange.com/questions/3143290/writing-action-value-function-in-terms-of-state-value-function-for-a-markov-deci this question] for some details.		This is basically what we want, except we want to say that <math>\sum_g g \Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \mathbb E_\pi[G_{t+1} \mid S_{t+1}=s']</math>, since the latter expression equals <math>v_\pi(s')</math>. Thankfully, we can say this, because of the Markov assumption. Actually proving this is a little complicated; see [https://math.stackexchange.com/questions/3143290/writing-action-value-function-in-terms-of-state-value-function-for-a-markov-deci this question] for some details. I think the following works: It suffices to show <math>\Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \Pr(G_{t+1} = g \mid S_{t+1}=s')</math>. Conditioning over actions in the <math>t+1</math> timestep, we have <math>\Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) =\sum_{a'} \Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)\Pr(A_{t+1}=a' \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>. But the action is chosen by the policy, which depends only on the state, so <math>\Pr(A_{t+1}=a' \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \pi(a' \mid s')</math>. As for <math>\Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>, recall that <math>G_{t+1} = R_{t+2} + R_{t+3} + \cdots</math> so has only rewards starting on timestep <math>t+2</math>. Since we are working with an MDP, the environment's dynamics are completely determined by the state and action on timestep <math>t+1</math>, i.e. on <math>s'</math> and <math>a'</math>. So this is equal to <math>\Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s')</math>. Thus we have <math>\sum_{a'} \Pr(G_{t+1} = g \mid A_{t+1}=a', S_{t+1}=s')\pi(a'\mid s')</math>. Now we can reverse the conditionalization, i.e. we marginalize to obtain <math>\Pr(G_{t+1} = g \mid S_{t+1}=s')</math>.

	So we end up with		So we end up with

IssaRice at 02:09, 1 September 2019

2019-09-01T02:09:34Z

← Older revision		Revision as of 02:09, 1 September 2019
Line 75:		Line 75:
	So now we have		So now we have

	<math>\begin{align}v_\pi(s) &= \sum_a \pi(a\mid s) \sum_{s',r} p(s',r \mid s,a) r + \gamma \sum_a \pi(a \mid s) \sum_{s',r} p(s',r\mid s,a) v_\pi(s') \\ &= \sum_a \pi(a\mid s) \sum_{s',r} p(s',r \mid s,a) [r + \gamma v_\pi(s')]\end{align}</math>		:<math>\begin{align}v_\pi(s) &= \sum_a \pi(a\mid s) \sum_{s',r} p(s',r \mid s,a) r + \gamma \sum_a \pi(a \mid s) \sum_{s',r} p(s',r\mid s,a) v_\pi(s') \\ &= \sum_a \pi(a\mid s) \sum_{s',r} p(s',r \mid s,a) [r + \gamma v_\pi(s')]\end{align}</math>

			This completes the proof. I'm pretty confused why Sutton and Barto seem to think abbreviating all these steps without comment is a good idea.

IssaRice at 02:08, 1 September 2019

2019-09-01T02:08:51Z

← Older revision		Revision as of 02:08, 1 September 2019
Line 75:		Line 75:
	So now we have		So now we have

	<math>\begin{align}~~v_pi~~(s) &= \sum_a \pi(a\mid s) \sum_{s',r} p(s',r \mid s,a) r + \gamma \sum_a \pi(a \mid s) \sum_{s',r} p(s',r\mid s,a) v_\pi(s') \\ &= \sum_a \pi(a\mid s) \sum_{s',r} p(s',r \mid s,a) [r + \gamma v_\pi(s')]\end{align}</math>		<math>\begin{align}v_\pi(s) &= \sum_a \pi(a\mid s) \sum_{s',r} p(s',r \mid s,a) r + \gamma \sum_a \pi(a \mid s) \sum_{s',r} p(s',r\mid s,a) v_\pi(s') \\ &= \sum_a \pi(a\mid s) \sum_{s',r} p(s',r \mid s,a) [r + \gamma v_\pi(s')]\end{align}</math>

IssaRice at 02:08, 1 September 2019

2019-09-01T02:08:22Z

← Older revision		Revision as of 02:08, 1 September 2019
Line 75:		Line 75:
	So now we have		So now we have

	<math>v_pi(s) = \sum_a \pi(a\mid s) \sum_{s',r} p(s',r \mid s,a) r + \gamma \sum_a \pi(a \mid s) \sum_{s',r} p(s',r\mid s,a) v_\pi(s')</math>		<math>\begin{align}v_pi(s) &= \sum_a \pi(a\mid s) \sum_{s',r} p(s',r \mid s,a) r + \gamma \sum_a \pi(a \mid s) \sum_{s',r} p(s',r\mid s,a) v_\pi(s') \\ &= \sum_a \pi(a\mid s) \sum_{s',r} p(s',r \mid s,a) [r + \gamma v_\pi(s')]\end{align}</math>

IssaRice at 02:07, 1 September 2019

2019-09-01T02:07:26Z

← Older revision		Revision as of 02:07, 1 September 2019
Line 67:		Line 67:
	:<math>\sum_a \pi(a \mid s) \sum_{s',r} p(s',r\mid s,a) \sum_g g \Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>		:<math>\sum_a \pi(a \mid s) \sum_{s',r} p(s',r\mid s,a) \sum_g g \Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s)</math>

	This is basically what we want, except we want to say that <math>\sum_g g \Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \mathbb E_\pi[G_{t+1} \mid S_{t+1}=s']</math>, since the latter expression equals <math>v_\pi(s')</math>. Thankfully, we can say this, because of the Markov assumption.		This is basically what we want, except we want to say that <math>\sum_g g \Pr(G_{t+1} = g \mid S_{t+1}=s', R_{t+1}=r, A_t=a, S_t=s) = \mathbb E_\pi[G_{t+1} \mid S_{t+1}=s']</math>, since the latter expression equals <math>v_\pi(s')</math>. Thankfully, we can say this, because of the Markov assumption. Actually proving this is a little complicated; see [https://math.stackexchange.com/questions/3143290/writing-action-value-function-in-terms-of-state-value-function-for-a-markov-deci this question] for some details.

			So we end up with

			:<math>\sum_a \pi(a \mid s) \sum_{s',r} p(s',r\mid s,a) v_\pi(s')</math>

			So now we have

			<math>v_pi(s) = \sum_a \pi(a\mid s) \sum_{s',r} p(s',r \mid s,a) r + \gamma \sum_a \pi(a \mid s) \sum_{s',r} p(s',r\mid s,a) v_\pi(s')</math>