$\newcommand{\plcypmf}[2]{\pi(#1\,|\,#2)}$
$\newcommand{\condpmf}[2]{p(#1\,|\,#2)}$
$\newcommand{\condpmfsym}[3]{#1(#2\,|\,#3)}$
$\newcommand{\cp}[2]{P\{#1\:|\, #2\}}$
$\newcommand{\cpwrt}[3]{P_{#1}\{#2\:|\, #3\}}$
$\newcommand{\Ecwrt}[3]{E_{#1}[#2\:|\, #3]}$
$\newcommand{\argmax}[1]{\text{arg max}_{#1}\,}$
$\newcommand{\cases}[1]{\begin{cases}#1\end{cases}}$
$\newcommand{\mcalA}{\mathcal{A}}$
$\newcommand{\mcalR}{\mathcal{R}}$
$\newcommand{\mcalS}{\mathcal{S}}$
$\newcommand{\qd}{\quad}$
$\newcommand{\wR}{\mathbb{R}}$
$\newcommand{\Bop}{\Big(}$
$\newcommand{\Bcp}{\Big)}$
$\newcommand{\Prn}[1]{\Bop #1\Bcp}$
$\newcommand{\align}[1]{\begin{align*}#1\end{align*}}$
$\newcommand{\wes}{\blacksquare}$

Let $T$ be the time step variable and let $t$ be a particular time step. 

Given an agent, we define a policy $\pi$ to be the conditional PMF that that agent takes a particular action given a particular state. That is, $\condpmfsym{\pi}{a}{s}$ is the probability that that agent takes action $a$ given the state $s$. More explicitly, let $\Pi$ denote the set of all possible policies on $\mcalS$ and $\mcalA$ and, for a policy $\pi$, we define

$$
\condpmfsym{\pi}{a}{s}\equiv\cpwrt{\pi}{A_T=a}{S_T=s}\equiv\cp{A_T=a}{S_T=s,\Pi=\pi}\qd\text{for all time steps }T
$$

Notice that the conditional PMF $\condpmfsym{\pi}{a}{s}$ is constant relative to the time step variable $T$. Many authors use this definition and hence assume that each policy behaves the same at all time steps.

But it is often helpful to define a policy where the conditional PMF's vary with the time step variable $T$. Indeed, there is no mathematical or probabilistic reason that precludes us from defining a policy with a different PMF at each time step. And when we learn about optimal policies (below), we can easily imagine some optimal policies whose behavior differs between time steps.

Hence, more generally, we define a policy $\pi$ by a set of conditional PMF's

$$
\condpmfsym{\pi}{a}{s}
 \equiv \cases{\cpwrt{\pi_{0}}{A_{0}=a}{S_{0}=s}\\\cpwrt{\pi_{1}}{A_{1}=a}{S_{1}=s}\\\vdots\\\cpwrt{\pi_{t}}{A_{t}=a}{S_{t}=s}\\\cpwrt{\pi_{t+1}}{A_{t+1}=a}{S_{t+1}=s}\\\vdots}
$$

such that

$$
1=\sum_{a\in\mcalA(s)}\cpwrt{\pi_{T}}{A_T=a}{S_T=s}\qd\text{for all }s\in\mcalS\text{ and all }T=0,1,2,\dots
$$

We assume that the Markov Property holds:

$$\align{
&\condpmf{g_{t+1}}{s',a,s}=\condpmf{g_{t+1}}{s'} \\\\
&\condpmf{g_{t+1}}{s',r,a,s}=\condpmf{g_{t+1}}{s'}\tag{MDP.0} \\\\
&\condpmf{r_{t+2}}{s',a,s}=\condpmf{r_{t+2}}{s'} \\\\
}$$

__Proposition MDP.5__ Let $s_0\in\mcalS$, let $a_0\in\mcalA(s_0)$, and let $\pi$ be any policy on $\mcalS$. Define the policy $\phi_t$ on $\mcalS$ by

$$
\cpwrt{\phi_t}{A_T=a}{S_T=s}=\condpmfsym{\phi_t}{a}{s}\equiv\cases{\condpmfsym{\pi}{a}{s}&\text{if }T\neq t\text{ or }s\neq s_0\\1&\text{else if }a=a_0\\0&\text{else}}
$$

Then, for all $a\in\mcalA(s_0)$, we have

$$
q_{\phi_{t}}(s_0,a) = q_{\pi}(s_0,a) \\
$$

__Proof__ If $g_{t+1}$ is a possible outcome of $G_{t+1}$, then $\condpmf{g_{t+1}}{s',\phi_t}=\condpmf{g_{t+1}}{s',\pi}$ since $\phi_t=\pi$ for $T=t+1,t+2,\dots$. Also note that, for all $a\in\mcalA(s_0)$, we have 

$$\condpmf{s'}{s_0,a,\phi_t}=\condpmf{s'}{s_0,a,\pi}$$

That is, if we know the state and action in the current time step, then the policy is irrelevant to determining the next state. Hence, for all $a\in\mcalA(s_0)$, we have

$$\align{
q_{\phi_t}(s_0,a) &= \Ecwrt{\phi}{G_t}{S_t=s_0,A_t=a} \\
 &= \Ecwrt{\phi_t}{R_{t+1}+\gamma G_{t+1}}{S_t=s_0,A_t=a} \\
 &= \Ecwrt{\phi_t}{R_{t+1}}{S_t=s_0,A_t=a}+\Ecwrt{\phi_t}{\gamma G_{t+1}}{S_t=s_0,A_t=a} \\
 &= \Ecwrt{\phi_t}{R_{t+1}}{S_t=s_0,A_t=a}+\sum_{g_{t+1}}\gamma g_{t+1}\cdot\condpmf{g_{t+1}}{s_0,a,\phi_t} \\
 &= \Ecwrt{\phi_t}{R_{t+1}}{S_t=s_0,A_t=a}+\sum_{g_{t+1}}\gamma g_{t+1}\cdot\sum_{s'}\condpmf{g_{t+1}}{s',s_0,a,\phi_t}\cdot\condpmf{s'}{s_0,a,\phi_t} \\
 &= \Ecwrt{\phi_t}{R_{t+1}}{S_t=s_0,A_t=a}+\sum_{g_{t+1}}\gamma g_{t+1}\cdot\sum_{s'}\condpmf{g_{t+1}}{s',\phi_t}\cdot\condpmf{s'}{s_0,a,\phi_t}\tag{by MDP.0} \\
 &= \Ecwrt{\pi}{R_{t+1}}{S_t=s_0,A_t=a}+\sum_{g_{t+1}}\gamma g_{t+1}\cdot\sum_{s'}\condpmf{g_{t+1}}{s',\pi}\cdot\condpmf{s'}{s_0,a,\pi} \\
 &= \Ecwrt{\pi}{R_{t+1}}{S_t=s_0,A_t=a}+\sum_{g_{t+1}}\gamma g_{t+1}\cdot\sum_{s'}\condpmf{g_{t+1}}{s',s_0,a,\pi}\cdot\condpmf{s'}{s_0,a,\pi} \\
 &= \Ecwrt{\pi}{R_{t+1}}{S_t=s_0,A_t=a}+\sum_{g_{t+1}}\gamma g_{t+1}\cdot\condpmf{g_{t+1}}{s_0,a,\pi} \\
 &= \Ecwrt{\pi}{R_{t+1}}{S_t=s_0,A_t=a}+\Ecwrt{\pi}{\gamma G_{t+1}}{S_t=s_0,A_t=a} \\
 &= \Ecwrt{\pi}{R_{t+1}+\gamma G_{t+1}}{S_t=s_0,A_t=a} \\
 &= \Ecwrt{\pi}{G_t}{S_t=s_0,A_t=a} \\
 &= q_{\pi}(s_0,a) \\
}$$

$\wes$

Define $v_{*}:\mcalS\mapsto\wR$ by

$$
v_{*}(s)\equiv\max_{\pi}v_{\pi}(s)\qd\text{for all }s\in\mcalS
$$

Define $q_{*}:\mcalS\times\mcalA\mapsto\wR$ by

$$
q_{*}(s,a)\equiv\max_{\pi}q_{\pi}(s,a)\qd\text{for all }s\in\mcalS,a\in\mcalA(s)
$$

__Proposition MDP.7__ For all $s\in\mcalS$, we have

$$
v_{*}(s) = \max_{a\in\mcalA(s)}q_{*}(s,a)
$$

__Proof__ Let $s_0\in\mcalS$ and define $a_{*}\in\argmax{a\in\mcalA(s_0)}q_{*}(s_0,a)$. Then for any policy $\pi$, we have

$$\align{
v_{\pi}(s_0) &= \sum_{a\in\mcalA({s_0})}\plcypmf{a}{s_0}\cdot q_{\pi}(s_0,a) \\
 &\leq \sum_{a\in\mcalA({s_0})}\plcypmf{a}{s_0}\cdot q_{*}(s_0,a) \\
 &\leq \sum_{a\in\mcalA({s_0})}\plcypmf{a}{s_0}\cdot q_{*}(s_0,a_{*}) \\
 &= q_{*}(s_0,a_{*})\cdot\sum_{a\in\mcalA({s_0})}\plcypmf{a}{s_0} \\
 &= q_{*}(s_0,a_{*}) \\
 &= \max_{a\in\mcalA(s_0)}q_{*}(s_0,a)
}$$

Since this is true for all policies $\pi$, then it must be that

$$
v_{*}(s_0)=\max_{\pi}v_{\pi}(s_0)\leq\max_{a\in\mcalA(s_0)}q_{*}(s_0,a)
$$

Suppose, by way of contradiction, that we have strict inequality:

$$
v_{*}(s_0)\lt\max_{a\in\mcalA(s_0)}q_{*}(s_0,a)
\tag{MDP.7.1}
$$

Define the policy $\pi_{**}$ by

$$
\pi_{**}\in\argmax{\pi}q_{\pi}(s_0,a_{*})
$$

Then

$$
q_{\pi_{**}}(s_0,a_{*}) = \max_{\pi}q_{\pi}(s_0,a_{*}) = q_{*}(s_0,a_{*}) = \max_{a\in\mcalA(s_0)}q_{*}(s_0,a)
$$

Also define the policy $\phi_t$ by

$$
\cpwrt{\phi_t}{A_T=a}{S_T=s}=\condpmfsym{\phi_t}{a}{s}\equiv\cases{\condpmfsym{\pi_{**}}{a}{s}&\text{if }T\neq t\text{ or }s\neq s_0\\1&\text{else if }a=a_{*}\\0&\text{else}}
$$

Then MDP.5 gives the third equality:

$$\align{
v_{\phi_t}(s_0) = \sum_{a\in\mcalA(s_0)}\condpmfsym{\phi_t}{a}{s_0}q_{\phi_t}(s_0,a) = q_{\phi_t}(s_0,a_{*})= q_{\pi_{**}}(s_0,a_{*}) = \max_{a\in\mcalA(s_0)}q_{*}(s_0,a) \gt v_{*}(s_0)
}$$

This contradicts the definition of $v_{*}(s_0)\equiv\max_{\pi}v_{\pi}(s_0)$. Hence assumption MDP.7.1 is false and we have

$$
v_{*}(s_0)=\max_{a\in\mcalA(s_0)}q_{*}(s_0,a)
$$

Since $s_0\in\mcalS$ was chosen arbitrarily, then this equality holds for all $s\in\mcalS$.

$\wes$