Answers.Body: <p>Based on <a href="http://ai.berkeley.edu/exams/sp14_midterm1_solutions.pdf" rel="nofollow noreferrer">this</a> and <a href="http://adp.princeton.edu/Papers/Powell%20-%20Perspectives%20of%20approximate%20dynamic%20programming.pdf#page=20" rel="nofollow noreferrer">this</a> resources, let me give an answer to my own question, but, essentially, I will just rewrite the contents of the first resource here, for reproducibility, with some minor changes to the notation (to be consistent with Sutton &amp; Barto's book, 2nd edition). Note that I am not fully sure if this formulation is universal (i.e. maybe there are other ways of formulating it), but the contents of the first resource seem to be consistent with the contents in <a href="http://adp.princeton.edu/Papers/Powell%20-%20Perspectives%20of%20approximate%20dynamic%20programming.pdf#page=20" rel="nofollow noreferrer">the second resource</a>.</p>
  <h3>Setup</h3>
  <p>Let's assume that we have an infinite-horizon MDP</p>
  <p><span class="math-container">$$\mathcal{M} = (\mathcal{S}, \mathcal{Y}, \mathcal{A}, \mathcal{T}, \mathcal{R}, \gamma),$$</span>
  where</p>
  <ul>
  <li><span class="math-container">$\mathcal{S}$</span> is the set of states</li>
  <li><span class="math-container">$\mathcal{Y} \subseteq \mathcal{S}$</span> is the set of <em>afterstates</em> (aka <em>post-decision states</em> or &quot;end of period&quot; states [<a href="http://adp.princeton.edu/Papers/Powell%20-%20Perspectives%20of%20approximate%20dynamic%20programming.pdf#page=20" rel="nofollow noreferrer">1</a>], which can also be written as <em>after-states</em>)</li>
  <li><span class="math-container">$\mathcal{A}$</span> is the set of actions</li>
  <li><span class="math-container">$\mathcal{T}$</span> is the transition function</li>
  <li><span class="math-container">$\mathcal{R}$</span> is the reward function</li>
  <li><span class="math-container">$\gamma$</span> is a discount factor</li>
  </ul>
  <p>Let</p>
  <ul>
  <li><span class="math-container">$y \in \mathcal{Y}$</span> be an afterstate</li>
  <li><span class="math-container">$f: \mathcal{S} \times \mathcal{A} \rightarrow \mathcal{Y}$</span> be a <em>deterministic</em> function (from state-action pairs to afterstates), so we have <span class="math-container">$f(s, a) = y$</span></li>
  </ul>
  <p>The transition function <span class="math-container">$\mathcal{T}$</span> for <span class="math-container">$\mathcal{M}$</span> is defined as</p>
  <p><span class="math-container">\begin{align}
  \mathcal{T}(s, a, s^{\prime}) 
  &amp;\doteq P ( s^{\prime} \mid f(s, a)) \\
  &amp;= P ( s^{\prime} \mid y)
  \end{align}</span></p>
  <p>A transition is composed of 2 steps</p>
  <ol>
  <li>a deterministic step, where we apply the deterministic function <span class="math-container">$f(s, a) = y$</span>, which depends on an action <span class="math-container">$a$</span> taken in the state <span class="math-container">$s$</span>, followed by</li>
  <li>a stochastic step, where we apply the probability distribution <span class="math-container">$P (s^{\prime} \mid y)$</span>, which does not depend on the action <span class="math-container">$a$</span> anymore, but only on <span class="math-container">$y$</span></li>
  </ol>
  <p>So, I have denoted afterstates with a different letter, <span class="math-container">$y$</span>, because afterstates are reached with a deterministic function <span class="math-container">$f$</span>, while other states, <span class="math-container">$s$</span> or <span class="math-container">$s'$</span>, are reached with <span class="math-container">$P$</span>.</p>
  <p>After having taken the action <span class="math-container">$a$</span> in the state <span class="math-container">$s$</span>, we get a reward (i.e. we get a reward in step 1), but we do not get a reward after the stochastic step (given that no action is taken).</p>
  <p>So, we can define the reward function <span class="math-container">$\mathcal{R}$</span> for this MDP as follows</p>
  <p><span class="math-container">$$
  \mathcal{R} (s, a, s^{\prime} ) \doteq \mathcal{R}(s, a)
  $$</span></p>
  <p>The situation is illustrated by the following diagram</p>
  <p><a href="https://i.sstatic.net/fi2on.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/fi2on.png" alt="enter image description here" /></a></p>
  <p>So, here, <span class="math-container">$P$</span> is the stochastic transition function (i.e. a probability distribution) as used above. Note that, here, <span class="math-container">$r_t$</span> is a specific realization of <span class="math-container">$R_t$</span> (the random variable) in the formulas below.</p>
  <h3>State value function</h3>
  <p>Let's recall the definition of the <strong>state value function</strong> <span class="math-container">$v_\pi(s)$</span> for a given policy <span class="math-container">$\pi$</span> (as defined in Sutton &amp; Barto, section 3.5)</p>
  <p><span class="math-container">\begin{align}
  v_{\pi}(s) 
  &amp;\doteq 
  \mathbb{E}_{\pi}\left[G_{t} \mid S_{t}=s\right] \\
  &amp;=
  \mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1} \mid S_{t}=s\right],
  \end{align}</span>
  for all <span class="math-container">$s \in \mathcal{S}$</span> and</p>
  <p><span class="math-container">\begin{align}
  G_{t} 
  &amp;\doteq 
  \sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1} \\
  &amp;=
  R_{t+1} + \gamma R_{t+2} + \gamma^{2} R_{t+3}+ \cdots \\
  &amp;=
  \mathcal{R}(s_t, a_t) + \gamma \mathcal{R}(s_{t+1}, a_{t+1})+\gamma^{2} \mathcal{R}(s_{t+2}, a_{t+2}) +\cdots,
  \end{align}</span>
  where <span class="math-container">$\pi(s_t) = a_t$</span> and <span class="math-container">$\mathcal{R}(s_t, a_t) = R_{t+1}$</span>, for <span class="math-container">$t=0, 1, 2, \dots$</span>. (So, note that <span class="math-container">$\mathcal{R} \neq R_t$</span>: the first is the reward function, while the second is a random variable that represents the reward received after having taken action <span class="math-container">$a_t$</span> in step <span class="math-container">$s_t$</span>)</p>
  <p>The <strong>optimal state value function</strong> is defined as</p>
  <p><span class="math-container">$$
  v_{*}(s) \doteq \max _{\pi} v_{\pi}(s)
  $$</span></p>
  <h3>Afterstate value function</h3>
  <p>Similarly, we will define the afterstate value function, but we will use the letter <span class="math-container">$w$</span> just to differentiate it from <span class="math-container">$v$</span> and <span class="math-container">$q$</span>.</p>
  <p><span class="math-container">\begin{align}
  w_{\pi}\left(y\right)
  &amp;\doteq 
  \mathbb{E}_{\pi}\left[G_{t+1} \mid Y_{t}=y\right] 
  \\
  &amp;=
  \mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+2} \mid Y_{t}=y\right] 
  \\
  &amp;=
  \mathbb{E}_{\pi}\left[
  R_{t+2} + \gamma R_{t+3}+\gamma^{2} R_{t+4} + \cdots
   \mid Y_{t}=y\right] 
  \\
  &amp;=
  \mathbb{E}_{\pi}\left[
  \mathcal{R}(s_{t+1}, a_{t+1})+\gamma \mathcal{R}(s_{t+2}, a_{t+2}) + \gamma^{2} \mathcal{R}(s_{t+3}, a_{t+3}) + \cdots
   \mid Y_{t}=y\right] ,
  \end{align}</span>
  where <span class="math-container">$\mathcal{R}(s_{t+1}, a_{t+1}) = R_{t+2}$</span>, for all <span class="math-container">$t$</span>.</p>
  <p>In other words, the value of an afterstate <span class="math-container">$y$</span> (at time step <span class="math-container">$t$</span>, i.e. given <span class="math-container">$Y_t = y$</span>) is defined as the expectation of the return starting from the state that you ended up in <em>after</em> the afterstate <span class="math-container">$y$</span>.</p>
  <p>This seems reasonable to me and is similar to my proposal for the definition of the afterstate value function in the question, although I was not considering any deterministic functions in a potential formulation, and I was also not thinking of afterstates as <em>intermediate</em> states, reached by a deterministic step, between the usual states.</p>
  <p>Similarly to the optimal state value function, we also define the <strong>optimal afterstate value function</strong></p>
  <p><span class="math-container">$$
  w_{*}(y) \doteq \max _{\pi} w_{\pi}(y)
  $$</span></p>
  <h3>Afterstate value function defined in terms of the state value function</h3>
  <p>We can define the afterstate value function in terms</p>
  <p><span class="math-container">$$
  w_{*}(y) 
  = 
  \sum_{s^{\prime}} P (s^{\prime} \mid y ) v_{*} ( s^{\prime} )
  $$</span>
  In other words, <span class="math-container">$w_{*}(y)$</span> is defined as an expectation over the value of next possible states <span class="math-container">$s'$</span> from the afterstate <span class="math-container">$y$</span>.</p>
  <p>This seems to be correct and consistent with the above definitions.</p>
  <h3>More equations</h3>
  <p>In <a href="http://ai.berkeley.edu/exams/sp14_midterm1_solutions.pdf" rel="nofollow noreferrer">this</a> and <a href="http://adp.princeton.edu/Papers/Powell%20-%20Perspectives%20of%20approximate%20dynamic%20programming.pdf#page=20" rel="nofollow noreferrer">this</a> resources, the <strong>state value function is also defined in terms of afterstate value function</strong> as follows</p>
  <p><span class="math-container">$$v_{*}(s)=\max_{a}\left(\mathcal{R}(s, a)+\gamma w_{*}(f(s, a))\right)$$</span></p>
  <p>The <strong>Bellman equation for afterstate value function</strong> (from which an update rule can be derived) is given by</p>
  <p><span class="math-container">$$
  w_{*}(y)
  =
  \sum_{s^{\prime}} 
  P(s^{\prime} \mid y ) 
  \max_{a} ( 
  \mathcal{R} (s^{\prime}, a)
  +
  \gamma 
  w_{*}(f ( s^{\prime}, a ))),
  $$</span>
  which is really similar to the Bellman equation for the state value function.</p>
  <p>Finally, we can also <strong>express the state-action value function in terms of the afterstate value function</strong></p>
  <p><span class="math-container">$$
  q_\pi(s_t, a_t)
  =
  \mathcal{R}\left(s_{t}, a_{t}\right)+\gamma w_{\pi}\left(f\left(s_{t}, a_{t}\right)\right)
  $$</span></p>
  <p>Given that this answer is already quite long, see the resource for more details (including an algorithm based on the afterstate Bellman equation).</p>
  <h3>Implementation</h3>
  <p>If you are the type of person that understands the concepts by looking at the code, then <a href="https://github.com/cpita/TicTacToeAI" rel="nofollow noreferrer">this Github project</a>, which implements a Monte Carlo method that uses afterstates to play tic-tac-toe, may be useful. Afterstates are useful in tic-tac-toe because it is a 2-player game, where two agents take actions in turn, so we can estimate the action that you should take deterministically (as if it was the <span class="math-container">$f$</span> above) before the other agent takes an action (probabilistically), at least, this is my current interpretation of the usefulness of afterstates in this game (and similar games/problems).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-26T06:18:33.977Z
Answers.Text: @NeilSlater interesting ideas, are you working on this idea?
Answers.UserDisplayName: GoingMyWay
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-24T17:19:56.350Z
Answers.Text: In terms of "usefulness", one thing that is not captured so much in the formal treatment is  that the mapping function $f(s,a)$ can be a compression (and is in many games). If this applies, it means there are fewer afterstates to estimate values for than action/state pairs, which means less data is required to gain better estimates with lower error bounds.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-24T12:59:15.527Z
Answers.LastActivityDate: 2021-02-17T14:37:36.783Z
Answers.LastEditDate: 2021-02-17T14:37:36.783Z
Answers.UserDisplayName: nbro
Body: <p>In <a href="https://ai.stackexchange.com/a/24803/2444">this answer</a>, <strong>afterstate value functions</strong> are mentioned, and that temporal-difference (TD) and Monte Carlo (MC) methods can also use these value functions. Mathematically, how are these value functions defined? Yes, they are a function of the next state, but what's the Bellman equation here? Is it simply defined as <span class="math-container">$v(s') = \mathbb{E}\left[ R_t \mid S_t = s, A_t = a, S_{t+1} = s' \right]$</span>? If yes, how can we define it in terms of the state, <span class="math-container">$v(s)$</span>, and state-action, <span class="math-container">$q(s, a)$</span>, value functions, or as a Bellman (recursive) equation?</p>
  <p>Sutton &amp; Barto's book (2nd edition) informally describe afterstate value functions in <a href="http://incompleteideas.net/book/RLbook2020.pdf#page=158" rel="nofollow noreferrer">section 6.8</a>, but they don't provide a formal definition (i.e. Bellman equation in terms of reward or other value functions), so that's why I am asking this question.</p>
  
Tags: <reinforcement-learning><definitions><value-functions><bellman-equations>
Title: How are afterstate value functions mathematically defined?
UserDisplayName: nbro
ThreadText: # How are afterstate value functions mathematically defined?
  
  (Asked by: username_0 on 2020-11-23)
  
  In [this answer](https://ai.stackexchange.com/a/24803/2444), **afterstate value functions** are mentioned, and that temporal-difference (TD) and Monte Carlo (MC) methods can also use these value functions. Mathematically, how are these value functions defined? Yes, they are a function of the next state, but what's the Bellman equation here? Is it simply defined as $v(s') = \mathbb{E}\left[ R\_t \mid S\_t = s, A\_t = a, S\_{t+1} = s' \right]$? If yes, how can we define it in terms of the state, $v(s)$, and state-action, $q(s, a)$, value functions, or as a Bellman (recursive) equation?
  
  Sutton & Barto's book (2nd edition) informally describe afterstate value functions in [section 6.8](http://incompleteideas.net/book/RLbook2020.pdf#page=158), but they don't provide a formal definition (i.e. Bellman equation in terms of reward or other value functions), so that's why I am asking this question.
  
  **Tags:** reinforcement-learning, definitions, value-functions, bellman-equations
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2020-11-24. Score: 3 | Accepted answer
  
  Based on [this](http://ai.berkeley.edu/exams/sp14_midterm1_solutions.pdf) and [this](http://adp.princeton.edu/Papers/Powell%20-%20Perspectives%20of%20approximate%20dynamic%20programming.pdf#page=20) resources, let me give an answer to my own question, but, essentially, I will just rewrite the contents of the first resource here, for reproducibility, with some minor changes to the notation (to be consistent with Sutton & Barto's book, 2nd edition). Note that I am not fully sure if this formulation is universal (i.e. maybe there are other ways of formulating it), but the contents of the first resource seem to be consistent with the contents in [the second resource](http://adp.princeton.edu/Papers/Powell%20-%20Perspectives%20of%20approximate%20dynamic%20programming.pdf#page=20).
  
  ### Setup
  
  Let's assume that we have an infinite-horizon MDP
  
  $$\mathcal{M} = (\mathcal{S}, \mathcal{Y}, \mathcal{A}, \mathcal{T}, \mathcal{R}, \gamma),$$
  where
  
  * $\mathcal{S}$ is the set of states
  * $\mathcal{Y} \subseteq \mathcal{S}$ is the set of *afterstates* (aka *post-decision states* or "end of period" states [[1](http://adp.princeton.edu/Papers/Powell%20-%20Perspectives%20of%20approximate%20dynamic%20programming.pdf#page=20)], which can also be written as *after-states*)
  * $\mathcal{A}$ is the set of actions
  * $\mathcal{T}$ is the transition function
  * $\mathcal{R}$ is the reward function
  * $\gamma$ is a discount factor
  
  Let
  
  * $y \in \mathcal{Y}$ be an afterstate
  * $f: \mathcal{S} \times \mathcal{A} \rightarrow \mathcal{Y}$ be a *deterministic* function (from state-action pairs to afterstates), so we have $f(s, a) = y$
  
  The transition function $\mathcal{T}$ for $\mathcal{M}$ is defined as
  
  \begin{align}
  \mathcal{T}(s, a, s^{\prime})
  &\doteq P ( s^{\prime} \mid f(s, a)) \\
  &= P ( s^{\prime} \mid y)
  \end{align}
  
  A transition is composed of 2 steps
  
  1. a deterministic step, where we apply the deterministic function $f(s, a) = y$, which depends on an action $a$ taken in the state $s$, followed by
  2. a stochastic step, where we apply the probability distribution $P (s^{\prime} \mid y)$, which does not depend on the action $a$ anymore, but only on $y$
  
  So, I have denoted afterstates with a different letter, $y$, because afterstates are reached with a deterministic function $f$, while other states, $s$ or $s'$, are reached with $P$.
  
  After having taken the action $a$ in the state $s$, we get a reward (i.e. we get a reward in step 1), but we do not get a reward after the stochastic step (given that no action is taken).
  
  So, we can define the reward function $\mathcal{R}$ for this MDP as follows
  
  $$
  \mathcal{R} (s, a, s^{\prime} ) \doteq \mathcal{R}(s, a)
  $$
  
  The situation is illustrated by the following diagram
  
  [![enter image description here](https://i.sstatic.net/fi2on.png)](https://i.sstatic.net/fi2on.png)
  
  So, here, $P$ is the stochastic transition function (i.e. a probability distribution) as used above. Note that, here, $r\_t$ is a specific realization of $R\_t$ (the random variable) in the formulas below.
  
  ### State value function
  
  Let's recall the definition of the **state value function** $v\_\pi(s)$ for a given policy $\pi$ (as defined in Sutton & Barto, section 3.5)
  
  \begin{align}
  v\_{\pi}(s)
  &\doteq
  \mathbb{E}\_{\pi}\left[G\_{t} \mid S\_{t}=s\right] \\
  &=
  \mathbb{E}\_{\pi}\left[\sum\_{k=0}^{\infty} \gamma^{k} R\_{t+k+1} \mid S\_{t}=s\right],
  \end{align}
  for all $s \in \mathcal{S}$ and
  
  \begin{align}
  G\_{t}
  &\doteq
  \sum\_{k=0}^{\infty} \gamma^{k} R\_{t+k+1} \\
  &=
  R\_{t+1} + \gamma R\_{t+2} + \gamma^{2} R\_{t+3}+ \cdots \\
  &=
  \mathcal{R}(s\_t, a\_t) + \gamma \mathcal{R}(s\_{t+1}, a\_{t+1})+\gamma^{2} \mathcal{R}(s\_{t+2}, a\_{t+2}) +\cdots,
  \end{align}
  where $\pi(s\_t) = a\_t$ and $\mathcal{R}(s\_t, a\_t) = R\_{t+1}$, for $t=0, 1, 2, \dots$. (So, note that $\mathcal{R} \neq R\_t$: the first is the reward function, while the second is a random variable that represents the reward received after having taken action $a\_t$ in step $s\_t$)
  
  The **optimal state value function** is defined as
  
  $$
  v\_{\*}(s) \doteq \max \_{\pi} v\_{\pi}(s)
  $$
  
  ### Afterstate value function
  
  Similarly, we will define the afterstate value function, but we will use the letter $w$ just to differentiate it from $v$ and $q$.
  
  \begin{align}
  w\_{\pi}\left(y\right)
  &\doteq
  \mathbb{E}\_{\pi}\left[G\_{t+1} \mid Y\_{t}=y\right]
  \\
  &=
  \mathbb{E}\_{\pi}\left[\sum\_{k=0}^{\infty} \gamma^{k} R\_{t+k+2} \mid Y\_{t}=y\right]
  \\
  &=
  \mathbb{E}\_{\pi}\left[
  R\_{t+2} + \gamma R\_{t+3}+\gamma^{2} R\_{t+4} + \cdots
  \mid Y\_{t}=y\right]
  \\
  &=
  \mathbb{E}\_{\pi}\left[
  \mathcal{R}(s\_{t+1}, a\_{t+1})+\gamma \mathcal{R}(s\_{t+2}, a\_{t+2}) + \gamma^{2} \mathcal{R}(s\_{t+3}, a\_{t+3}) + \cdots
  \mid Y\_{t}=y\right] ,
  \end{align}
  where $\mathcal{R}(s\_{t+1}, a\_{t+1}) = R\_{t+2}$, for all $t$.
  
  In other words, the value of an afterstate $y$ (at time step $t$, i.e. given $Y\_t = y$) is defined as the expectation of the return starting from the state that you ended up in *after* the afterstate $y$.
  
  This seems reasonable to me and is similar to my proposal for the definition of the afterstate value function in the question, although I was not considering any deterministic functions in a potential formulation, and I was also not thinking of afterstates as *intermediate* states, reached by a deterministic step, between the usual states.
  
  Similarly to the optimal state value function, we also define the **optimal afterstate value function**
  
  $$
  w\_{\*}(y) \doteq \max \_{\pi} w\_{\pi}(y)
  $$
  
  ### Afterstate value function defined in terms of the state value function
  
  We can define the afterstate value function in terms
  
  $$
  w\_{\*}(y)
  =
  \sum\_{s^{\prime}} P (s^{\prime} \mid y ) v\_{\*} ( s^{\prime} )
  $$
  In other words, $w\_{\*}(y)$ is defined as an expectation over the value of next possible states $s'$ from the afterstate $y$.
  
  This seems to be correct and consistent with the above definitions.
  
  ### More equations
  
  In [this](http://ai.berkeley.edu/exams/sp14_midterm1_solutions.pdf) and [this](http://adp.princeton.edu/Papers/Powell%20-%20Perspectives%20of%20approximate%20dynamic%20programming.pdf#page=20) resources, the **state value function is also defined in terms of afterstate value function** as follows
  
  $$v\_{\*}(s)=\max\_{a}\left(\mathcal{R}(s, a)+\gamma w\_{\*}(f(s, a))\right)$$
  
  The **Bellman equation for afterstate value function** (from which an update rule can be derived) is given by
  
  $$
  w\_{\*}(y)
  =
  \sum\_{s^{\prime}}
  P(s^{\prime} \mid y )
  \max\_{a} (
  \mathcal{R} (s^{\prime}, a)
  +
  \gamma
  w\_{\*}(f ( s^{\prime}, a ))),
  $$
  which is really similar to the Bellman equation for the state value function.
  
  Finally, we can also **express the state-action value function in terms of the afterstate value function**
  
  $$
  q\_\pi(s\_t, a\_t)
  =
  \mathcal{R}\left(s\_{t}, a\_{t}\right)+\gamma w\_{\pi}\left(f\left(s\_{t}, a\_{t}\right)\right)
  $$
  
  Given that this answer is already quite long, see the resource for more details (including an algorithm based on the afterstate Bellman equation).
  
  ### Implementation
  
  If you are the type of person that understands the concepts by looking at the code, then [this Github project](https://github.com/cpita/TicTacToeAI), which implements a Monte Carlo method that uses afterstates to play tic-tac-toe, may be useful. Afterstates are useful in tic-tac-toe because it is a 2-player game, where two agents take actions in turn, so we can estimate the action that you should take deterministically (as if it was the $f$ above) before the other agent takes an action (probabilistically), at least, this is my current interpretation of the usefulness of afterstates in this game (and similar games/problems).
  
  > **Comments:**
  > **username_2**: In terms of "usefulness", one thing that is not captured so much in the formal treatment is  that the mapping function $f(s,a)$ can be a compression (and is in many games). If this applies, it means there are fewer afterstates to estimate values for than action/state pairs, which means less data is required to gain better estimates with lower error bounds.  
  > **username_1**: @NeilSlater interesting ideas, are you working on this idea?  
  
  ---
  
  