Answers.Body: <blockquote>
  <p>What am I missing here?</p>
  </blockquote>
  <p>You are not missing anything mathematically.</p>
  <p>Potentially what you are missing is that the discount factor <span class="math-container">$\gamma$</span>, is part of the <em>problem definition</em>. In reinforcement learning (RL), you do not always solve problems to obtain the highest total sum of rewards. Instead you solve problems to obtain the highest expected return on any action. If you use a discount factor, then it affects the return calculation, which in turn may affect which behaviours are optimal.</p>
  <p>If you choose <span class="math-container">$gamma$</span> such that an agent would move away from a terminal state to receive the highest expected return, then you have defined the problem such that this behaviour is optimal.</p>
  <p>This can be an issue when solving RL problems and you have taken a free choice for reward functions and definition of return (this is quite common, often it is the researcher's problem to set these values up to define the agent's goals). Often you can use a discount factor to make a problem more numerically stable, because it will keep sums of rewards over many time steps within bounds. Also, it can be used as a way to search for faster solutions - i.e. in less time steps to reach episode end - because the agent will prioritise reaching higher values sooner if it can. Your example MDP deliberately puts those two effects in opposition to each other.</p>
  <p>Assuming you want the agent to find the terminal state by getting over the larger negative reward just before it: Probably you should not use a discount factor for your MDP. Alternatively, if the reward signal is more of a free choice for that problem, you could offset it (by <span class="math-container">$+0.1$</span>) and then most values of discount factor will still resolve to reaching the terminal state as optimal behaviour.</p>
  <p>There are a few common ways to mitigate or avoid the issue of changing problem definition by selecting <span class="math-container">$\gamma$</span>:</p>
  <ul>
  <li><p>Use a value of <span class="math-container">$\gamma$</span> derived from the problem. In some cases, the value of <span class="math-container">$\gamma$</span> is a realistic physical part of a problem. For instance in financial problems, cash now is often preferable to cash later.</p>
  </li>
  <li><p>Set <span class="math-container">$\gamma$</span> to relavtively high value, such as <span class="math-container">$0.99$</span> or <span class="math-container">$0.999$</span>, depending on episode length and relative sizes of rewards. This can work well enough for a wide range of problems. It is a common solution when using DQN. Effectively this approximates the next approach (average rewards) for a low cost.</p>
  </li>
  <li><p>Use <a href="https://link.springer.com/article/10.1007/BF00114727" rel="nofollow noreferrer">average reward settings</a>. There are separate Bellman equations, TD updates etc based on maximising expected average reward per time step as opposed to maximising expected discounted return.</p>
  </li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-03T09:57:10.233Z
Answers.Text: Thank you for the input. However, I believe with this MDP, value iteration will converge to the optimal policy even with a discount factor of 0. Im not 100% sure yet about 0 but anything above 0 it will converge.
Answers.UserDisplayName: Paternostro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-03T12:50:17.837Z
Answers.Text: @Paternostro Yes it will converge. But it may be a *different* optimal policy, because by changing $\gamma$ you have changed what it means to be optimal.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-03T14:34:01.133Z
Answers.Text: I meant converging to the policy with the highest return. You're right about y changing what is optimal.
Answers.UserDisplayName: Paternostro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-03T09:10:21.020Z
Answers.LastActivityDate: 2021-04-03T09:24:53.757Z
Answers.LastEditDate: 2021-04-03T09:24:53.757Z
Answers.UserDisplayName: Neil Slater
Body: <p>When applying the bellman expectation equation:</p>
  <p><span class="math-container">$$v(s)=\mathbb{E}\left[R_{t+1}+\gamma v\left(S_{t+1}\right) \mid S_{t}=s\right]$$</span></p>
  <p>to the <strong>MRP</strong> below, states further away from the terminal state will have the same value <span class="math-container">${v(s)}$</span> as states closer to the terminal states. Even though it is clear that the expected total reward from states further away is lower. If the discount factor <span class="math-container">$\gamma$</span> would be even lower states further away would get a higher value. If we now make this an <strong>MDP</strong> where the agent can decide to go either direction from all states (with the first state having an action leading to itself), the agent would then choose to go further away from the terminal. Getting less reward over the whole episode. So, this seems to be an example where policy/value iteration would not converge to an optimal policy. I know there is something wrong with the reasoning here. I just cannot seem to figure out what.</p>
  <p>What am I missing here?
  <a href="https://i.sstatic.net/ZnnmD.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ZnnmD.png" alt="![enter image description here" /></a></p>
  <p>EDIT: So, the problem actually was that I didn't take into account that the terminal state has to get a value of 0. If you put it at 0 at all times this will converge as expected because all the other states will get lower and lower values while, assuming a greedy policy, the one-to-last state will retain a value of -1. After a bit over 10 iterations (if gamma is close to 1) it will converge because the states further away will get a value less than -1.</p>
  
Tags: <value-functions><bellman-equations><value-iteration><policy-iteration>
Title: Bellman Expectation Equation leading to results where value iteration would not converge to the optimal policy
UserDisplayName: Paternostro
ThreadText: # Bellman Expectation Equation leading to results where value iteration would not converge to the optimal policy
  
  (Asked by: username_0 on 2021-04-02)
  
  When applying the bellman expectation equation:
  
  $$v(s)=\mathbb{E}\left[R\_{t+1}+\gamma v\left(S\_{t+1}\right) \mid S\_{t}=s\right]$$
  
  to the **MRP** below, states further away from the terminal state will have the same value ${v(s)}$ as states closer to the terminal states. Even though it is clear that the expected total reward from states further away is lower. If the discount factor $\gamma$ would be even lower states further away would get a higher value. If we now make this an **MDP** where the agent can decide to go either direction from all states (with the first state having an action leading to itself), the agent would then choose to go further away from the terminal. Getting less reward over the whole episode. So, this seems to be an example where policy/value iteration would not converge to an optimal policy. I know there is something wrong with the reasoning here. I just cannot seem to figure out what.
  
  What am I missing here?
  [![![enter image description here](https://i.sstatic.net/ZnnmD.png)](https://i.sstatic.net/ZnnmD.png)
  
  EDIT: So, the problem actually was that I didn't take into account that the terminal state has to get a value of 0. If you put it at 0 at all times this will converge as expected because all the other states will get lower and lower values while, assuming a greedy policy, the one-to-last state will retain a value of -1. After a bit over 10 iterations (if gamma is close to 1) it will converge because the states further away will get a value less than -1.
  
  **Tags:** value-functions, bellman-equations, value-iteration, policy-iteration
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-04-03. Score: 1
  
  > What am I missing here?
  
  You are not missing anything mathematically.
  
  Potentially what you are missing is that the discount factor $\gamma$, is part of the *problem definition*. In reinforcement learning (RL), you do not always solve problems to obtain the highest total sum of rewards. Instead you solve problems to obtain the highest expected return on any action. If you use a discount factor, then it affects the return calculation, which in turn may affect which behaviours are optimal.
  
  If you choose $gamma$ such that an agent would move away from a terminal state to receive the highest expected return, then you have defined the problem such that this behaviour is optimal.
  
  This can be an issue when solving RL problems and you have taken a free choice for reward functions and definition of return (this is quite common, often it is the researcher's problem to set these values up to define the agent's goals). Often you can use a discount factor to make a problem more numerically stable, because it will keep sums of rewards over many time steps within bounds. Also, it can be used as a way to search for faster solutions - i.e. in less time steps to reach episode end - because the agent will prioritise reaching higher values sooner if it can. Your example MDP deliberately puts those two effects in opposition to each other.
  
  Assuming you want the agent to find the terminal state by getting over the larger negative reward just before it: Probably you should not use a discount factor for your MDP. Alternatively, if the reward signal is more of a free choice for that problem, you could offset it (by $+0.1$) and then most values of discount factor will still resolve to reaching the terminal state as optimal behaviour.
  
  There are a few common ways to mitigate or avoid the issue of changing problem definition by selecting $\gamma$:
  
  * Use a value of $\gamma$ derived from the problem. In some cases, the value of $\gamma$ is a realistic physical part of a problem. For instance in financial problems, cash now is often preferable to cash later.
  * Set $\gamma$ to relavtively high value, such as $0.99$ or $0.999$, depending on episode length and relative sizes of rewards. This can work well enough for a wide range of problems. It is a common solution when using DQN. Effectively this approximates the next approach (average rewards) for a low cost.
  * Use [average reward settings](https://link.springer.com/article/10.1007/BF00114727). There are separate Bellman equations, TD updates etc based on maximising expected average reward per time step as opposed to maximising expected discounted return.
  
  > **Comments:**
  > **username_0**: Thank you for the input. However, I believe with this MDP, value iteration will converge to the optimal policy even with a discount factor of 0. Im not 100% sure yet about 0 but anything above 0 it will converge.  
  > **username_1**: @username_0 Yes it will converge. But it may be a *different* optimal policy, because by changing $\gamma$ you have changed what it means to be optimal.  
  > **username_0**: I meant converging to the policy with the highest return. You're right about y changing what is optimal.  
  
  ---
  
  