Answers.Body: <p>A non-starving policy is a (behavior) policy that is <em>theoretically</em> guaranteed to visit each state and take all possible actions from each state an infinite number of times, so that to always update <span class="math-container">$Q(s, a)$</span>, <span class="math-container">$\forall s, \forall a$</span>, an infinite number of times. In the context of off-policy prediction, this criterion implies that any trajectory will have no zero probability under a behavior policy. As a consequence, the experience from the behavior policy sufficiently covers the possibilities of any target policy.</p>
  
  <p>An example of a non-starving policy is the <em><span class="math-container">$\epsilon$</span>-greedy policy</em>, which, with <span class="math-container">$0 &lt; \epsilon \leq 1$</span> (which is usually a small number between <span class="math-container">$0$</span> and <span class="math-container">$1$</span>) probability, takes a random action from a given state, and, with <span class="math-container">$1-\epsilon$</span> probability, takes the current best action, that is, the action with the highest value from a given state, according to the current value function.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-12T03:22:21.787Z
Answers.Text: Could I say that the presence of a non-starving behavior policy is to guarantee that an importance sampling ratio does not go to "infinity"?
  
  A second thought tells me that this is not the case. Non-starving seems to be a "requirement" for all policies considered in RL?
Answers.UserDisplayName: Phizaz
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-12T10:40:30.160Z
Answers.Text: @Phizaz You can ask another question on the website.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-12T17:21:57.513Z
Answers.Text: You didn't answer my question on the "why is it required" part.
Answers.UserDisplayName: Phizaz
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-12T19:18:09.250Z
Answers.Text: @Phizaz I answered: "Of course, while the agent is learning, it needs to sufficiently explore the state and action spaces, so that to learn the most rewarding (or profitable) actions from each state.".
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-14T03:58:50.563Z
Answers.Text: Does it have anything to do with off-policy learning? Or it's just a common assumption needed for any learning algorithm to work? I suspect if that the case, it is not worth mentioning in the paper at all.
Answers.UserDisplayName: Phizaz
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-14T12:34:22.917Z
Answers.Text: @Phizaz Yes, it has a lot to do with off-policy algorithms. In off-policy algorithms, there are two policies: the policy that you use to take actions while you are learning (the behavior policy) and the policy that you want to find. In these algorithms, the behavior policy should be a non-starving policy. It may be implicit that any behavior policy is non-starving. If it is non-starving the algorithms may not find the optimal policy.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-15T15:41:38.413Z
Answers.Text: In a prediction setting, there is no need to consider an optimality. I think a reasonable explanation is that we need to make sure that a behavior policy "covers" the target policy. Without which assumption, there will exist some trajectory that is in the target but not in the behavior. For those trajectories, the behavior will fail to capture their values in its estimate.
Answers.UserDisplayName: Phizaz
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-15T15:48:18.623Z
Answers.Text: @Phizaz Yes, I think this is a good way of looking at it. However, note that I had not made any distinction between the prediction and control problems.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-11T12:59:48.743Z
Answers.LastActivityDate: 2019-09-15T16:09:55.830Z
Answers.LastEditDate: 2019-09-15T16:09:55.830Z
Answers.UserDisplayName: nbro
Body: <p>In the paper, <a href="https://scholarworks.umass.edu/cgi/viewcontent.cgi?article=1079&amp;context=cs_faculty_pubs" rel="nofollow noreferrer">Eligibility Traces for off-Policy Policy Evaluation</a> (2010), by Doina Precup et al., mentioned the term "non-starving" many times. The specific use of the term was like "non-starving policy" in the context of off-policy learning. </p>
  
  <p>A specific mention of the term</p>
  
  <blockquote>
    <p>we consider a method that requires nothing of the behavior
    policy other than that it be non-starving, i.e., that it
    never reaches a time when some state-action pair is never
    visited again.</p>
  </blockquote>
  
  <p>What does the thing look like intuitively? Why is it required?</p>
  
Tags: <reinforcement-learning><definitions><papers><off-policy-methods>
Title: What is a non-starving policy in reinforcement learning?
UserDisplayName: Phizaz
ThreadText: # What is a non-starving policy in reinforcement learning?
  
  (Asked by: username_0 on 2019-09-11)
  
  In the paper, [Eligibility Traces for off-Policy Policy Evaluation](https://scholarworks.umass.edu/cgi/viewcontent.cgi?article=1079&context=cs_faculty_pubs) (2010), by Doina Precup et al., mentioned the term "non-starving" many times. The specific use of the term was like "non-starving policy" in the context of off-policy learning.
  
  A specific mention of the term
  
  > we consider a method that requires nothing of the behavior
  > policy other than that it be non-starving, i.e., that it
  > never reaches a time when some state-action pair is never
  > visited again.
  
  What does the thing look like intuitively? Why is it required?
  
  **Tags:** reinforcement-learning, definitions, papers, off-policy-methods
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-09-11. Score: 4 | Accepted answer
  
  A non-starving policy is a (behavior) policy that is *theoretically* guaranteed to visit each state and take all possible actions from each state an infinite number of times, so that to always update $Q(s, a)$, $\forall s, \forall a$, an infinite number of times. In the context of off-policy prediction, this criterion implies that any trajectory will have no zero probability under a behavior policy. As a consequence, the experience from the behavior policy sufficiently covers the possibilities of any target policy.
  
  An example of a non-starving policy is the *$\epsilon$-greedy policy*, which, with $0 < \epsilon \leq 1$ (which is usually a small number between $0$ and $1$) probability, takes a random action from a given state, and, with $1-\epsilon$ probability, takes the current best action, that is, the action with the highest value from a given state, according to the current value function.
  
  > **Comments:**
  > **username_0**: Could I say that the presence of a non-starving behavior policy is to guarantee that an importance sampling ratio does not go to "infinity"?  A second thought tells me that this is not the case. Non-starving seems to be a "requirement" for all policies considered in RL?  
  > **username_1**: @Phizaz You can ask another question on the website.  
  > **username_0**: You didn't answer my question on the "why is it required" part.  
  > **username_1**: @Phizaz I answered: "Of course, while the agent is learning, it needs to sufficiently explore the state and action spaces, so that to learn the most rewarding (or profitable) actions from each state.".  
  > **username_0**: Does it have anything to do with off-policy learning? Or it's just a common assumption needed for any learning algorithm to work? I suspect if that the case, it is not worth mentioning in the paper at all.  
  > **username_1**: @Phizaz Yes, it has a lot to do with off-policy algorithms. In off-policy algorithms, there are two policies: the policy that you use to take actions while you are learning (the behavior policy) and the policy that you want to find. In these algorithms, the behavior policy should be a non-starving policy. It may be implicit that any behavior policy is non-starving. If it is non-starving the algorithms may not find the optimal policy.  
  > **username_0**: In a prediction setting, there is no need to consider an optimality. I think a reasonable explanation is that we need to make sure that a behavior policy "covers" the target policy. Without which assumption, there will exist some trajectory that is in the target but not in the behavior. For those trajectories, the behavior will fail to capture their values in its estimate.  
  > **username_1**: @Phizaz Yes, I think this is a good way of looking at it. However, note that I had not made any distinction between the prediction and control problems.  
  
  ---
  
  