Answers.Body: <p>The value of a state depends on the policy that you use, so I'll make the assumption here that you're talking about value <strong>using the optimal policy</strong>. </p>
  
  <p><em>According to the optimal policy, the agent would choose to stay in the square (1,1) every time</em>, but since it has a 0.8 probability of actually staying (and 0.2 probability of dying), we can compute the value of the agent using the Bellman equation as:</p>
  
  <p><span class="math-container">$$
  V(1,1) = 1 + 0.8 V(1,1) + 0.2 V(\text{death state}) \\
  \implies V(1,1) = 1 + 0.8 V(1,1) \\
  \implies V(1,1) = \frac{1}{1 - 0.8} \\
  \implies V(1,1) = 5
  $$</span></p>
  
  <p>There are other ways of deriving the same number (value function has multiple definitions) but they are equivalent.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-13T16:49:55.283Z
Answers.LastActivityDate: 2020-06-13T17:03:19.367Z
Answers.LastEditDate: 2020-06-13T17:03:19.367Z
Answers.UserDisplayName: shaabhishek
Answers.Body: <p>I will fill in some details in shaabhishek's answer for people who are interested.</p>
  
  <blockquote>
    <p>With this in mind, what is the value of a square (1,1)?</p>
  </blockquote>
  
  <p>First of all, the value function is dependent on a policy. The supposed correct answer you provided is the value of <span class="math-container">$(1, 1)$</span> under the <em>optimal</em> policy, so from now on, we will assume that we are finding the value function under the optimal policy. Also, we will assume that the environment dynamics are deterministic: choosing to take an action will guarantee that the agent moves in that direction.</p>
  
  <blockquote>
    <p>Possible actions are go left, right, up, down or stay in a square. Reward has a value 1 for any action done in square (1,1) and zero for actions done in all the other squares.</p>
  </blockquote>
  
  <p>Based on this information, the optimal policy at <span class="math-container">$(1, 1)$</span> should be to always stay in that square. The agent doesn't receive any reward for being in another square, and the probability of dying is the same for each square, so choosing the action to stay in square <span class="math-container">$(1, 1)$</span> is best.</p>
  
  <blockquote>
    <p>The correct answer is supposed to be 5, and is calculated as <span class="math-container">$\frac{1}{1 \cdot 0.2} = 5$</span>. But why is that?</p>
  </blockquote>
  
  <p>By the Bellman Equation, the value function under the optimal policy <span class="math-container">$\pi_*$</span> at <span class="math-container">$(1,1)$</span> can be written as follows:</p>
  
  <p><span class="math-container">$$v_{\pi_*}((1, 1))  = \mathbb{E}_{\pi_*}\left[R_t + \gamma v_{\pi_{*}}(s') | s = (1,1)\right],$$</span></p>
  
  <p>where <span class="math-container">$R_t$</span> denotes the immediate reward, <span class="math-container">$s$</span> denotes the current state, and <span class="math-container">$s'$</span> denotes the next state. By the problem statement, <span class="math-container">$\gamma = 1$</span>. The next state is the <span class="math-container">$\texttt{dead}$</span> terminal state <span class="math-container">$\alpha = 20\%$</span> of the time. Terminal states have value <span class="math-container">$0$</span>, as they do not accrue future rewards. The next state <span class="math-container">$s'$</span> is equal to <span class="math-container">$(1, 1)$</span> the remaining <span class="math-container">$(1-\alpha) = 80\%$</span> of the time because our policy dictates to remain in the same state and we assumed the dynamics were deterministic. Since expectation is linear, we can rewrite the expectation as follows (replacing <span class="math-container">$\gamma$</span> with <span class="math-container">$1$</span>):</p>
  
  <p><span class="math-container">\begin{align*}
  v_{\pi_*}((1,1))  &amp;= \mathbb{E}_{\pi_*}\left[R_t + v_{\pi_{*}}(s') | s = (1,1)\right]\\
  &amp;= \mathbb{E}_{\pi_*}\left[R_t |s=(1, 1)\right]+  \mathbb{E}_{\pi_*}\left[v_{\pi_{*}}(s') | s = (1,1)\right].\qquad (*)
  \end{align*}</span></p>
  
  <p>We have </p>
  
  <p><span class="math-container">$$\mathbb{E}_{\pi_*}\left[R_t |s=(1, 1)\right] = 1\qquad (**)$$</span></p>
  
  <p>because we are guaranteed an immediate reward of <span class="math-container">$1$</span> when taking an action in state <span class="math-container">$(1, 1)$</span>. Also, from the comments above regarding the next state values and probabilities, we have the following:</p>
  
  <p><span class="math-container">\begin{align*}\mathbb{E}_{\pi_*}\left[v_{\pi_{*}}(s') | s = (1,1)\right] &amp;= (1-\alpha) \cdot v_{\pi_{*}}((1,1)) + \alpha \cdot v_{\pi_*}(\texttt{dead})\\
  &amp;= 0.8 \cdot v_{\pi_{*}}((1,1)) + 0.2 \cdot 0\\
  &amp;= 0.8 \cdot v_{\pi_{*}}((1,1)).\qquad (***)
  \end{align*}</span></p>
  
  <p>Substituting <span class="math-container">$(**)$</span> and <span class="math-container">$(***)$</span> into <span class="math-container">$(*)$</span> yields the following:</p>
  
  <p><span class="math-container">\begin{align*}
  v_{\pi_*}((1,1)) &amp;= 1 + 0.8 \cdot v_{\pi_{*}}((1,1))\\
  v_{\pi_*}((1,1)) - 0.8 \cdot v_{\pi_{*}}((1,1)) &amp;= 1\\
  (1-0.8)v_{\pi_*}((1,1)) &amp;= 1\\
  v_{\pi_*}((1,1))  &amp;= \frac{1}{1-0.8} = \frac{1}{0.2} = 5.
  \end{align*}</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-13T18:40:16.753Z
Answers.LastActivityDate: 2020-06-13T18:40:16.753Z
Answers.UserDisplayName: DeepQZero
Body: <p>We assume infinite horizon and discount factor <span class="math-container">$\gamma = 1$</span>. At each step, after the agent takes an action and gets its reward, there is a probability <span class="math-container">$\alpha = 0.2$</span>, that agent will die. The assumed maze looks like this</p>
  
  <p><a href="https://i.sstatic.net/vTe5M.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/vTe5M.png" alt="enter image description here"></a></p>
  
  <p>Possible actions are go left, right, up, down or stay in a square. The reward has a value 1 for any action done in the square (1,1) and zero for actions done in all the other squares.</p>
  
  <p>With this in mind, what is the value of a square (1,1)?</p>
  
  <p>The correct answer is supposed to be 5, and is calculated as <span class="math-container">$1/(1\cdot 0.2) = 5$</span>. But why is that? I didn't manage to find any explanation on the net, so I am asking here. </p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-13T16:43:48.650Z
Comments.Text: Hi Milan and welcome to AI Stack Exchange! This is a fun question! I think two clarifications would be helpful. (1) Are the dynamics of the environment deterministic - i.e. when taking an action, is the agent guaranteed to move in that direction, or is there some randomness/uncertainty? (2) The value function is dependent on a given policy. Did you have a particular policy in mind (e.g. random or optimal)? Based on the supposed correct answer you provided, I think the answers to these questions are (1) yes (2) optimal, but I just want to be sure. Thanks!
Comments.UserDisplayName: DeepQZero
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-13T19:23:49.997Z
Comments.Text: Yes, enviroment is deterministic, and policy is optimal. Sorry for omitting that. And thanks for welcome.
Comments.UserDisplayName: Milan Mitterko
Tags: <reinforcement-learning><markov-decision-process><value-functions><value-iteration><discount-factor>
Title: What is the value of a state when there is a certain probability that agent will die after each step?
UserDisplayName: Milan Mitterko
ThreadText: # What is the value of a state when there is a certain probability that agent will die after each step?
  
  (Asked by: username_0 on 2020-06-13)
  
  We assume infinite horizon and discount factor $\gamma = 1$. At each step, after the agent takes an action and gets its reward, there is a probability $\alpha = 0.2$, that agent will die. The assumed maze looks like this
  
  [![enter image description here](https://i.sstatic.net/vTe5M.png)](https://i.sstatic.net/vTe5M.png)
  
  Possible actions are go left, right, up, down or stay in a square. The reward has a value 1 for any action done in the square (1,1) and zero for actions done in all the other squares.
  
  With this in mind, what is the value of a square (1,1)?
  
  The correct answer is supposed to be 5, and is calculated as $1/(1\cdot 0.2) = 5$. But why is that? I didn't manage to find any explanation on the net, so I am asking here.
  
  **Tags:** reinforcement-learning, markov-decision-process, value-functions, value-iteration, discount-factor
  > **Comments:**
  > **username_1**: Hi Milan and welcome to AI Stack Exchange! This is a fun question! I think two clarifications would be helpful. (1) Are the dynamics of the environment deterministic - i.e. when taking an action, is the agent guaranteed to move in that direction, or is there some randomness/uncertainty? (2) The value function is dependent on a given policy. Did you have a particular policy in mind (e.g. random or optimal)? Based on the supposed correct answer you provided, I think the answers to these questions are (1) yes (2) optimal, but I just want to be sure. Thanks!  
  > **username_0**: Yes, enviroment is deterministic, and policy is optimal. Sorry for omitting that. And thanks for welcome.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2020-06-13. Score: 2 | Accepted answer
  
  I will fill in some details in shaabhishek's answer for people who are interested.
  
  > With this in mind, what is the value of a square (1,1)?
  
  First of all, the value function is dependent on a policy. The supposed correct answer you provided is the value of $(1, 1)$ under the *optimal* policy, so from now on, we will assume that we are finding the value function under the optimal policy. Also, we will assume that the environment dynamics are deterministic: choosing to take an action will guarantee that the agent moves in that direction.
  
  > Possible actions are go left, right, up, down or stay in a square. Reward has a value 1 for any action done in square (1,1) and zero for actions done in all the other squares.
  
  Based on this information, the optimal policy at $(1, 1)$ should be to always stay in that square. The agent doesn't receive any reward for being in another square, and the probability of dying is the same for each square, so choosing the action to stay in square $(1, 1)$ is best.
  
  > The correct answer is supposed to be 5, and is calculated as $\frac{1}{1 \cdot 0.2} = 5$. But why is that?
  
  By the Bellman Equation, the value function under the optimal policy $\pi\_\*$ at $(1,1)$ can be written as follows:
  
  $$v\_{\pi\_\*}((1, 1)) = \mathbb{E}\_{\pi\_\*}\left[R\_t + \gamma v\_{\pi\_{\*}}(s') | s = (1,1)\right],$$
  
  where $R\_t$ denotes the immediate reward, $s$ denotes the current state, and $s'$ denotes the next state. By the problem statement, $\gamma = 1$. The next state is the $\texttt{dead}$ terminal state $\alpha = 20\%$ of the time. Terminal states have value $0$, as they do not accrue future rewards. The next state $s'$ is equal to $(1, 1)$ the remaining $(1-\alpha) = 80\%$ of the time because our policy dictates to remain in the same state and we assumed the dynamics were deterministic. Since expectation is linear, we can rewrite the expectation as follows (replacing $\gamma$ with $1$):
  
  \begin{align\*}
  v\_{\pi\_\*}((1,1)) &= \mathbb{E}\_{\pi\_\*}\left[R\_t + v\_{\pi\_{\*}}(s') | s = (1,1)\right]\\
  &= \mathbb{E}\_{\pi\_\*}\left[R\_t |s=(1, 1)\right]+ \mathbb{E}\_{\pi\_\*}\left[v\_{\pi\_{\*}}(s') | s = (1,1)\right].\qquad (\*)
  \end{align\*}
  
  We have
  
  $$\mathbb{E}\_{\pi\_\*}\left[R\_t |s=(1, 1)\right] = 1\qquad (\*\*)$$
  
  because we are guaranteed an immediate reward of $1$ when taking an action in state $(1, 1)$. Also, from the comments above regarding the next state values and probabilities, we have the following:
  
  \begin{align\*}\mathbb{E}\_{\pi\_\*}\left[v\_{\pi\_{\*}}(s') | s = (1,1)\right] &= (1-\alpha) \cdot v\_{\pi\_{\*}}((1,1)) + \alpha \cdot v\_{\pi\_\*}(\texttt{dead})\\
  &= 0.8 \cdot v\_{\pi\_{\*}}((1,1)) + 0.2 \cdot 0\\
  &= 0.8 \cdot v\_{\pi\_{\*}}((1,1)).\qquad (\*\*\*)
  \end{align\*}
  
  Substituting $(\*\*)$ and $(\*\*\*)$ into $(\*)$ yields the following:
  
  \begin{align\*}
  v\_{\pi\_\*}((1,1)) &= 1 + 0.8 \cdot v\_{\pi\_{\*}}((1,1))\\
  v\_{\pi\_\*}((1,1)) - 0.8 \cdot v\_{\pi\_{\*}}((1,1)) &= 1\\
  (1-0.8)v\_{\pi\_\*}((1,1)) &= 1\\
  v\_{\pi\_\*}((1,1)) &= \frac{1}{1-0.8} = \frac{1}{0.2} = 5.
  \end{align\*}
  
  
  ---
  
  ### Answer by username_2 on 2020-06-13. Score: 3
  
  The value of a state depends on the policy that you use, so I'll make the assumption here that you're talking about value **using the optimal policy**.
  
  *According to the optimal policy, the agent would choose to stay in the square (1,1) every time*, but since it has a 0.8 probability of actually staying (and 0.2 probability of dying), we can compute the value of the agent using the Bellman equation as:
  
  $$
  V(1,1) = 1 + 0.8 V(1,1) + 0.2 V(\text{death state}) \\
  \implies V(1,1) = 1 + 0.8 V(1,1) \\
  \implies V(1,1) = \frac{1}{1 - 0.8} \\
  \implies V(1,1) = 5
  $$
  
  There are other ways of deriving the same number (value function has multiple definitions) but they are equivalent.
  
  
  ---
  
  