Answers.Body: <blockquote>
  <p>After trying to understand what was happening by going through the algorithm on paper (below), I found all values were the same, so greedifying with respect to the value function often just had the agent going around in circles. Reducing the discount factor from 1 to anything below 1 gave me 100 percent success.</p>
  </blockquote>
  <p>This is expected (and optimal, as defined) behaviour with a discount factor of 1 in the deterministic case. With a reward of 1 at the end, no discounting and and no negative rewards for taking its time, the agent has infinite time to complete the task. So whatever it does, provided it does not step into a hole at any point, is optimal.</p>
  <p>The caveat is that when following the policy as a test, you need to use random choice to resolve ties (this is assumed in the theory behind value iteration, that the agent can reach the high rewards). Most simple argmax functions will not do that, so you will need to add some kind of shuffle or other random selection over the maximum results to ensure you are really following the policy that value iteration discovered the state value function for.</p>
  <p>The last sentence in the pseudocode is ignoring the possibility that you have this kind of situation, so it is not strictly true in all cases. That is, you cannot reliably build a working deterministic policy directly from the optimal value function when <span class="math-container">$\gamma=1$</span> for environments like Frozen Lake.</p>
  <blockquote>
  <p>But going to anything below 0.9 gave me worse results in the slippery case.</p>
  </blockquote>
  <p>I am less sure about what is happening in this case. Given that you successfully found an optimal value function in the deterministic environment, then this may actually be optimal too. Whether or not it is may depend on the map - an optimal agent with low discount factor may prefer not to &quot;run a gauntlet&quot; early with risk of failure even if the overall probability of success is better. That may cause it to prefer a safer start that leads to a tougher end, where it is forced to take more risks overall than would be optimal for a goal of completing the most episodes.</p>
  <blockquote>
  <p>how to interpret and choose the discount factor for any use case?</p>
  </blockquote>
  <p>The discount factor is not a free choice for the agent, and it is not a hyperparameter for the learning method in value iteration. Instead, it is part of the definion for what is and isn't optimal. So you should select it based on the problem definition.</p>
  <p>In an episodic environment where the agent's goal is to reach a certain state or states as fast as possible, there are two &quot;natural&quot; formulations:</p>
  <ul>
  <li><p>Zero reward for most transitions, &quot;goal&quot; rewards for reaching certain terminal states, and a discount factor below <span class="math-container">$1$</span>. I think your choice of <span class="math-container">$0.9$</span> would be fine, and it is commonly used in the literature for this kind of toy environment.</p>
  </li>
  <li><p>Negative reward for most transitions, &quot;goal&quot; rewards for reaching certain terminal states. If there is a single &quot;target&quot; state, such as exiting a maze, the &quot;goal&quot; reward can be zero. Usually no discounting, but you could add discounting if it represents something else about the problem.</p>
  </li>
  </ul>
  <p>In more complex systems, the discount factor may <em>also</em> become a hyperparameter of the agent. For instance, it does so when using function approximation with temporal difference learning, because it can dampen positive feedback from bootstrapping. In those cases, where &quot;naturally&quot; there would be no discounting, then you may want to use the highest value that prevents the estimator diverging e.g. <span class="math-container">$\gamma = 0.99$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-20T10:31:40.390Z
Answers.LastActivityDate: 2022-05-21T08:01:03.250Z
Answers.LastEditDate: 2022-05-21T08:01:03.250Z
Answers.UserDisplayName: Neil Slater
Body: <p>I was working with FrozenLake 4x4 from open AI gym. In the slippery case, using a discounting factor of 1, my value iteration implementation was giving a success rate of around 75 percent. It was much worse for the 8x8 grid with success around 50%. I thought in the non slippery case, it should definitely give me 100 percent success, but it turned out to be 0 percent.</p>
  <p>After trying to understand what was happening by going through the algorithm on paper (below), I found all values were the same, so greedifying with respect to the value function often just had the agent going around in circles. Reducing the discount factor from 1 to anything below 1 gave me 100 percent success. But going to anything below 0.9 gave me worse results in the slippery case.</p>
  <p>Can someone give me some intuition as to why this happened and how to interpret and choose the discount factor for any use case?</p>
  <p>Algorithm used (where <span class="math-container">$\theta = 0.0000001$</span>):</p>
  <p><a href="https://i.sstatic.net/sUWwN.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/sUWwN.png" alt="enter image description here" /></a></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-20T07:03:02.687Z
Comments.Text: Could you please refernce the exact algorithm you used - e.g. tabular Q-learning - plus any other hyperparameters that you set? The learning rate especially is going to interact with the discount rate to determine stability.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-20T09:03:03.297Z
Comments.Text: Hello @NeilSlater, I have updated the question with the algorithm used and I only set one additional parameter theta = 0.0000001
Comments.UserDisplayName: ketan dhanuka
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-20T09:09:52.687Z
Comments.Text: Value iteration requires a model of the environment - i.e. the state transition probabilities. Gym doesn't give you those via the normal API - how are you getting them?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-20T09:20:46.523Z
Comments.Text: I get them from the API itself. For this particular environment the API gives the state transition probabilities
Comments.UserDisplayName: ketan dhanuka
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-20T09:28:56.913Z
Comments.Text: Do you mean the info block returned *after* taking the action in the `.step` method? How are you iterating the states?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-20T09:35:09.457Z
Comments.Text: No I am not using the step method. It is an attribute of the environment object itself. Calling env.P[s][a] returns the Probability of transitioning to state s_dash from s after taking action a along with the return.
  The states are just indexed from 0 to 15 so I am iterating over them using a simple for loop.
Comments.UserDisplayName: ketan dhanuka
Tags: <reinforcement-learning><sutton-barto><value-iteration><discount-factor><frozen-lake>
Title: What should the discount factor for the non-slippery version of the FrozenLake environment be?
UserDisplayName: ketan dhanuka
ThreadText: # What should the discount factor for the non-slippery version of the FrozenLake environment be?
  
  (Asked by: username_0 on 2022-05-20)
  
  I was working with FrozenLake 4x4 from open AI gym. In the slippery case, using a discounting factor of 1, my value iteration implementation was giving a success rate of around 75 percent. It was much worse for the 8x8 grid with success around 50%. I thought in the non slippery case, it should definitely give me 100 percent success, but it turned out to be 0 percent.
  
  After trying to understand what was happening by going through the algorithm on paper (below), I found all values were the same, so greedifying with respect to the value function often just had the agent going around in circles. Reducing the discount factor from 1 to anything below 1 gave me 100 percent success. But going to anything below 0.9 gave me worse results in the slippery case.
  
  Can someone give me some intuition as to why this happened and how to interpret and choose the discount factor for any use case?
  
  Algorithm used (where $\theta = 0.0000001$):
  
  [![enter image description here](https://i.sstatic.net/sUWwN.png)](https://i.sstatic.net/sUWwN.png)
  
  **Tags:** reinforcement-learning, sutton-barto, value-iteration, discount-factor, frozen-lake
  
  > **Comments:**
  > **username_1**: Could you please refernce the exact algorithm you used - e.g. tabular Q-learning - plus any other hyperparameters that you set? The learning rate especially is going to interact with the discount rate to determine stability.  
  > **username_0**: Hello @username_1, I have updated the question with the algorithm used and I only set one additional parameter theta = 0.0000001  
  > **username_1**: Value iteration requires a model of the environment - i.e. the state transition probabilities. Gym doesn't give you those via the normal API - how are you getting them?  
  > **username_0**: I get them from the API itself. For this particular environment the API gives the state transition probabilities  
  > **username_1**: Do you mean the info block returned *after* taking the action in the `.step` method? How are you iterating the states?  
  > **username_0**: No I am not using the step method. It is an attribute of the environment object itself. Calling env.P[s][a] returns the Probability of transitioning to state s_dash from s after taking action a along with the return. The states are just indexed from 0 to 15 so I am iterating over them using a simple for loop.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-05-20. Score: 3 | Accepted answer
  
  > After trying to understand what was happening by going through the algorithm on paper (below), I found all values were the same, so greedifying with respect to the value function often just had the agent going around in circles. Reducing the discount factor from 1 to anything below 1 gave me 100 percent success.
  
  This is expected (and optimal, as defined) behaviour with a discount factor of 1 in the deterministic case. With a reward of 1 at the end, no discounting and and no negative rewards for taking its time, the agent has infinite time to complete the task. So whatever it does, provided it does not step into a hole at any point, is optimal.
  
  The caveat is that when following the policy as a test, you need to use random choice to resolve ties (this is assumed in the theory behind value iteration, that the agent can reach the high rewards). Most simple argmax functions will not do that, so you will need to add some kind of shuffle or other random selection over the maximum results to ensure you are really following the policy that value iteration discovered the state value function for.
  
  The last sentence in the pseudocode is ignoring the possibility that you have this kind of situation, so it is not strictly true in all cases. That is, you cannot reliably build a working deterministic policy directly from the optimal value function when $\gamma=1$ for environments like Frozen Lake.
  
  > But going to anything below 0.9 gave me worse results in the slippery case.
  
  I am less sure about what is happening in this case. Given that you successfully found an optimal value function in the deterministic environment, then this may actually be optimal too. Whether or not it is may depend on the map - an optimal agent with low discount factor may prefer not to "run a gauntlet" early with risk of failure even if the overall probability of success is better. That may cause it to prefer a safer start that leads to a tougher end, where it is forced to take more risks overall than would be optimal for a goal of completing the most episodes.
  
  > how to interpret and choose the discount factor for any use case?
  
  The discount factor is not a free choice for the agent, and it is not a hyperparameter for the learning method in value iteration. Instead, it is part of the definion for what is and isn't optimal. So you should select it based on the problem definition.
  
  In an episodic environment where the agent's goal is to reach a certain state or states as fast as possible, there are two "natural" formulations:
  
  * Zero reward for most transitions, "goal" rewards for reaching certain terminal states, and a discount factor below $1$. I think your choice of $0.9$ would be fine, and it is commonly used in the literature for this kind of toy environment.
  * Negative reward for most transitions, "goal" rewards for reaching certain terminal states. If there is a single "target" state, such as exiting a maze, the "goal" reward can be zero. Usually no discounting, but you could add discounting if it represents something else about the problem.
  
  In more complex systems, the discount factor may *also* become a hyperparameter of the agent. For instance, it does so when using function approximation with temporal difference learning, because it can dampen positive feedback from bootstrapping. In those cases, where "naturally" there would be no discounting, then you may want to use the highest value that prevents the estimator diverging e.g. $\gamma = 0.99$.
  
  
  ---
  
  