Answers.Body: <blockquote>
    <p>If <span class="math-container">$\pi$</span> is a random policy, and after running through this algorithm, and for each state take the <span class="math-container">$\max Q(s,a)$</span> for all possible actions, why would that not be equal to <span class="math-container">$Q_{\pi^*}(s, a)$</span> (optimal Q function)? </p>
  </blockquote>
  
  <p>Assuming that the estimates for <span class="math-container">$Q_{\pi}(s,a)$</span> have converged to close to correct values from many samples, then a policy based on <span class="math-container">$\pi'(s) = \text{argmax}_a Q_{\pi}(s,a)$</span> is not guaranteed to be an optimal policy <em>unless</em> the policy <span class="math-container">$\pi$</span> being measured is <em>already</em> the optimal policy.</p>
  
  <p>This is because the action value <span class="math-container">$Q_{\pi}(s,a)$</span> gives the expected future reward from taking action <span class="math-container">$a$</span> in state <span class="math-container">$s$</span>, and from that point on following the policy <span class="math-container">$\pi$</span>. The function does not, by itself, adapt to the idea that you might change other action choices as well. It is a measure of <em>immediate</em> differences between action choices at any given time step. Therefore if there are any long-term dependencies where your action choice at <span class="math-container">$t$</span> would be different if only you could guarantee a certain choice at <span class="math-container">$t+1$</span> or later, this cannot be resolved by simply taking the maximum <span class="math-container">$Q_{\pi}(s,a)$</span> when <span class="math-container">$\pi$</span> was a simple random policy.</p>
  
  <p>However, if you do decide to change the policy such that you always follow actions <span class="math-container">$\pi'(s) = \text{argmax}_a Q_{\pi}(s,a)$</span> for all states, then you can say this: <em>For each state, <span class="math-container">$V_{\pi'}(s) \ge V_{\pi}(s)$</span>.</em> I.e.  <span class="math-container">$\pi'(s)$</span> is no worse than, and may be a strict improvement over <span class="math-container">$\pi(s)$</span>. Better than that, <span class="math-container">$\pi'(s)$</span> will be a strict improvment over <span class="math-container">$\pi(s)$</span> if <span class="math-container">$Q_{\pi}(s,a)$</span> is accurate and <span class="math-container">$\pi(s)$</span> is not already the optimal policy <span class="math-container">$\pi^*(s)$</span>. This is the basis for the <a href="http://incompleteideas.net/book/first/ebook/node42.html" rel="nofollow noreferrer">Policy Improvement Theorem</a> which shows that if you repeat the process of measuring <span class="math-container">$Q_{\pi^k}$</span> and then creating a new policy <span class="math-container">$\pi^{k+1}(s) = \text{argmax}_a Q_{\pi^k}(s,a)$</span> that you will eventually find the optimal policy. You only have to repeat your idea many times to eventually find <span class="math-container">$\pi^*$</span></p>
  
  <p>The Dynamic Programming technique Policy Iteration does this exactly. All other value-based Reinforcement Learning methods are variations of this idea and rely at least in part on this proof.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-16T13:42:39.803Z
Answers.Text: Hey Neil, thanks for answering ! I think I have a clearer understanding of why it is not Q opt ! What do you mean in the second paragraph when you say “stuck measuring immediate differences between ... “ from that point onwards up till the end of the paragraph ?
Answers.UserDisplayName: calveeen
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-16T15:21:26.627Z
Answers.Text: I have one more question regarding the last paragraph where you talk about policy iteration. Policy iteration does not necessarily output Q opt in the case where not all actions are explored when following a policy pi, am i right ? If we take the case of a grid problem, where we can move "up" , " down", "left" and "right", then if our current policy specifies move only "right" for cell number (1,1), we would only get the Q value for action move "right", at the end of the whole monte carlo simulation and there would be no way to update the policy for cell number (1,1) ?
Answers.UserDisplayName: calveeen
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-16T16:01:13.150Z
Answers.Text: @calveen: Policy Iteration from Dynamic Programming explores all state.action pairs. That means it doesn't scale well. However, it is theoretically solid. The example you are asking about is a Monte Carlo updates - these approach optimal policy in a more stochastic way over time. To do that you need to add some randomness - typically epsilon greedy policies, so that sometimes the agent will take a different action than the polciy derived by taking the maximisiing action, and learn about the other directions
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-16T16:04:52.540Z
Answers.Text: @calveen: In my second paragraph I am trying to cover that accurate Q(s,a) gives only a one step look ahead. It does not measure longer-term effects. That's what I meant by "stuck" - just that the values do not change instantly for $Q_{\pi}(s_2,*)$ solely because you changed your policy choice when looking at  $Q_{\pi}(s_1,*)$. You need to make that policy change for real (or in simulation) and then re-estimate your Q values after using it for a while
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-16T09:40:33.220Z
Answers.LastActivityDate: 2020-01-19T08:46:11.137Z
Answers.LastEditDate: 2020-01-19T08:46:11.137Z
Answers.UserDisplayName: Neil Slater
Body: <p>I am new to Reinforcement learning and am currently reading up on the estimation of Q <span class="math-container">$\pi(s, a)$</span> values using MC epsilon-soft approach and chanced upon this algorithm. The link to the algorithm is found from this website. </p>
  
  <p><a href="https://www.analyticsvidhya.com/blog/2018/11/reinforcement-learning-introduction-monte-carlo-learning-openai-gym/" rel="nofollow noreferrer">https://www.analyticsvidhya.com/blog/2018/11/reinforcement-learning-introduction-monte-carlo-learning-openai-gym/</a></p>
  
  <pre><code>def monte_carlo_e_soft(env, episodes=100, policy=None, epsilon=0.01):
  
  if not policy:
      policy = create_random_policy(env)
  # Create an empty dictionary to store state action values
  Q = create_state_action_dictionary(env, policy)
  
  # Empty dictionary for storing rewards for each state-action pair
  returns = {} # 3.
  
  for _ in range(episodes): # Looping through episodes
      G = 0 # Store cumulative reward in G (initialized at 0)
      episode = run_game(env=env, policy=policy, display=False) # Store state, action and value respectively
  
      # for loop through reversed indices of episode array.
      # The logic behind it being reversed is that the eventual reward would be at the end.
      # So we have to go back from the last timestep to the first one propagating result from the future.
  
      # episodes = [[s1,a1,r1], [s2,a2,r2], ... [Sn, an, Rn]]
      for i in reversed(range(0, len(episode))):
          s_t, a_t, r_t = episode[i]
          state_action = (s_t, a_t)
          G += r_t # Increment total reward by reward on current timestep
  
          # if state - action pair not found in the preceeding episodes,
          # then this is the only time the state appears in this episode.
  
          if not state_action in [(x[0], x[1]) for x in episode[0:i]]: #
              # if returns dict contains a state action pair from prev episodes,
              # append the curr reward to this dict
              if returns.get(state_action):
                  returns[state_action].append(G)
              else:
                  # create new dictionary entry with reward
                  returns[state_action] = [G]
  
              # returns is a dictionary that maps (s,a) : [G1,G2, ...]
              # Once reward is found for this state in current episode,
              # average the reward.
              Q[s_t][a_t] = sum(returns[state_action]) / len(returns[state_action]) # Average reward across episodes
  
              # Finding the action with maximum value.
  
  
  
              Q_list = list(map(lambda x: x[1], Q[s_t].items()))
              indices = [i for i, x in enumerate(Q_list) if x == max(Q_list)]
              max_Q = random.choice(indices)
  
              A_star = max_Q # 14.
  
              # Update action probability for s_t in policy
              for a in policy[s_t].items():
                  if a[0] == A_star:
                      policy[s_t][a[0]] = 1 - epsilon + (epsilon / abs(sum(policy[s_t].values())))
                  else:
                      policy[s_t][a[0]] = (epsilon / abs(sum(policy[s_t].values())))
  
  return policy
  </code></pre>
  
  <p>This algorithm computes the <span class="math-container">$Q(s, a)$</span> for all state action value pairs that the policy follows. If <span class="math-container">$\pi$</span> is a random policy, and after running through this algorithm, and for each state take the <span class="math-container">$\max Q(s,a)$</span> for all possible actions, why would that not be equal to <span class="math-container">$Q_{\pi^*}(s, a)$</span> (optimal Q function)? </p>
  
  <p>From this website, they claim to have been able to find the optimal policy when running through this algorithm.</p>
  
  <p>I have read up a bit on Q-learning and the update equation is different from MC epsilon-soft. However, I can't seem to understand clearly how these 2 approaches are different. </p>
  
Tags: <reinforcement-learning><q-learning><monte-carlo-methods>
Title: Why Monte Carlo epsilon-soft approach cannot compute $\max Q(s,a)$?
UserDisplayName: calveeen
ThreadText: # Why Monte Carlo epsilon-soft approach cannot compute $\max Q(s,a)$?
  
  (Asked by: username_0 on 2020-01-16)
  
  I am new to Reinforcement learning and am currently reading up on the estimation of Q $\pi(s, a)$ values using MC epsilon-soft approach and chanced upon this algorithm. The link to the algorithm is found from this website.
  
  <https://www.analyticsvidhya.com/blog/2018/11/reinforcement-learning-introduction-monte-carlo-learning-openai-gym/>
  
  ```
  def monte_carlo_e_soft(env, episodes=100, policy=None, epsilon=0.01):
  
  if not policy:
      policy = create_random_policy(env)
  # Create an empty dictionary to store state action values
  Q = create_state_action_dictionary(env, policy)
  
  # Empty dictionary for storing rewards for each state-action pair
  returns = {} # 3.
  
  for _ in range(episodes): # Looping through episodes
      G = 0 # Store cumulative reward in G (initialized at 0)
      episode = run_game(env=env, policy=policy, display=False) # Store state, action and value respectively
  
      # for loop through reversed indices of episode array.
      # The logic behind it being reversed is that the eventual reward would be at the end.
      # So we have to go back from the last timestep to the first one propagating result from the future.
  
      # episodes = [[s1,a1,r1], [s2,a2,r2], ... [Sn, an, Rn]]
      for i in reversed(range(0, len(episode))):
          s_t, a_t, r_t = episode[i]
          state_action = (s_t, a_t)
          G += r_t # Increment total reward by reward on current timestep
  
          # if state - action pair not found in the preceeding episodes,
          # then this is the only time the state appears in this episode.
  
          if not state_action in [(x[0], x[1]) for x in episode[0:i]]: #
              # if returns dict contains a state action pair from prev episodes,
              # append the curr reward to this dict
              if returns.get(state_action):
                  returns[state_action].append(G)
              else:
                  # create new dictionary entry with reward
                  returns[state_action] = [G]
  
              # returns is a dictionary that maps (s,a) : [G1,G2, ...]
              # Once reward is found for this state in current episode,
              # average the reward.
              Q[s_t][a_t] = sum(returns[state_action]) / len(returns[state_action]) # Average reward across episodes
  
              # Finding the action with maximum value.
  
              Q_list = list(map(lambda x: x[1], Q[s_t].items()))
              indices = [i for i, x in enumerate(Q_list) if x == max(Q_list)]
              max_Q = random.choice(indices)
  
              A_star = max_Q # 14.
  
              # Update action probability for s_t in policy
              for a in policy[s_t].items():
                  if a[0] == A_star:
                      policy[s_t][a[0]] = 1 - epsilon + (epsilon / abs(sum(policy[s_t].values())))
                  else:
                      policy[s_t][a[0]] = (epsilon / abs(sum(policy[s_t].values())))
  
  return policy
  
  ```
  
  This algorithm computes the $Q(s, a)$ for all state action value pairs that the policy follows. If $\pi$ is a random policy, and after running through this algorithm, and for each state take the $\max Q(s,a)$ for all possible actions, why would that not be equal to $Q\_{\pi^\*}(s, a)$ (optimal Q function)?
  
  From this website, they claim to have been able to find the optimal policy when running through this algorithm.
  
  I have read up a bit on Q-learning and the update equation is different from MC epsilon-soft. However, I can't seem to understand clearly how these 2 approaches are different.
  
  **Tags:** reinforcement-learning, q-learning, monte-carlo-methods
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-01-16. Score: 2 | Accepted answer
  
  > If $\pi$ is a random policy, and after running through this algorithm, and for each state take the $\max Q(s,a)$ for all possible actions, why would that not be equal to $Q\_{\pi^\*}(s, a)$ (optimal Q function)?
  
  Assuming that the estimates for $Q\_{\pi}(s,a)$ have converged to close to correct values from many samples, then a policy based on $\pi'(s) = \text{argmax}\_a Q\_{\pi}(s,a)$ is not guaranteed to be an optimal policy *unless* the policy $\pi$ being measured is *already* the optimal policy.
  
  This is because the action value $Q\_{\pi}(s,a)$ gives the expected future reward from taking action $a$ in state $s$, and from that point on following the policy $\pi$. The function does not, by itself, adapt to the idea that you might change other action choices as well. It is a measure of *immediate* differences between action choices at any given time step. Therefore if there are any long-term dependencies where your action choice at $t$ would be different if only you could guarantee a certain choice at $t+1$ or later, this cannot be resolved by simply taking the maximum $Q\_{\pi}(s,a)$ when $\pi$ was a simple random policy.
  
  However, if you do decide to change the policy such that you always follow actions $\pi'(s) = \text{argmax}\_a Q\_{\pi}(s,a)$ for all states, then you can say this: *For each state, $V\_{\pi'}(s) \ge V\_{\pi}(s)$.* I.e. $\pi'(s)$ is no worse than, and may be a strict improvement over $\pi(s)$. Better than that, $\pi'(s)$ will be a strict improvment over $\pi(s)$ if $Q\_{\pi}(s,a)$ is accurate and $\pi(s)$ is not already the optimal policy $\pi^\*(s)$. This is the basis for the [Policy Improvement Theorem](http://incompleteideas.net/book/first/ebook/node42.html) which shows that if you repeat the process of measuring $Q\_{\pi^k}$ and then creating a new policy $\pi^{k+1}(s) = \text{argmax}\_a Q\_{\pi^k}(s,a)$ that you will eventually find the optimal policy. You only have to repeat your idea many times to eventually find $\pi^\*$
  
  The Dynamic Programming technique Policy Iteration does this exactly. All other value-based Reinforcement Learning methods are variations of this idea and rely at least in part on this proof.
  
  > **Comments:**
  > **username_0**: Hey username_1, thanks for answering ! I think I have a clearer understanding of why it is not Q opt ! What do you mean in the second paragraph when you say “stuck measuring immediate differences between ... “ from that point onwards up till the end of the paragraph ?  
  > **username_0**: I have one more question regarding the last paragraph where you talk about policy iteration. Policy iteration does not necessarily output Q opt in the case where not all actions are explored when following a policy pi, am i right ? If we take the case of a grid problem, where we can move "up" , " down", "left" and "right", then if our current policy specifies move only "right" for cell number (1,1), we would only get the Q value for action move "right", at the end of the whole monte carlo simulation and there would be no way to update the policy for cell number (1,1) ?  
  > **username_1**: @calveen: Policy Iteration from Dynamic Programming explores all state.action pairs. That means it doesn't scale well. However, it is theoretically solid. The example you are asking about is a Monte Carlo updates - these approach optimal policy in a more stochastic way over time. To do that you need to add some randomness - typically epsilon greedy policies, so that sometimes the agent will take a different action than the polciy derived by taking the maximisiing action, and learn about the other directions  
  > **username_1**: @calveen: In my second paragraph I am trying to cover that accurate Q(s,a) gives only a one step look ahead. It does not measure longer-term effects. That's what I meant by "stuck" - just that the values do not change instantly for $Q_{\pi}(s_2,*)$ solely because you changed your policy choice when looking at  $Q_{\pi}(s_1,*)$. You need to make that policy change for real (or in simulation) and then re-estimate your Q values after using it for a while  
  
  ---
  
  