Answers.Body: <p>The problem statement assumes that <span class="math-container">$\pi_i$</span> is <span class="math-container">$\epsilon$</span>-greedy. By definition (see section 5.4 of <a href="http://incompleteideas.net/book/the-book-2nd.html" rel="nofollow noreferrer">Sutton &amp; Barto</a>), an action is chosen uniformly randomly with probability <span class="math-container">$\epsilon$</span> at each time step; otherwise, the greedy action is chosen. Since there are <span class="math-container">$|A|$</span> actions, each action <span class="math-container">$a \in A$</span> has a <span class="math-container">$\frac{\epsilon}{|A|}$</span> probability of being chosen randomly at each time step. Therefore, <span class="math-container">$\pi_i(a|s) \ge \frac{\epsilon}{|A|}$</span> for all <span class="math-container">$a \in A$</span>, and the expression underlined in red can never be negative.</p>
  <p>In the case that <span class="math-container">$\epsilon = 1$</span>, both <span class="math-container">$\pi_i$</span> and <span class="math-container">$\pi_{i+1}$</span> will both choose actions uniformly randomly. Note that this &quot;improvement&quot; is still monotonic since <span class="math-container">$V^{\pi_i}=V^{\pi_{i+1}}$</span>, and equality is allowed in the definition of (non-strict) monotonicity.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-10-03T00:40:00.977Z
Answers.LastActivityDate: 2024-10-03T00:40:00.977Z
Answers.UserDisplayName: DeepQZero
Body: <p><a href="https://i.sstatic.net/7HAtodeK.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/7HAtodeK.png" alt="" /></a></p>
  <p>The picture is the shortcut from the Stanford CS234 RL course note. I have a question about the proof on the monotonic property of <span class="math-container">$\epsilon$</span>-greedy policies. In the red underlined expression, if some <span class="math-container">$\tilde{a} \in A$</span> makes the value of the red underlined expression less than 0, then shouldn't
  <span class="math-container">$$\frac{\pi_i(\tilde{a}|s)-\frac{\epsilon}{|A|}}{1-\epsilon} \max_{a'}Q^{\pi_i}(s, a') &lt; \frac{\pi_i(\tilde{a}|s)-\frac{\epsilon}{|A|}}{1-\epsilon} Q^{\pi_i}(s, \tilde{a})$$</span> be true? Specifically, the inequality sign needs to be reversed -- it's no longer &quot;greater than or equal to&quot;. Moreover, considering the scenario when <span class="math-container">$\epsilon$</span> tends to 1, which means we take uniformly random actions, why does the value function <span class="math-container">$V$</span> still have the monotonic improvement? Thanks.</p>
  
Tags: <reinforcement-learning><math><proofs><monte-carlo-methods>
Title: mathematics on monotonic e-greedy policy improvement
UserDisplayName: song
ThreadText: # mathematics on monotonic e-greedy policy improvement
  
  (Asked by: username_0 on 2024-09-28)
  
  [![](https://i.sstatic.net/7HAtodeK.png)](https://i.sstatic.net/7HAtodeK.png)
  
  The picture is the shortcut from the Stanford CS234 RL course note. I have a question about the proof on the monotonic property of $\epsilon$-greedy policies. In the red underlined expression, if some $\tilde{a} \in A$ makes the value of the red underlined expression less than 0, then shouldn't
  $$\frac{\pi\_i(\tilde{a}|s)-\frac{\epsilon}{|A|}}{1-\epsilon} \max\_{a'}Q^{\pi\_i}(s, a') < \frac{\pi\_i(\tilde{a}|s)-\frac{\epsilon}{|A|}}{1-\epsilon} Q^{\pi\_i}(s, \tilde{a})$$ be true? Specifically, the inequality sign needs to be reversed -- it's no longer "greater than or equal to". Moreover, considering the scenario when $\epsilon$ tends to 1, which means we take uniformly random actions, why does the value function $V$ still have the monotonic improvement? Thanks.
  
  **Tags:** reinforcement-learning, math, proofs, monte-carlo-methods
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-10-03. Score: 1 | Accepted answer
  
  The problem statement assumes that $\pi\_i$ is $\epsilon$-greedy. By definition (see section 5.4 of [Sutton & Barto](http://incompleteideas.net/book/the-book-2nd.html)), an action is chosen uniformly randomly with probability $\epsilon$ at each time step; otherwise, the greedy action is chosen. Since there are $|A|$ actions, each action $a \in A$ has a $\frac{\epsilon}{|A|}$ probability of being chosen randomly at each time step. Therefore, $\pi\_i(a|s) \ge \frac{\epsilon}{|A|}$ for all $a \in A$, and the expression underlined in red can never be negative.
  
  In the case that $\epsilon = 1$, both $\pi\_i$ and $\pi\_{i+1}$ will both choose actions uniformly randomly. Note that this "improvement" is still monotonic since $V^{\pi\_i}=V^{\pi\_{i+1}}$, and equality is allowed in the definition of (non-strict) monotonicity.
  
  
  ---
  
  