In the paper, Eligibility Traces for off-Policy Policy Evaluation (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?


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.

  • $\begingroup$ 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? $\endgroup$ – Phizaz Sep 12 '19 at 3:22
  • $\begingroup$ @Phizaz You can ask another question on the website. $\endgroup$ – nbro Sep 12 '19 at 10:40
  • $\begingroup$ You didn't answer my question on the "why is it required" part. $\endgroup$ – Phizaz Sep 12 '19 at 17:21
  • $\begingroup$ @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.". $\endgroup$ – nbro Sep 12 '19 at 19:18
  • $\begingroup$ 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. $\endgroup$ – Phizaz Sep 14 '19 at 3:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.