3 deleted 11 characters in body edited Apr 3 at 17:11 spektr 15666 bronze badges Your intuition is off because the policy $$\pi$$ used to form $$V_k$$ (or what I will denote as $$V^{\pi}$$) will actually be different than the policy $$\pi_k$$ if $$\pi$$ is not optimal. We can show they will be different in the event $$\pi$$ is not optimal by investigating the following. We can first state the following definitions \begin{align} V^{\pi}(s) &= R(s, \pi(s)) + \gamma \mathbb{E}_{s' \sim P(s,\pi(s))} \left[V^{\pi}(s')\right] \\ Q^{\pi}(s,a) &= R(s,a) + \gamma \mathbb{E}_{s' \sim P(s,a)} \left[V^{\pi}(s')\right] \end{align} If we make note of the above definitions, it is clear that $$V^{\pi}(s) = Q^{\pi}(s, \pi(s))$$. We can also use these definitions to restate $$\pi_k$$ in the following manner \begin{align} \pi_k(s) &= \arg \min_{a \in A(s)} \left\lbrace R(s,a) + \gamma \mathbb{E}_{s' \sim P(s,a)} \left[V^{\pi}(s')\right] \right\rbrace \\ &= \arg \min_{a \in A(s)} Q^{\pi}(s,a) \\ &= \arg \min_{a \in A(s)} \left\lbrace Q^{\pi}(s,a) - Q^{\pi}(s, \pi(s))\right\rbrace \end{align} If we look at the final expression for $$\pi_{k}(s)$$, it is clear that for a given state $$s$$, $$\pi_k(s)$$ will be a better action than $$\pi(s)$$ unless $$\pi(s)$$ is already an optimal action for the given state $$s$$. This implies that $$V^{\pi_k}(s) \leq V^{\pi}(s)$$ for all $$s \in S$$. The way one can view it is that the $$\arg \min$$ step to construct $$\pi_k(s)$$ is effectively saying "For each state $$s$$, choose the action $$a$$ that is at least as good asmost optimal relative to $$\pi(s)$$, if not better, to make as the action choice for $$\pi_k(s)$$". Your intuition is off because the policy $$\pi$$ used to form $$V_k$$ (or what I will denote as $$V^{\pi}$$) will actually be different than the policy $$\pi_k$$ if $$\pi$$ is not optimal. We can show they will be different in the event $$\pi$$ is not optimal by investigating the following. We can first state the following definitions \begin{align} V^{\pi}(s) &= R(s, \pi(s)) + \gamma \mathbb{E}_{s' \sim P(s,\pi(s))} \left[V^{\pi}(s')\right] \\ Q^{\pi}(s,a) &= R(s,a) + \gamma \mathbb{E}_{s' \sim P(s,a)} \left[V^{\pi}(s')\right] \end{align} If we make note of the above definitions, it is clear that $$V^{\pi}(s) = Q^{\pi}(s, \pi(s))$$. We can also use these definitions to restate $$\pi_k$$ in the following manner \begin{align} \pi_k(s) &= \arg \min_{a \in A(s)} \left\lbrace R(s,a) + \gamma \mathbb{E}_{s' \sim P(s,a)} \left[V^{\pi}(s')\right] \right\rbrace \\ &= \arg \min_{a \in A(s)} Q^{\pi}(s,a) \\ &= \arg \min_{a \in A(s)} \left\lbrace Q^{\pi}(s,a) - Q^{\pi}(s, \pi(s))\right\rbrace \end{align} If we look at the final expression for $$\pi_{k}(s)$$, it is clear that for a given state $$s$$, $$\pi_k(s)$$ will be a better action than $$\pi(s)$$ unless $$\pi(s)$$ is already an optimal action for the given state $$s$$. This implies that $$V^{\pi_k}(s) \leq V^{\pi}(s)$$ for all $$s \in S$$. The way one can view it is that the $$\arg \min$$ step to construct $$\pi_k(s)$$ is effectively saying "For each state $$s$$, choose the action $$a$$ that is at least as good as $$\pi(s)$$, if not better, to make as the action choice for $$\pi_k(s)$$". Your intuition is off because the policy $$\pi$$ used to form $$V_k$$ (or what I will denote as $$V^{\pi}$$) will actually be different than the policy $$\pi_k$$ if $$\pi$$ is not optimal. We can show they will be different in the event $$\pi$$ is not optimal by investigating the following. We can first state the following definitions \begin{align} V^{\pi}(s) &= R(s, \pi(s)) + \gamma \mathbb{E}_{s' \sim P(s,\pi(s))} \left[V^{\pi}(s')\right] \\ Q^{\pi}(s,a) &= R(s,a) + \gamma \mathbb{E}_{s' \sim P(s,a)} \left[V^{\pi}(s')\right] \end{align} If we make note of the above definitions, it is clear that $$V^{\pi}(s) = Q^{\pi}(s, \pi(s))$$. We can also use these definitions to restate $$\pi_k$$ in the following manner \begin{align} \pi_k(s) &= \arg \min_{a \in A(s)} \left\lbrace R(s,a) + \gamma \mathbb{E}_{s' \sim P(s,a)} \left[V^{\pi}(s')\right] \right\rbrace \\ &= \arg \min_{a \in A(s)} Q^{\pi}(s,a) \\ &= \arg \min_{a \in A(s)} \left\lbrace Q^{\pi}(s,a) - Q^{\pi}(s, \pi(s))\right\rbrace \end{align} If we look at the final expression for $$\pi_{k}(s)$$, it is clear that for a given state $$s$$, $$\pi_k(s)$$ will be a better action than $$\pi(s)$$ unless $$\pi(s)$$ is already an optimal action for the given state $$s$$. This implies that $$V^{\pi_k}(s) \leq V^{\pi}(s)$$ for all $$s \in S$$. The way one can view it is that the $$\arg \min$$ step to construct $$\pi_k(s)$$ is effectively saying "For each state $$s$$, choose the action $$a$$ that is most optimal relative to $$\pi(s)$$ to make as the action choice for $$\pi_k(s)$$". 2 added 241 characters in body edited Apr 3 at 16:51 spektr 15666 bronze badges Your intuition is off because the policy $$\pi$$ used to form $$V_k$$ (or what I will denote as $$V^{\pi}$$) will actually be different than the policy $$\pi_k$$ if $$\pi$$ is not optimal. We can show they will be different in the event $$\pi$$ is not optimal by investigating the following. We can first state the following definitions \begin{align} V^{\pi}(s) &= R(s, \pi(s)) + \gamma \mathbb{E}_{s' \sim P(s,\pi(s))} \left[V^{\pi}(s')\right] \\ Q^{\pi}(s,a) &= R(s,a) + \gamma \mathbb{E}_{s' \sim P(s,a)} \left[V^{\pi}(s')\right] \end{align} If we make note of the above definitions, it is clear that $$V^{\pi}(s) = Q^{\pi}(s, \pi(s))$$. We can also use these definitions to restate $$\pi_k$$ in the following manner \begin{align} \pi_k(s) &= \arg \min_{a \in A(s)} \left\lbrace R(s,a) + \gamma \mathbb{E}_{s' \sim P(s,a)} \left[V^{\pi}(s')\right] \right\rbrace \\ &= \arg \min_{a \in A(s)} Q^{\pi}(s,a) \\ &= \arg \min_{a \in A(s)} \left\lbrace Q^{\pi}(s,a) - Q^{\pi}(s, \pi(s))\right\rbrace \end{align} If we look at the final expression for $$\pi_{k}(s)$$, it is clear that for a given state $$s$$, $$\pi_k(s)$$ will be a better action than $$\pi(s)$$ unless $$\pi(s)$$ is already an optimal action for the given state $$s$$. This implies that $$V^{\pi_k}(s) \leq V^{\pi}(s)$$ for all $$s \in S$$. The way one can view it is that the $$\arg \min$$ step to construct $$\pi_k(s)$$ is effectively saying "For each state $$s$$, choose the action $$a$$ that is at least as good as $$\pi(s)$$, if not better, to make as the action choice for $$\pi_k(s)$$". Your intuition is off because the policy $$\pi$$ used to form $$V_k$$ (or what I will denote as $$V^{\pi}$$) will actually be different than the policy $$\pi_k$$ if $$\pi$$ is not optimal. We can show they will be different in the event $$\pi$$ is not optimal by investigating the following. We can first state the following definitions \begin{align} V^{\pi}(s) &= R(s, \pi(s)) + \gamma \mathbb{E}_{s' \sim P(s,\pi(s))} \left[V^{\pi}(s')\right] \\ Q^{\pi}(s,a) &= R(s,a) + \gamma \mathbb{E}_{s' \sim P(s,a)} \left[V^{\pi}(s')\right] \end{align} If we make note of the above definitions, it is clear that $$V^{\pi}(s) = Q^{\pi}(s, \pi(s))$$. We can also use these definitions to restate $$\pi_k$$ in the following manner \begin{align} \pi_k(s) &= \arg \min_{a \in A(s)} \left\lbrace R(s,a) + \gamma \mathbb{E}_{s' \sim P(s,a)} \left[V^{\pi}(s')\right] \right\rbrace \\ &= \arg \min_{a \in A(s)} Q^{\pi}(s,a) \\ &= \arg \min_{a \in A(s)} \left\lbrace Q^{\pi}(s,a) - Q^{\pi}(s, \pi(s))\right\rbrace \end{align} If we look at the final expression for $$\pi_{k}(s)$$, it is clear that for a given state $$s$$, $$\pi_k(s)$$ will be a better action than $$\pi(s)$$ unless $$\pi(s)$$ is already an optimal action for the given state $$s$$. This implies that $$V^{\pi_k}(s) \leq V^{\pi}(s)$$ for all $$s \in S$$. Your intuition is off because the policy $$\pi$$ used to form $$V_k$$ (or what I will denote as $$V^{\pi}$$) will actually be different than the policy $$\pi_k$$ if $$\pi$$ is not optimal. We can show they will be different in the event $$\pi$$ is not optimal by investigating the following. We can first state the following definitions \begin{align} V^{\pi}(s) &= R(s, \pi(s)) + \gamma \mathbb{E}_{s' \sim P(s,\pi(s))} \left[V^{\pi}(s')\right] \\ Q^{\pi}(s,a) &= R(s,a) + \gamma \mathbb{E}_{s' \sim P(s,a)} \left[V^{\pi}(s')\right] \end{align} If we make note of the above definitions, it is clear that $$V^{\pi}(s) = Q^{\pi}(s, \pi(s))$$. We can also use these definitions to restate $$\pi_k$$ in the following manner \begin{align} \pi_k(s) &= \arg \min_{a \in A(s)} \left\lbrace R(s,a) + \gamma \mathbb{E}_{s' \sim P(s,a)} \left[V^{\pi}(s')\right] \right\rbrace \\ &= \arg \min_{a \in A(s)} Q^{\pi}(s,a) \\ &= \arg \min_{a \in A(s)} \left\lbrace Q^{\pi}(s,a) - Q^{\pi}(s, \pi(s))\right\rbrace \end{align} If we look at the final expression for $$\pi_{k}(s)$$, it is clear that for a given state $$s$$, $$\pi_k(s)$$ will be a better action than $$\pi(s)$$ unless $$\pi(s)$$ is already an optimal action for the given state $$s$$. This implies that $$V^{\pi_k}(s) \leq V^{\pi}(s)$$ for all $$s \in S$$. The way one can view it is that the $$\arg \min$$ step to construct $$\pi_k(s)$$ is effectively saying "For each state $$s$$, choose the action $$a$$ that is at least as good as $$\pi(s)$$, if not better, to make as the action choice for $$\pi_k(s)$$". 1 answered Apr 3 at 16:39 spektr 15666 bronze badges Your intuition is off because the policy $$\pi$$ used to form $$V_k$$ (or what I will denote as $$V^{\pi}$$) will actually be different than the policy $$\pi_k$$ if $$\pi$$ is not optimal. We can show they will be different in the event $$\pi$$ is not optimal by investigating the following. We can first state the following definitions \begin{align} V^{\pi}(s) &= R(s, \pi(s)) + \gamma \mathbb{E}_{s' \sim P(s,\pi(s))} \left[V^{\pi}(s')\right] \\ Q^{\pi}(s,a) &= R(s,a) + \gamma \mathbb{E}_{s' \sim P(s,a)} \left[V^{\pi}(s')\right] \end{align} If we make note of the above definitions, it is clear that $$V^{\pi}(s) = Q^{\pi}(s, \pi(s))$$. We can also use these definitions to restate $$\pi_k$$ in the following manner \begin{align} \pi_k(s) &= \arg \min_{a \in A(s)} \left\lbrace R(s,a) + \gamma \mathbb{E}_{s' \sim P(s,a)} \left[V^{\pi}(s')\right] \right\rbrace \\ &= \arg \min_{a \in A(s)} Q^{\pi}(s,a) \\ &= \arg \min_{a \in A(s)} \left\lbrace Q^{\pi}(s,a) - Q^{\pi}(s, \pi(s))\right\rbrace \end{align} If we look at the final expression for $$\pi_{k}(s)$$, it is clear that for a given state $$s$$, $$\pi_k(s)$$ will be a better action than $$\pi(s)$$ unless $$\pi(s)$$ is already an optimal action for the given state $$s$$. This implies that $$V^{\pi_k}(s) \leq V^{\pi}(s)$$ for all $$s \in S$$.