3
$\begingroup$

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

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – DeepQZero Jun 13 at 16:43
  • $\begingroup$ Yes, enviroment is deterministic, and policy is optimal. Sorry for omitting that. And thanks for welcome. $\endgroup$ – Milan Mitterko Jun 13 at 19:23
  • $\begingroup$ How is this different from decreasing the discount factor by $\alpha$? $\endgroup$ – user76284 Jun 14 at 3:20
2
$\begingroup$

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*}

| improve this answer | |
$\endgroup$
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.