Answers.Body: <p>The quoted text is from the end of a paragraph that is explaining some aspects of bandit algorithms, and looking forward to how knowledge of them is applicable in a reinforcement learning context. Just before your quote, the relevant text is:</p>
  <blockquote>
  <p>For example, suppose the bandit task were nonstationary, that is, the true values of the actions changed over time. In this case exploration is needed even in the deterministic case to make sure one of the nongreedy actions has not changed to become better than the greedy one. As we shall see in the next few chapters, nonstationarity is the case most commonly encountered in reinforcement learning. Even if the underlying task [ . . . ]</p>
  </blockquote>
  <p>In particular, your quote is explaining that <em>deterministic</em> RL environments present a bit like a series of <em>non-stationary</em> bandit environments, because when a policy changes, it impacts the expected values of earlier actions, maybe to the point that an earlier &quot;best&quot; action choice needs to be changed.</p>
  <p>We can illustrate this with a simple deterministic RL environment. In the diagram, states are squares, actions circles, and rewards shown as labels on the next state transition.</p>
  <p><a href="https://i.sstatic.net/OVU1p.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/OVU1p.png" alt="Simple deterministic MDP" /></a></p>
  <p>You can look at the choices of action in states <span class="math-container">$s_0$</span>, <span class="math-container">$s_1$</span> and <span class="math-container">$s_2$</span>  as simple bandits. They have a choice between action <span class="math-container">$a_1$</span> or <span class="math-container">$a_2$</span>. There is some extra complexity, because the results from the choice in <span class="math-container">$s_0$</span> depend on the later choice in state <span class="math-container">$s_1$</span> or <span class="math-container">$s_2$</span>. This means that the optimal choice for the &quot;bandit&quot; at state <span class="math-container">$s_0$</span> depends on what the <em>current</em> choices will be in state <span class="math-container">$s_1$</span> and <span class="math-container">$s_2$</span> - but a bandit algorithm doesn't look ahead, or have ways to ask other bandit algorithms what they will do*, it only gets to know the end result, i.e. what the eventual reward is.</p>
  <p>At the start of learning, you may decide to set a simple equiprobable policy in all states i.e. <span class="math-container">$p(a_1) = 0.5, p(a_2) = 0.5$</span> and the same for each separate &quot;bandit&quot;. This would be a normal starting policy when you know nothing about rewards. In that case, the expected return from actions in state <span class="math-container">$s_0$</span> would be <span class="math-container">$q(s_0, a_1) = 1.5$</span> and <span class="math-container">$q(s_0, a_2) = 0$</span>, making the maximising choice from <span class="math-container">$s_0$</span> the action <span class="math-container">$a_1$</span> - if you only trained the first <span class="math-container">$s_0$</span> bandit, as it experienced the results from randomly trying <span class="math-container">$a_1$</span> and <span class="math-container">$a_2$</span>, and did not update the others from their starting policies, then the first bandit would learn to take action <span class="math-container">$a_1$</span>.</p>
  <p>Later on during learning, the policies in the later states <span class="math-container">$s_1$</span> and <span class="math-container">$s_2$</span> may have converged towards the maximising choices there. <em>For the purposes of this discussion, it doesn't matter how you do that, only that the policies have changed.</em></p>
  <p>Let's say for the sake of argument, learning has progressed in states <span class="math-container">$s_1$</span> and <span class="math-container">$s_2$</span> to the point that the policy chooses the maximising reward 90% of the time - action <span class="math-container">$a_2$</span> for the &quot;bandit&quot; in <span class="math-container">$s_1$</span> (getting +2 reward) and action <span class="math-container">$a_1$</span> for the &quot;bandit&quot; in <span class="math-container">$s_2$</span> (getting +3 reward).</p>
  <p>At that stage of learning, the expected return from actions in state <span class="math-container">$s_0$</span> would be <span class="math-container">$q(s_0, a_1) = 1.9$</span> and <span class="math-container">$q(s_0, a_2) = 2.4$</span>, making the maximising choice from <span class="math-container">$s_0$</span> the action <span class="math-container">$a_2$</span>.</p>
  <p>From the perspective of a bandit-like choice in state <span class="math-container">$s_0$</span>, the expected rewards and best action choice have changed over time, even though the environment is deterministic and has not changed in any way. That's because the policy is not static during the learning process, and this has an impact on earlier decisions due to how later decisions navigate the same environment.</p>
  <hr />
  <p>* This may immediately make you ask &quot;why not look ahead and link the states/action choices that way?&quot;. The answer is that you can, this is called planning, or searching (a tree search, typically). That is not relevant to understanding the bandit algorithm and related RL issues in early chapters of Sutton &amp; Barto, but will come up in various ways later in the book.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-10T13:48:00.157Z
Answers.Text: Thank you for the effort but the explanations are very confusing.  Let me go step by step. In first paragraph, you say "At the start of learning, you may decide to set a simple equiprobable policy in all states.".  What does this mean? Is this the policy you want to learn? If yes, then how can you set it yourself?
Answers.UserDisplayName: DSPinfinity
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-10T14:08:25.907Z
Answers.Text: @DSPinfinity when you want to learn an optimal policy, you typically start with some arbitrary policy and improve it. There is no way to gain experience without some kind of current policy - in order to learn from experience you must make decisions so you can observe what happens after you choose a certain action. So yes, when you start a learning process you do set a policy
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-10T14:14:55.700Z
Answers.Text: @DSPinfinity The idea of starting with an arbitrary policy, observing the results and making changes to that policy is the main focus of the chapter on bandit problems. After introducing the bandit concept, the chapter shows several variants on how to setup and learn policies
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-10T17:06:37.893Z
Answers.Text: Amazing explanation after update. You should write an RL book and I believe that it will be the best seller.
Answers.UserDisplayName: DSPinfinity
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-10T12:50:26.290Z
Answers.LastActivityDate: 2024-02-10T16:39:45.133Z
Answers.LastEditDate: 2024-02-10T16:39:45.133Z
Answers.UserDisplayName: Neil Slater
Body: <p>This is a text from Sutton-Barto, second edition, page 30:</p>
  <blockquote>
  <p>Even if the underlying task is stationary and deterministic,the learner faces a set of bandit like decision tasks each of which changes over time as learning proceeds and the agent’s decision-making policy changes. Reinforcement learning requires a balance between exploration and exploitation.</p>
  </blockquote>
  <p>Could someone explain (and if possible give some examples) this paragraph?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-02-10T16:17:31.517Z
Comments.Text: What is unclear exactly? What do you know or not know about what is written here?
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><sutton-barto>
Title: Unclear paragraph in Sutton-Barto on exploration/exploitation relating to bandit like decision tasks
UserDisplayName: DSPinfinity
ThreadText: # Unclear paragraph in Sutton-Barto on exploration/exploitation relating to bandit like decision tasks
  
  (Asked by: username_0 on 2024-02-10)
  
  This is a text from Sutton-Barto, second edition, page 30:
  
  > Even if the underlying task is stationary and deterministic,the learner faces a set of bandit like decision tasks each of which changes over time as learning proceeds and the agent’s decision-making policy changes. Reinforcement learning requires a balance between exploration and exploitation.
  
  Could someone explain (and if possible give some examples) this paragraph?
  
  **Tags:** reinforcement-learning, sutton-barto
  
  > **Comments:**
  > **username_1**: What is unclear exactly? What do you know or not know about what is written here?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2024-02-10. Score: 4 | Accepted answer
  
  The quoted text is from the end of a paragraph that is explaining some aspects of bandit algorithms, and looking forward to how knowledge of them is applicable in a reinforcement learning context. Just before your quote, the relevant text is:
  
  > For example, suppose the bandit task were nonstationary, that is, the true values of the actions changed over time. In this case exploration is needed even in the deterministic case to make sure one of the nongreedy actions has not changed to become better than the greedy one. As we shall see in the next few chapters, nonstationarity is the case most commonly encountered in reinforcement learning. Even if the underlying task [ . . . ]
  
  In particular, your quote is explaining that *deterministic* RL environments present a bit like a series of *non-stationary* bandit environments, because when a policy changes, it impacts the expected values of earlier actions, maybe to the point that an earlier "best" action choice needs to be changed.
  
  We can illustrate this with a simple deterministic RL environment. In the diagram, states are squares, actions circles, and rewards shown as labels on the next state transition.
  
  [![Simple deterministic MDP](https://i.sstatic.net/OVU1p.png)](https://i.sstatic.net/OVU1p.png)
  
  You can look at the choices of action in states $s\_0$, $s\_1$ and $s\_2$ as simple bandits. They have a choice between action $a\_1$ or $a\_2$. There is some extra complexity, because the results from the choice in $s\_0$ depend on the later choice in state $s\_1$ or $s\_2$. This means that the optimal choice for the "bandit" at state $s\_0$ depends on what the *current* choices will be in state $s\_1$ and $s\_2$ - but a bandit algorithm doesn't look ahead, or have ways to ask other bandit algorithms what they will do\*, it only gets to know the end result, i.e. what the eventual reward is.
  
  At the start of learning, you may decide to set a simple equiprobable policy in all states i.e. $p(a\_1) = 0.5, p(a\_2) = 0.5$ and the same for each separate "bandit". This would be a normal starting policy when you know nothing about rewards. In that case, the expected return from actions in state $s\_0$ would be $q(s\_0, a\_1) = 1.5$ and $q(s\_0, a\_2) = 0$, making the maximising choice from $s\_0$ the action $a\_1$ - if you only trained the first $s\_0$ bandit, as it experienced the results from randomly trying $a\_1$ and $a\_2$, and did not update the others from their starting policies, then the first bandit would learn to take action $a\_1$.
  
  Later on during learning, the policies in the later states $s\_1$ and $s\_2$ may have converged towards the maximising choices there. *For the purposes of this discussion, it doesn't matter how you do that, only that the policies have changed.*
  
  Let's say for the sake of argument, learning has progressed in states $s\_1$ and $s\_2$ to the point that the policy chooses the maximising reward 90% of the time - action $a\_2$ for the "bandit" in $s\_1$ (getting +2 reward) and action $a\_1$ for the "bandit" in $s\_2$ (getting +3 reward).
  
  At that stage of learning, the expected return from actions in state $s\_0$ would be $q(s\_0, a\_1) = 1.9$ and $q(s\_0, a\_2) = 2.4$, making the maximising choice from $s\_0$ the action $a\_2$.
  
  From the perspective of a bandit-like choice in state $s\_0$, the expected rewards and best action choice have changed over time, even though the environment is deterministic and has not changed in any way. That's because the policy is not static during the learning process, and this has an impact on earlier decisions due to how later decisions navigate the same environment.
  
  ---
  
  \* This may immediately make you ask "why not look ahead and link the states/action choices that way?". The answer is that you can, this is called planning, or searching (a tree search, typically). That is not relevant to understanding the bandit algorithm and related RL issues in early chapters of Sutton & Barto, but will come up in various ways later in the book.
  
  > **Comments:**
  > **username_0**: Thank you for the effort but the explanations are very confusing.  Let me go step by step. In first paragraph, you say "At the start of learning, you may decide to set a simple equiprobable policy in all states.".  What does this mean? Is this the policy you want to learn? If yes, then how can you set it yourself?  
  > **username_2**: @username_0 when you want to learn an optimal policy, you typically start with some arbitrary policy and improve it. There is no way to gain experience without some kind of current policy - in order to learn from experience you must make decisions so you can observe what happens after you choose a certain action. So yes, when you start a learning process you do set a policy  
  > **username_2**: @username_0 The idea of starting with an arbitrary policy, observing the results and making changes to that policy is the main focus of the chapter on bandit problems. After introducing the bandit concept, the chapter shows several variants on how to setup and learn policies  
  > **username_0**: Amazing explanation after update. You should write an RL book and I believe that it will be the best seller.  
  
  ---
  
  