What is the value of a state when there is a certain probability that agent will die after each step?

Question

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

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.

Answer 1

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 2

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.